Come enumerare tutte le macchine Turing?

Question

Perché è vero: "Làsono connobilmente molte macchine Turing "

Nella risposta migliore per questa domanda è data una descrizione di come enumerare tutte le macchine Turing.

Tutto è chiaro tranne che per una parte: come fai a sapere se una stringa è una codifica valida di una macchina di Turing?Nel passaggio 3 L'algoritmo deve controllare se una stringa è una codifica valida di una macchina di Turing.Com'è fatto?

Answer 1

Una macchina di Turing ha una rappresentazione come una stringa.Più specificamente, scrivi la funzione di transizione .Per fare questo, semplicemente pensarlo come un grande tavolo, avendo in ogni riga due afferma una lettera e una transizione testa (L per sinistra o r per destra).

Ora, codifica ogni voce della tabella delle funzioni di transizione e lo spazio tra di loro con 3 zeri (è come un "numero magico", quindi sapremmo dove iniziano e finiscono le voci).Ogni voce conterrà due numeri: ogni numero che rappresenta uno stato, un altro bit per la lettera e un altro bit per la transizione della testa (dire 1 sarebbe r e 0 è l).

Tra i due numeri e gli altri bit metti altri 2 zeri, solo così saresti in grado di distinguere tra loro.

Ora, per enumerare su tutte le macchine di Turing, semplicemente enumerare su tutte le stringhe e controllare se sono nel formato sopra descritto