¿Cuál es la prueba de la afirmación, ‘Un programa escrito en cálculo lambda mecanografiado siempre termina’? Educación te da un futuro mejor

Pregunta originalmente respondida: ¿Cuál es la prueba de la afirmación “Un programa escrito en cálculo lambda mecanografiado siempre finaliza”?

No hay tal prueba. Simplemente no es el caso que los programas escritos en un cálculo lambda mecanografiado siempre terminan. Si el sistema de tipos para el cálculo Lambda en consideración admite tipos recursivos, entonces es posible escribir programas sin terminación. Incluso si no hay tipos recursivos, la existencia de un operador de recursión en el nivel de valor también puede provocar que los programas no finalicen, a pesar del cálculo del tipo.

Ahora, si restringimos nuestra atención a los sistemas de tipos sin operadores y tipos recursivos, podemos construir una prueba de que todos los programas siempre terminan.

Por ejemplo, veamos el cálculo lambda simplemente escrito.

Suponga que se nos da un conjunto contable [matemático] Atómico = \ {a_1, a_2, \ cdots \} [/ matemático] de tipos básicos.

Defina el conjunto [matemático] Tipos [/ matemático] de tipos de la siguiente manera:

[math] (a_i \ en Atomic) \ implica (a_i \ en Tipos) [/ math].
[matemáticas] (\ alpha \ en Tipos \ land \ beta \ en Tipos) \ implica (\ alpha \ rightarrow \ beta) \ en Tipos [/ math].

Supongamos también que para cualquier tipo [matemática] \ alpha [/ matemática] tenemos conjuntos contables [matemática] Consts = \ {c_1 ^ {\ alpha}, c_2 ^ {\ alpha}, \ cdots \} [/ math] y [ matemática] Vars = \ {v_1 ^ {\ alpha}, v_2 ^ {\ alpha}, \ cdots \} [/ math] de constantes y variables de ese tipo.

Defina el conjunto [math] TypedTerms [/ math] de la siguiente manera:

[math] (c ^ {\ alpha} \ en Consts) \ implica (c ^ {\ alpha} \ en TypedTerms) [/ math]
[matemáticas] (v ^ {\ alpha} \ en Vars) \ implica (v ^ {\ alpha} \ en TypedTerms) [/ math]
[matemáticas] (M ^ {\ alpha \ rightarrow \ beta} \ en TypedTerms \ land N ^ {\ alpha} \ en TypedTerms) \ implica (M ^ {\ alpha \ rightarrow \ beta} N ^ {\ alpha}) ^ {\ beta} \ en TypedTerms [/ math]
[matemáticas] (v ^ {\ alpha} \ en Vars) \ land (M ^ {\ beta} \ en TypedTerms) \ implica (\ lambda v ^ {\ alpha} .M ^ {\ beta}) ^ {\ alpha \ rightarrow \ beta} \ en TypedTerms [/ math]

Entonces tenemos un conjunto de términos escritos a partir de constantes básicas escritas y variables escritas, conocidas colectivamente como átomos escritos, donde el tipo de un término se escribe como un superíndice. Utilizo una notación de superíndice ([matemáticas] x ^ {\ alpha} [/ matemáticas]) en lugar de la notación de dos puntos ([matemáticas] x: \ alfa [/ matemáticas]) para no tener que especificar explícitamente si el tipo es en realidad una parte de la sintaxis del término o puede ser inferida por algún algoritmo.

Un ejemplo simple de dicho término sería: [matemáticas] I _ {\ alpha}: = (\ lambda x ^ {\ alpha} .x ^ {\ alpha}) ^ {\ alpha \ rightarrow \ alpha} [/ math] cuál es la función de identidad en el tipo [math] \ alpha [/ math].

