Turing complétude de lambda calcul?

Question

Comment argumentez-vous pour le fait que le lambda-calcul Turing est complet (de la manière la plus simple possible)?

Answer 1

Le moyen le plus simple est de mettre en œuvre une machine de Turing dans le calcul lambda. C'est assez facile, parce que le Lambda Calculus est pratiquement un langage de programmation de haut niveau. Cette approche a l'avantage de ne nécessiter aucune autre dépendance mathématique, et devrait donc fournir le moyen le plus simple possible de fournir votre argument. En termes de preuve mathématique, le plus court chemin consiste à implémenter un autre paradigme qui a déjà été montré comme complet à Turing, comme les fonctions μ-récursives. Ceux-ci sont déjà définis récursivement, de sorte que leur expression dans le calcul lambda est légèrement plus élégante que la machine de Turing elle-même.

Answer 2

Brainfuck est une langue très près les modèles machines de Turing, et vous pouvez trouver un interprète lambda-calcul précisées à http://en.wikipedia.org/wiki/Binary_lambda_calculus#Brainfuck