Turing Tabella Macchina di istruzioni

Question

Le definizioni di Macchina di Turing dicono che è vietato per una lettura / modifica è tabella di istruzioni (programma). Esattamente, Macchina di Turing non ha accesso a un proprio programma.

Quali benefici possono essere raggiunti se si potesse indebolire questa restrizione? Se una macchina potrebbe analizzare con e / o modificare il suo programma. Vorrei che estendere la classe di compiti di Turing-calcolabile?

Answer 1

La macchina di Turing può già realizzare un'altra macchina di Turing, e cambiare la sua regole, per esempio, di prendere come input di un programma modificabile. In particolare, la macchina di Turing può calcolare qualsiasi funzione calcolabile. Si potrebbe, in teoria, implementare un interprete Lisp, che avrebbe macro, "auto-Modifing" codice, ecc.

Quindi, la risposta è No . Ricordate, nessuno, e dico assolutamente nessuna persona ovunque, mai, ha in realtà ha voluto una macchina di Turing, anche se non zillions dubbio di simulatori sono stati scritti. (Non voglio ammetterlo, ma come un undergrad io possa aver fatto una cosa del genere ...) E 'solo qualcosa che le varie prove importanti si basano su.

Answer 2

Più completamente: C'è una differenza tra una "macchina di Turing universale" e una Macchina "di Turing '' Un normale Macchina di Turing ha un set di regole cablato, quindi non può essere auto-modificante quello che hai descritto è un universale.. macchina di Turing, che legge il suo set di regole fuori dello stesso nastro che utilizza per l'I / O, e ha la capacità di modificare quel set di regole. Se l'UTM è in grado di ricaricare (riavvio) che ha modificato set di regole dal nastro, allora è in infatti già auto-modifica.