My simple turing machine

Question

Sto cercando di capire e implementare la macchina turing più semplice e vorrei un feedback se ho un senso.

Abbiamo un nastro infinito (diciamo un array di nome T con puntatore a 0 alla partenza) e la tabella di istruzioni:

(S , R , W , D , N) 

S->STEP (Start at step 1) 
R->READ (0 or 1) 
W->WRITE (0 or 1) 
D->DIRECTION (0=LEFT 1=RIGHT) 
N->NEXTSTEP (Non existing step is HALT) 

mia comprensione è che a 3 Stato 2-simbolo è la macchina più semplice . 3-state non capisco. 2-symbol perché usiamo 0 e 1 per READ/WRITE.

Ad esempio:

(1,0,1,1,2) 
(1,1,0,1,2) 

partendo dal punto 1, se letto è 0 allora {Scrivere 1, Sposta a destra) else {Scrivere 0, Sposta a destra) e poi passare al punto 2 - che non esiste che interrompe il programma.

Che cosa significa lo stato 3? Questa macchina passa come turing machine? Possiamo semplificare di più?

Answer 1

Credo che il concetto di stato sia sostanzialmente lo stesso di Finite State Machines. Se ricordo, è necessario uno stato di terminazione separato, a cui la macchina di turazione può transitare dopo aver terminato l'esecuzione del programma. Per quanto riguarda il motivo per cui 3 stati direi che gli altri due stati sono rispettivamente per l'intializzazione e l'esecuzione.

Sfortunatamente niente di tutto ciò è garantito per essere corretto, ma ho pensato di postare comunque i miei pensieri poiché la domanda era senza risposta per 5 ore. Sospetto che se dovessi riproporre questa domanda su cstheory.stackexchange.com potresti ottenere una risposta migliore/più definitiva.

Answer 2

"Stato" nel contesto delle macchine di Turing dovrebbe essere chiarito a quale viene descritto: (i) l'istruzione corrente, o (ii) l'elenco di simboli sul nastro insieme con l'istruzione corrente, o (iii)) l'elenco dei simboli sul nastro insieme con l'istruzione corrente posizionata a sinistra del simbolo scansionato o alla destra del simbolo scansionato. Reference

Answer 3

Penso che la confusione potrebbe venire dal tuo uso di "passaggi" anziché di "stati". Puoi considerare lo stato di una macchina come il valore che ha nella sua memoria (anche se, come notato da un poster precedente, alcune persone prendono anche lo stato di una macchina per includere il contenuto del nastro - tuttavia, non credo che la definizione sia pertinente alla tua domanda). È possibile che questo cambiamento di terminologia possa essere al centro della tua confusione. Lascia che ti spieghi cosa penso che stia pensando. :)

Hai fornito elenchi di cinque numeri, ad esempio (1,0,1,1,2). Come si afferma correttamente, questo dovrebbe essere interpretato (leggendo da sinistra a destra) come "Se la macchina è nello stato 1 E il quadrato corrente contiene uno 0, stampa un 1, vai a destra e passa allo stato 2." Tuttavia, l'uso della parola "step" sembra suggerire che quel "passo 2" deve essere seguito da "step 3", ecc., Quando in realtà una macchina di Turing può andare avanti e indietro tra stati (e ovviamente, lì può essere solo un numero finito di stati possibili).

Quindi, per rispondere alle vostre domande:

• macchine di Turing tenere traccia di "afferma" non "passi";
• Quello che hai descritto è una macchina di Turing legittima;
• Una macchina di turing più semplice (anche se non interessante) sarebbe quella che inizia nello stato HALT.

Modifiche: grammatica, formattazione e rimozione di una descrizione superflua delle macchine di Turing.

risposta al commento: correggermi se sto interpretando male il tuo commento, ma io non intendo suggerire una macchina di Turing potrebbe essere in più di uno stato alla volta, solo che il numero di possibili stati possono essere un numero finito Ad esempio, per una macchina a 3 stati, potresti etichettare i possibili stati A, B e C. (nell'esempio che hai fornito, hai etichettato i due stati possibili come "1" e "2") In qualsiasi momento, esattamente uno di quei valori (stati) sarebbe nella memoria della macchina. Diciamo "la macchina è nello stato A" o "la macchina è nello stato B", ecc. (La macchina inizia nello stato "1" e termina dopo essere entrata nello stato "2").

Inoltre, non è più chiaro per me cosa intendi con una macchina "più semplice/est". La più piccola Universal Turing (cioè una macchina di Turing in grado di simulare un'altra macchina di Turing, dato un nastro appropriato) richiede 2 stati e 5 simboli (vedere the relevant Wikipedia article).

D'altra parte, se si sta cercando qualcosa di più semplice di una macchina di Turing con la stessa potenza di calcolo, Post-Turing machines potrebbe essere di interesse.