Ahora, el cálculo en el cálculo lambda se realiza mediante un proceso conocido como reducción, que se realiza sustituyendo recursivamente términos de tipo por variables tipadas. Existen varias relaciones de reducción diferentes, las más conocidas son probablemente [math] \ beta [/ math] -reduction y [math] \ beta \ eta [/ math] -reduction.

Entonces, lo siguiente que tenemos que formalizar es el concepto de sustitución. Para hacer esto necesitaremos los conceptos de alcance y de variables libres y enlazadas.

En la abstracción lambda [matemáticas] (\ lambda x ^ {\ alpha} .M ^ {\ beta}) ^ {\ alpha \ rightarrow \ beta} [/ matemáticas] el término [matemáticas] M ^ {\ beta} [/ matemáticas] se llama el alcance de la abstracción.

Una ocurrencia específica de una variable [matemática] x ^ {\ alpha} [/ matemática] en algún término [matemática] P ^ {\ beta} [/ matemática], se llama obligado si es parte de algún subterráneo de la forma [math] (\ lambda x ^ {\ alpha} .M ^ {\ gamma}) ^ {\ alpha \ rightarrow \ gamma} [/ math], de lo contrario, está libre. Si hay ocurrencias libres de una variable en un término [matemática] M [/ matemática], entonces la variable se llama variable libre del término. El conjunto de todas las variables libres de un término [matemática] M [/ matemática] se escribe [matemática] FV (M) [/ matemática].

Escribamos [math] [x ^ {\ alpha} = N ^ {\ alpha}] M ^ {\ beta} [/ math] para la sustitución del término [math] N [/ math] de tipo [math] \ alpha [/ math] para la variable [math] x [/ math] del tipo [math] \ alpha [/ math] en el término [math] M [/ math] del tipo [math] \ beta [/ math]. Luego, eliminando las anotaciones de tipo por conveniencia, la definición de esta operación de sustitución es la siguiente:

[matemáticas] [x = N] x = N; x \ en Vars [/ math]
[matemáticas] [x = N] c = c; c \ in Vars \ not = x [/ math] o [math] c \ in Consts [/ math]
[matemáticas] [x = N] (PQ) = ([x = N] P [x = N] Q) [/ matemáticas]
[matemáticas] [x = N] (\ lambda xP) = \ lambda xP [/ matemáticas]
[matemáticas] [x = N] (\ lambda yP) = \ lambda y. ([x = N] P); y \ not = x, y \ not \ en FV (N), [/ math] o [math] x \ not \ en FV (P) [/ math]
[matemáticas] [x = N] (\ lambda yP) = \ lambda z. ([x = N] [y = z] P); y \ not = x, y \ en FV (P), x \ en FV (P), z \ not \ en FV (NP) [/ math]

Ahora podemos definir [math] \ beta [/ math] -reduction de la siguiente manera:

Dado un término [matemática] P [/ matemática] de la forma [matemática] (\ lambda xM) N [/ matemática], llamamos [matemática] P [/ matemática] a [matemática] \ beta [/ matemática] -dex y llame al término [matemáticas] [x = N] M [/ matemáticas] su contracción. Una reducción de un paso [matemática] \ beta [/ matemática] es el reemplazo de la redex por su contracción.

Escribimos [math] (\ lambda xM) N \ triangleright_ {1 \ beta} [x = N] M [/ math].

En general, si podemos realizar una secuencia finita de contracciones de un solo paso en un término [matemática] P [/ matemática] produciendo un término [matemática] P ‘[/ matemática], entonces esto se conoce como [matemática] \ beta [ / math] -reduction y escrito [math] P \ triangleright _ {\ beta} P ‘[/ math].

Entonces, por ejemplo: [matemáticas] (\ lambda xx (xy)) N \ triangleright _ {\ beta} [x = N] (x (xy)) = ([x = N] x) ([x = N] (xy )) = N ([x = N] x [x = N] y) = N (Ny) [/ matemáticas]

