Lambda Calculus sans variables libres est aussi fort que la Calmbda Calculus?

Question

Première question: comment prouver qu'en supprimant les variables libres (non liées) du calcul de Lambda et permettant uniquement des variables liées, sa puissance n'est pas réduite (elle est toujours complète)?

Deuxième question: La proposition est-elle donnée ci-dessus vraiment vraie?Est-ce que Lambda Calculus Sans variables libres est vraiment Turing-complète?

Answer 1

Je suppose que vous vous référez au calcul de la Lambda non typée.

Si oui, écrivez $ \ newcommand {\ num} [1] {\ ulcorner # 1 \ urcorner} \ num {n} $ pour le chiffre de l'église de Le NATUREL DUBBER N $ N $ .

On sait qu'il existe un terme fermé (c'est-à-dire sans variables libres) $ TM $ tel que $$ Tm \ \ num {i} \ \ num {n} \= _ {\ bêta \ eta} \ \ num {m} $$ Si, et seulement si, le I $ I $ -TH Turing Machine (dans une énumération standard) Exécuter avec l'entrée $ N \ In \ mathbb n $ (codé comme d'habitude) arrête de retourner $ m $ comme sortie.

En effet, écrire $ TM $ est une "programmation" standard dans le calcul de la Lambda. Pour cela, on peut représenter la bande comme une paire-ou des paires de paires de ... (alias une liste des inconvénients) des symboles. Ensuite, un sous-programme "pas en marche" pour faire progresser la bande et l'état TM peut être écrit. Enfin, le sous-programme intensif est invoqué jusqu'à ce qu'un état d'arrêt soit atteint. Cette dernière étape peut être obtenue à l'aide d'un combinateur à point fixe tel que $ y $ .

Puisque nous pouvons simuler n'importe quelle machine Turing, nous obtenons une complétude.

---

Une preuve alternative, qui est (à mon avis) plus facile à jouer en détail en détail: prouver que toute fonction récursive générale peut être $ \ lambda $ -Définie en utilisant un terme de Lambda fermé. Pour cela, procédez par induction sur la définition de la fonction récursive générale.

En effet, même si vous ne visez pas les termes fermés, dans cet exercice de programmation, vous obtiendrez une voie fermée de manière naturelle. Après tout, lorsque la programmation on n'a jamais besoin d'une variable qui n'a pas été déclarée au préalable.

Comme les fonctions récursives générales sont exactement celles qui peuvent être calculées par une machine Turing, nous obtenons une complétude pour le calcul de la Lambda fermé.