Quali sarebbero gli equivalenti in linguaggio assembly delle operazioni sulla macchina di Turing originale?

Question

Se si prende la definizione originale macchina di Turing come segue:

... una capacità di memoria infinita ottenuto sotto forma di un nastro infinito segnato a quadrati, su ciascuno dei quali un simbolo potrebbe essere stampato. in qualsiasi momento c'è un simbolo nella macchina; è chiamato il simbolo scansionato. La macchina può modificare il simbolo scansionato e il suo comportamento è in parte determinato dal simbolo , ma i simboli sul nastro altrove non influiscono sul comportamento della macchina . Tuttavia, il nastro può essere spostato avanti e indietro attraverso la macchina, ovvero una delle operazioni elementari della macchina. Qualsiasi simbolo sul nastro può alla fine avere un inning. (Turing 1948, p 61.)

Se si desidera mappare queste operazioni a quelli fatti su un processore in grado di interpretare assembler/istruzioni binarie - che le operazioni sarebbero mappati?

(Sono consapevole del salto da macchine di Turing alle macchine Von Neuman insiti in questa domanda)

Answer 1

leggere quello che hai scritto direi che basta:

• A istruzione di incremento diretto (da aggiungere alla posizione corrente del nastro)
• Un'istruzione di incremento indiretto (per spostare il nastro)
• Qualcosa di agire in risposta del nastro corrente valore di posizione

In un'assemblea ARM-come, per esempio, se si dispone di R0 contenente l'indirizzo sul nastro si deve solo bisogno di

ADDS r0, r0, #1 ;moves the tape forward 
ADDS r0, r0, #-1 ;moves the tape backwards 
ADDS [r0], [r0], #1 ;increments the value 'pointed by' the tape 
ADDS [r0], [r0], #-1 ;decrements the value 'pointed by' the tape 

poi, rami per fare cose in caso di certi valori assunti dal simbolo corrente

BEQ Somewhere 

Questo è più o meno come funziona Brainfuck.

Answer 2

una capacità di memoria infinita ottenuto sotto forma di un nastro infinito delimitato in quadrati, sulla ognuno dei quali può essere stampato un simbolo.

Chiamiamo un array int. int[] Symbols

In ogni momento v'è un simbolo nella macchina; è chiamato il simbolo scansionato.

int inxSym; 
int scannedSymbol = Symbols[inxSym]; 

(A livello di CPU, questo è noto come "memoria principale" o in sistema moderno "segmento di programma".

La macchina può alterare il simbolo digitalizzato

Symbols[inxSym] = newSymbol; 

e il suo comportamento è in parte determinata da detto simbolo,

switch(scannedSymbol) {....} 

(A livello CPU, questo è "esecuzione di un'istruzione". Non esiste un codice operativo per dirlo di farlo; è solo ciò che fa la CPU.)

ma i simboli sul nastro altrove non influenzano il comportamento della macchina.

Niente da fare.

Tuttavia, il nastro può essere spostato avanti e indietro attraverso la macchina, essendo questa una delle operazioni elementari della macchina.

++inxSym; 
    --inxSym 
    inxSym +=10; 
// etc. 

(A livello di CPU, questo è gestire con i codici op JMP)

Answer 3

Dal momento che la macchina di Turing è completamente determinato dalla definizione del Alfabet sul nastro e la macchina dello stato, che sta leggendo il nastro renderebbe più senso per rendere il linguaggio come un tavolo

consente di chiamare gli stati Qn , i personaggi di Alfabet Ai leggono dal nastro. La macchina determina lo stato successivo dalla un tavolo transisiton e scrive Ao al nastro e si muove nella direzione D: L/R

La macchina può quindi essere definito scrivendo il

QnAi -> QmAoD

il programma di aggiungere da wikipedia sarebbe poi diventato

QbA0 -> QbA1R 
QbA1 -> QbA1R 
Q0A- -> Q0A-L 
Q1A0 -> QrA-L 
Q1A1 -> QaA-L 
Q1A- -> QrA-L 

uno spirito dello stato accettare e r lo stato rifiutare. Questo è abbastanza compatto e una presentazione leggibile della matrice di transizioni.

Questo naturalmente presuppone che ciò che è presente sul nastro sia interpretato come dati. Ma nulla impedisce a chiunque di creare la matrice di transizione per far sì che la statemachine interpreti le istruzioni dal nastro.

Per implementare questo si ha sul lato sinistro una tupla e sul lato destro una tripla, quindi questa mappa su una ricerca in una matrice 2D per leggere la terzina.Sposta lo stato con i #bit del carattere sul nastro e incollali insieme. Moltiplicare (ok, un'altra operazione di cambio) per fare spazio alla terzina e usarla come offset in una tabella per leggere la tripletta.

Scrivere il nuovo stato nel registro di stato, il carattere sul nastro e il decremento, se si trovano i dati nella terzina o l'interruzione di non ci sono dati lì. Dovrebbe essere divertente in assemblea.

Answer 4

io non sono sicuro se questo è corretta al 100%, ma sarebbe più o meno così:

• la testa della macchina di Turing (quello che "scansiona" un simbolo in un dato momento) sarebbero equivalente con il puntatore di istruzioni.
• Le fasi di recupero e decodifica sono quindi equivalenti all'interpretazione del simbolo scansionato.
• L'esecuzione sarebbe rappresentata come una sequenza più complessa di operazioni TM. Prendiamo ad esempio una scrittura in memoria: spostate la testa in una determinata posizione di memoria, spostate i dati dai registri nella posizione, tornate nella posizione indicata dal registro IP e incrementatela.

Si noti che il controllo del movimento della testa è equivalente alle istruzioni di controllo del flusso, ad esempio JMP e i suoi fratelli.

Si noti inoltre che i registri sono un'importante aggiunta alla TM classica. Potrebbero essere rappresentati come celle speciali (o gruppi di celle) sul nastro o come entità separate. Vedi lo register machine per maggiori dettagli.

Infine, è importante menzionare che mentre questo funziona perfettamente per l'architettura Von Neumann, l'architettura di Harvard utilizza due nastri distinti, uno per le istruzioni e uno per i dati.