Ahora, si comenzamos desde un término determinado y seguimos reduciendo los redexes, no hay garantía de que este sea un proceso finito. Considere el término [matemáticas] M = NN, donde N = \ lambda x.xxy [/ matemáticas].

Luego, aplicando las definiciones anteriores tenemos:

[matemáticas] M \ triangleright_ {1 \ beta} Mi \ triangleright_ {1 \ beta} Myy \ triangleright_ {1 \ beta} Myyy \ cdots [/ math].

Tenga en cuenta que cualquier término puede contener múltiples redexes y que, por lo tanto, puede haber múltiples reducciones diferentes a partir de ese término, dependiendo de la redex elegida. Otro teorema importante del cálculo lambda, el teorema de Church-Rosser, demuestra que el orden en que se reducen estos redexes es irrelevante para el resultado final.

La afirmación de que los programas en el cálculo lambda simplemente tipeado siempre terminan, básicamente significa que no hay cadenas infinitas como se demostró anteriormente de las reducciones [matemáticas] \ beta [/ matemáticas] posibles para los términos en ese cálculo. Esto se conoce como el Teorema de Normalización Fuerte para el cálculo Lambda simplemente tipado.

Presentaré aquí una prueba siguiendo un método promovido por Tait.

Comenzamos con algunas definiciones:

Un término en nuestro cálculo se llama forma normal, específicamente [math] \ beta [/ math] -forma normal, si no contiene redexes, es decir, si no puede reducirse más. Por ejemplo, [math] (\ lambda xx) c [/ math] no es una forma normal, porque contiene una redex, pero si reducimos esa redex obtenemos [math] c [/ math], que es una forma normal, porque [math] c [/ math] es una constante y no se reduce más.
Cualquier término en nuestro cálculo se llama normalizable si admite una forma normal, es decir, existe alguna reducción a una forma normal.
Un término se llama fuertemente normalizable si todas las reducciones de ese término son a una forma normal, o dicho de otra manera, son finitas. Según el teorema de Church-Rosser, esa forma normal es única.
Un término se llama iff fuertemente computable

es un término de tipo atómico ([matemática] X ^ {a} [/ matemática]) y es fuertemente normalizable
es un término de la forma [matemática] X ^ {\ alpha \ rightarrow \ beta} [/ matemática] y para cada término altamente computable [matemática] Y ^ {\ alpha} [/ matemática] el término [matemática] (XY ) ^ {\ beta} [/ math] es altamente computable.

La prueba funciona mostrando que

cada término altamente computable es fuertemente normalizable
Cada término es fuertemente computable.

Lema 1

Dado cualquier tipo [math] \ alpha [/ math] se cumple lo siguiente:

Cada término de la forma [math] (aX_1 \ cdots X_n) ^ {\ alpha} [/ math], con [math] a [/ math] un átomo y [math] X_1, \ cdots, X_n [/ math] fuertemente normalizable, es altamente computable.
Cada término altamente computable de tipo [math] \ alpha [/ math] es altamente normalizable.

Prueba

Usamos inducción en el número de ‘[math] \ rightarrow [/ math]’ s en [math] \ alpha [/ math].

Base: [matemática] \ alpha [/ matemática] es atómica

[math] X_1, \ cdots X_n [/ math] son altamente normalizables, por lo tanto, [math] (aX_1 \ cdots X_n) [/ math] debe ser fuertemente normalizable, por lo tanto, según la definición de fuertemente computable, es fuertemente computable.

Por definición de fuertemente computable (caso 1).

Inducción: [math] \ alpha [/ math] tiene la forma [math] \ beta \ rightarrow \ gamma [/ math]

Suponga que [math] Y ^ {\ beta} [/ math] es altamente computable, entonces por la hipótesis de inducción [math] Y ^ {\ beta} [/ math] se está normalizando fuertemente.
Por lo tanto, también según la hipótesis de inducción, el término [matemáticas] (aX_1 \ cdots X_nY) ^ {\ gamma} [/ matemáticas] es altamente computable.

