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

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

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

lo.logic lambda-calculus combinatory-logic TCI
источник

Не могли бы вы уточнить, что вы подразумеваете под числом связанных переменных комбинатора (= замкнутый лямбда-член)? Общее количество лямбда-абстракций?

Ноам Цайлбергер

Да, это то, что я имел в виду.

TCI

(λ x . x (λ y . y)) (λ x . λ y . x y)

$(\lambda x.x(\lambda y.y))(\lambda x.\lambda y.x y)$

Правильно. Я думаю, что это ответ, который я искал, и я определенно ожидал, что это будет результатом Statman. Я еще не проверял, но я думаю, что это также дало бы отрицательный ответ на вопрос, который я упомянул. Если бы вы опубликовали это как ответ, я бы с радостью принял это.

TCI

Ответы:

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

$t$

the total number of distinct bound variable names in t

$\text{the total number of distinct bound variable names in }t$

t = (λ x . x (λ y . y)) (λ x . λ y . y x)

$t = (\lambda x.x(\lambda y.y))(\lambda x.\lambda y.yx)$

α

$\alpha$

t

$t$

α

$\alpha$

t^{'} = (λ x . x (λ y . y)) (λ a . λ b . b a)

$t' = (\lambda x.x(\lambda y.y))(\lambda a.\lambda b.ba)$

t^{'}

$t'$

t

$t$

the maximum number of free variables in a subterm of t

$\text{the maximum number of free variables in a subterm of }t$

α

$\alpha$

$\mathcal{C}$

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

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

$\beta$

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

$Hn$ $Hn$ $n+1$ $\beta$ $n$ $S = \lambda x.\lambda y.\lambda z.(xz)(yz)$ $n$ $n$ $Hn$ $n+1$

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