Completezza di lambda del calcolo lambda?

Question

Come si sostiene il fatto che il calcolo lambda è completo di Turing (nel modo più semplice possibile)?

Answer 1

Il modo più semplice è quello di implementare una macchina di turing nel calcolo Lambda. Questo è abbastanza facile, perché il Lambda Calculus è praticamente un linguaggio di programmazione di alto livello. Questo approccio ha il vantaggio di non richiedere altre dipendenze matematiche e dovrebbe quindi fornire il modo più semplice di fornire la tua argomentazione.

In termini di una dimostrazione matematica, la via più breve passa implementando un altro paradigma che è già stato dimostrato essere completo di Turing, come le funzioni μ-ricorsive. Questi sono già definiti in modo ricorsivo, quindi la loro espressione nel calcolo Lambda è leggermente più elegante della Macchina di Turing stessa.

Answer 2

Brainfuck è un linguaggio che i modelli molto da vicino Turing Macchine, e si può trovare un interprete lambda calcolo precisato al http://en.wikipedia.org/wiki/Binary_lambda_calculus#Brainfuck