Por lo tanto, [math] (aX_1 \ cdots X_n) ^ {\ alpha} [/ math] es altamente computable por definición de fuertemente computable (caso 2).

Deje que [math] X ^ {\ alpha} [/ math] sea altamente computable y no contenga la variable [math] x ^ {\ beta} [/ math].
Ahora, según la hipótesis de inducción (caso 1) con [matemática] n = 0 [/ matemática], [matemática] x [/ matemática] es altamente computable. Por lo tanto, [math] (Xx) ^ {\ gamma} [/ math] es altamente computable, porque, por definición de fuertemente computable (caso 2).

Entonces, según la hipótesis de inducción, [math] (Xx) ^ {\ gamma} [/ math] se está normalizando fuertemente.

Pero entonces [matemática] X ^ {\ alpha} [/ matemática], debe normalizarse fuertemente, porque si un término se normaliza fuertemente, entonces cada subterráneo de ese término debe normalizarse fuertemente, de lo contrario existiría una reducción infinita del subterráneo eso no estaba normalizando fuertemente.

QED

Lema 2 .

Si [math] [x ^ {\ alpha} = N ^ {\ alpha}] M ^ {\ beta} [/ math] es altamente computable y [math] N ^ {\ alpha} [/ math] es altamente computable, entonces también lo es el término [math] (\ lambda x ^ {\ alpha} .M ^ {\ beta}) N ^ {\ alpha} [/ math], donde [math] x ^ {\ alpha} \ not \ in FV (M ^ {\ beta}) [/ math].

Prueba

Deje [math] \ beta = \ beta_1 \ rightarrow \ cdots \ rightarrow \ beta_n \ rightarrow \ theta [/ math], con [math] \ theta \ en Atomic [/ math].

También deje que [math] M_i ^ {\ beta_i}, i \ in \ {1 \ cdots n \} [/ math] sean términos altamente computables.

Se nos dice que [matemáticas] [x ^ {\ alpha} = N ^ {\ alpha}] M ^ {\ beta} [/ matemáticas] es altamente computable, por lo que se deduce que [matemáticas] (([x = N] M) M_1 \ cdots M_n) ^ {\ theta} [/ math] es altamente normalizable. Esto se debe a que cualquier término [matemático] (MM_1 \ cdots M_n) ^ {\ theta} [/ matemático] debe ser altamente computable, dado que los [matemático] M_i [/ matemático] son altamente computables y la definición de computabilidad sólida (caso 2) Pero entonces, dado que [math] \ theta [/ math] es atómico, por la definición de computabilidad fuerte (caso 1), el término también se está normalizando fuertemente.

Entonces el lema seguirá si podemos establecer que [math] ((\ lambda xM) NM_1 \ cdots M_n) ^ {\ theta} [/ math] se está normalizando fuertemente.

Ahora, debido a que [math] (([x = N] M) M_1 \ cdots M_n) ^ {\ theta} [/ math] se está normalizando fuertemente, también lo son todos sus subterms, de lo contrario existiría una reducción infinita de uno de Los subterms. En particular, todos los términos [matemática] [x = N] M [/ matemática], [matemática] M_i, i \ in \ {1 \ cdots n \} [/ matemática], se normalizan fuertemente. Esto significa que no se puede hacer una reducción infinita por completo dentro de uno de estos subterms.

Eso a su vez significa que cualquier reducción infinita de [math] (\ lambda x ^ {\ alpha} .M ^ {\ beta}) N ^ {\ alpha} [/ math] debe tener la siguiente forma:

[matemáticas] ((\ lambda xM) NM_1 \ cdots M_n) \ triangleright _ {\ beta} [/ matemáticas]

[matemáticas] ((\ lambda xM ‘) N’M’_1 \ cdots M’_n) \ triangleright_ {1 \ beta} (M \ triangleright _ {\ beta} M’, etc.) [/ math]

