Base incompleta de combinadores

Esto está inspirado en esta pregunta. Sea la colección de todos los combinadores que solo tienen dos variables ligadas. ¿ es combinatoriamente completa? $\mathcal{C}$ $\mathcal{C}$

Creo que la respuesta es negativa, sin embargo, no pude encontrar una referencia para esto. También me interesarían las referencias para pruebas de incompletitud combinatoria de conjuntos de combinadores (puedo ver por qué el conjunto consiste en combinadores con una sola variable enlazada es incompleto, por lo que estos conjuntos deberían contener más que solo elementos de ). $\mathcal{D}$ $\mathcal{D}$

lo.logic lambda-calculus combinatory-logic tci
fuente

¿Podría aclarar qué quiere decir con el número de variables ligadas de un combinador (= término lambda cerrado)? ¿Número total de abstracciones lambda?

Noam Zeilberger

Sí, esto es lo que quise decir.

tci

En realidad, tal vez eso no sea exactamente lo que quiso decir ... tal vez más bien se refiere al número total de variables distintas utilizadas en abstracciones lambda, de modo que, por ejemplo

tiene dos variables ligadas distintas, a pesar de tener cuatro abstracciones lambda? En ese caso, parece que Rick Statman respondió exactamente esta pregunta (negativamente), en " Dos variables no son suficientes ".

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

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

Noam Zeilberger

Correcto. Creo que esta es la respuesta que estaba buscando, y definitivamente esperaba que fuera el resultado de Statman. Todavía no lo he verificado, pero creo que esto también daría una respuesta negativa a la pregunta que mencioné. Si lo publicaras como respuesta, con gusto lo aceptaría.

tci

Respuestas:

[Expandiendo el comentario en una respuesta.]

Primero, solo una aclaración sobre el conteo de variables ligadas en un combinador (= término cerrado) . Interpreto la pregunta como preguntando sobre modo que, por ejemplo, el término cuenta como tener dos variables ligadas, a pesar de tener cuatro ligantes (es decir, abstracciones lambda). Esta forma de contar fue inicialmente un poco extraña para mí, ya que no es invariable bajo $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)$

Conversión

: por ejemplo,

esequivalente a

, pero

tiene cuatro nombres distintos de variables enlazadas. Sin embargo, esto no es realmente un problema, porque elnúmeromínimode nombres de variables ligadas distintas necesarios para escribir un término cerrado

es igual al

α

$\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$ y la última noción es invariante bajo conversión

α

$\alpha$

Entonces, que sea la colección de todos los combinadores que se pueden escribir utilizando como máximo dos variables ligadas distintas, o de manera equivalente la colección de todos los combinadores cuyos subterms tienen como máximo dos variables libres. $\mathcal{C}$

Teorema (Statman) : no está combinatoriamente completo. $\mathcal{C}$

Parece que la prueba original de esto está contenida en un informe técnico de Rick Statman:

Combinadores hereditarios de la orden dos. Carnegie Mellon Math Department Technical Report 88-33, agosto de 1988. ( pdf )

Statman define una colección de combinadores esencialmente isomórficos que él llama "HOT", por "hereditariamente de orden dos". El informe técnico en realidad muestra que el problema de la palabra (es decir, la igualdad ) para HOT aún no se puede decidir, a pesar del hecho de que no es combinatoriamente completo. Más tarde, Statman escribió un breve documento autónomo con la prueba de que HOT no se completa combinatoriamente en: $\beta$

Dos variables no son suficientes. Actas de la novena conferencia italiana sobre informática teórica, págs. 406-409, 2005. ( acm )

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

Noam Zeilberger
fuente