¿Cálculo Lambda sin variables libres es tan fuerte como el cálculo lambda?

Question

Primera pregunta: ¿Cómo se demostraría que al eliminar las variables libres (sin límite) del cálculo de Lambda y permitiría solo las variables vinculadas, su potencia no se reduce (todavía está Turing-Completa)?

Segunda pregunta: ¿Se da la proposición anterior?¿Es Lambda Cálculo Sans Variables libres realmente Turing-Completa?

Answer 1

Supongo que usted se está refiriendo al terrible cálculo de Lambda.

Si es así, escriba $ \ newcommand {\ num} [1] {\ ulcorner # 1 \ urcorner} \ num {n} $ para el número de la iglesia de el Unmber Natural $ n $ .

Se sabe que existe un término cerrado (es decir, sin variables libres) $ tm $ tal que $$ Tm \ \ num {i} \ \ num {n \ \= _ {\ beta \ eta} \ \ num {m} $$ Si, y solo si, el $ i $ -th turing Machine (en alguna enumeración estándar) Ejecute con entrada $ n \ en \ mathbb n $ (codificado como de costumbre) se detiene a regresar $ m $ como salida.

De hecho, escribir $ tm $ es un ejercicio estándar de "programación" en el cálculo lambda. Para eso, uno puede representar la cinta como un par o pares de pares de ... (también conocido como una lista de consigo) de símbolos. Luego, se puede escribir una subrutina de "paso" para avanzar la cinta y el estado de TM. Finalmente, se invoca la subrutina paso a paso hasta que se alcanza un estado de hallo. Este último paso se puede lograr utilizando un combinador de punto fijo, como $ y $ .

Dado que podemos simular cualquier máquina de Turing, obtenemos la integridad.

---

Prueba alternativa, que es (en mi opinión) más fácil realizar realmente en detalle: probar que cualquier función recursiva general puede ser $ \ lambda $ -defining usando un término de lambda cerrado. Para eso, proceda por la inducción sobre la definición de la función recursiva general.

De hecho, incluso si no tiene como objetivo para los términos cerrados, en este ejercicio de programación, obtendrá uno cerrado de una manera natural. Después de todo, cuando la programación nunca necesita una variable que no fue declarada de antemano.

Dado que las funciones recursivas generales son exactamente aquellas que pueden ser calculadas por una máquina de Turing, obtenemos la integridad de los cálculos de lambda cerrados.