[matemáticas] ([x = N ‘] M’) M’_1 \ cdots M’_n \ triangleright _ {\ beta} [/ math]

[matemáticas] \ cdots [/ matemáticas]

Pero, si [matemática] M \ triangleright M ‘[/ matemática] y [matemática] N \ triangleright N’ [/ matemática] entonces tenemos que [matemática] [x = N] M \ triangleright [x = N ‘] M ‘[/matemáticas]. Entonces existiría una reducción infinita:

[matemáticas] ([x = N] M) M_1 \ cdots M_n \ triangleright _ {\ beta} [/ matemáticas]

[matemáticas] ([x = N ‘] M’) M’_1 \ cdots M’_n \ triangleright _ {\ beta} [/ math]

[matemáticas] \ cdots [/ matemáticas].

Y esta reducción infinita contradice el hecho de que ya hemos demostrado que [math] ([x = N] M) M_1 \ cdots M_n [/ math] es fuertemente normalizable.

Concluimos que [math] ((\ lambda xM) NM_1 \ cdots M_n) [/ math] es fuertemente normalizable.

QED

Lema 3

Para todas las variables [math] x_i ^ {\ alpha_i} [/ math] y todos los términos altamente computables [math] N_i ^ {\ alpha_i} [/ math], con [math] i \ in \ {1 \ cdots n \} [/ math], el término [math] M ^ {* \ beta} = [x_1 = N_1] \ cdots [x_n = N_n] M [/ math], es altamente computable.

Prueba:

Utilizamos inducción estructural en [matemática] M [/ matemática].

[matemáticas] M [/ matemáticas] es una variable [matemáticas] x_i [/ matemáticas]. Entonces [matemática] M ^ * [/ matemática] es [matemática] N_i [/ matemática], que es altamente computable por la suposición de este lema.

[math] M [/ math] es una constante o una variable distinta de [math] x_1 \ cdots x_n [/ math]. Entonces [math] M ^ * [/ math] es [math] M [/ math], que es fuertemente computable por el lema 1.

[math] M [/ math] tiene la forma [math] M_1M_2 [/ math]. Entonces [matemática] M ^ * [/ matemática] es [matemática] M_1 ^ * M_2 ^ * [/ matemática]. Según la hipótesis de inducción, tanto [matemática] M_1 ^ * [/ matemática] como [matemática] M_2 ^ * [/ matemática] son altamente computables y, por lo tanto, según la definición de computabilidad sólida (caso 2) también lo es [matemática] M_1 ^ * M_2 ^ * [/ matemáticas].

[math] M [/ math] tiene la forma [math] (\ lambda x.M_1) [/ math]. Entonces [math] M ^ * [/ math] es [math] (\ lambda x.M_1 ^ *) [/ math]. Para que [math] M ^ * [/ math] sea fuertemente computable, según la definición de fuertemente computable (caso 2), debe contener eso para todos los [math] N [/ math] fuertemente computable que [math] M ^ * N [/ math] es altamente computable.
Pero tenemos que [matemáticas] M ^ * N = (\ lambda x.M_1 ^ *) N \ triangleright_ {1 \ beta} [x = N] M_1 ^ * [/ matemáticas], que es altamente computable por la hipótesis de inducción con [matemáticas] n + 1 [/ matemáticas] para [matemáticas] n [/ matemáticas].

QED

Teorema principal

Cualquier término escrito [matemática] M ^ {\ beta} [/ matemática] es altamente normalizable.

Prueba:

Como un caso especial del lema 3 donde [matemática] x_i = N_i, i \ in \ {1 \ cdots n \} [/ matemática] ya tenemos que [matemática] M ^ {\ beta} [/ matemática] es altamente computable . Además, la prueba del lema ya ha establecido que cualquier término altamente computable se está normalizando fuertemente.

QED