Il calcolo di Lambda senza variabili libere è forte come il calcolo della Lambda?

Question

PRIMA DOMANDA: Come si può dimostrare che rimuovendo le variabili GRATUITAMENTE (nessuna undatura) dal calcolo della Lambda, e consentendo solo variabili rilegate, la sua potenza non è ridotta (è ancora in Turing-Complete)?

Seconda domanda: la proposta è stata sopra davvero vera?La Lambda Calculus sans è davvero le variabili gratuite di Turing-complete?

Answer 1

Suppongo che ti riferisca al calcolo Lambda non aderente.

In caso affermativo, scrivi $ \ newcommand {\ num} [1] {\ ulcorner # 1 \ urcorner} \ num {n} $ per il numero della Chiesa di The Natural Unmber $ n $ .

è noto che esiste un termine chiuso (cioè, senza variabili liberi) $ tm $ tale $$ Tm \ \ num {i} \ \ num {n} \= _ {\ beta \ eta} \ \ num {m} $$ Se, e solo se, la classe $ I $ -th turing macchina (in alcune enumerazione standard) eseguire con ingresso $ n \ in \ MathBB N $ (codificato come al solito) fermi di ritorno $ m $ come output.

Infatti, scrittura $ TM $ è un esperto di "programmazione" standard nel calcolo della lambda. Per questo, si può rappresentare il nastro come una coppia o-paia-di paia-di ... (alias A contro elenco) dei simboli. Quindi una subroutine "stepping" per far avanzare il nastro e lo stato TM può essere scritto. Infine, la subroutine passo-passo viene richiamata fino al raggiungimento di uno stato di blocco. Quest'ultimo passaggio può essere ottenuto utilizzando un combinatore di punti fissi come $ y $ .

Poiché possiamo simulare qualsiasi macchina di tentazione, otteniamo la completezza.

---

.

Prova alternativa, che è (a mio avviso) più facile da eseguire in modo effettivamente dettagliato: dimostrare che qualsiasi funzione di ricorsività generale può essere $ \ Lambda $ -Defined usando un termine chiuso lambda. Per questo, procedere per induzione sulla definizione della funzione di ricorsivo generale.

In effetti, anche se non si mira a termini chiusi, in questo esercizio di programmazione otterrai uno chiuso in modo naturale. Dopotutto, quando la programmazione non ha mai bisogno di una variabile che non è stata dichiarata in anticipo.

Poiché le funzioni di ricorsività generali sono esattamente quelle che possono essere calcolate da una macchina di Turing, otteniamo la completezza per il calcolo Lambda chiuso.