Неполная основа комбинаторов

10

Это вдохновлено этим вопросом. Пусть будет совокупностью всех комбинаторов, которые имеют только две связанные переменные. Является ли C комбинаторно полным?CC

Я считаю, что ответ отрицательный, однако я не смог найти ссылку для этого. Я также был бы заинтересован в ссылках для доказательства комбинаторной неполноты множеств комбинаторов (я понимаю, почему множество состоящее из комбинаторов только с одной связанной переменной, является неполным, поэтому эти множества должны содержать не только элементы D ).DD

TCI
источник
Не могли бы вы уточнить, что вы подразумеваете под числом связанных переменных комбинатора (= замкнутый лямбда-член)? Общее количество лямбда-абстракций?
Ноам Цайлбергер
Да, это то, что я имел в виду.
TCI
3
(λx.x(λy.y))(λx.λy.xy)
Правильно. Я думаю, что это ответ, который я искал, и я определенно ожидал, что это будет результатом Statman. Я еще не проверял, но я думаю, что это также дало бы отрицательный ответ на вопрос, который я упомянул. Если бы вы опубликовали это как ответ, я бы с радостью принял это.
TCI

Ответы:

7

[Расширяя комментарий в ответ.]

t

the total number of distinct bound variable names in t
t=(λx.x(λy.y))(λx.λy.yx)αtαt=(λx.x(λy.y))(λa.λb.ba)tt
the maximum number of free variables in a subterm of t
α

C

C

Кажется, что оригинальное доказательство этого содержится в техническом отчете Рика Стэтмана:

  • Комбинаторы наследственно второго порядка. Технический отчет математического факультета Карнеги-Меллона, 88-33, август 1988 г. ( pdf )

β

  • Двух переменных недостаточно. Материалы 9-й итальянской конференции по теоретической информатике, с. 406-409, 2005. ( ACM )

HnHnn+1βnS=λx.λy.λz.(xz)(yz)nnHnn+1

Ноам Цайлбергер
источник