Come si sostiene il fatto che il calcolo lambda è completo di Turing (nel modo più semplice possibile)?Completezza di lambda del calcolo lambda?
risposta
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.
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
Si mostra che tutte le [funzioni u-ricorsiva] (https: //en.wikipedia .org/wiki /% CE% 9C-recursive_function) può essere espresso nel calcolo lambda, quindi fare affidamento sul risultato di completezza di Turing per quelli –