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

Question

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

  

... una capacità di memoria infinita   ottenuti sotto forma di un infinito   nastro segnata       in quadrati, su ciascuno dei quali un simbolo potrebbe essere stampata. In qualsiasi momento   c'è       un simbolo nella macchina; si chiama il simbolo digitalizzata. La macchina   possono alterare       il simbolo scansionato e il suo comportamento è in parte determinata da quella   simbolo, ma la       simboli sul nastro altrove non influiscono sul comportamento del   macchina. Tuttavia,       il nastro può essere spostato avanti e indietro attraverso la macchina, questo essere   uno di       operazioni elementari della macchina. Qualsiasi simbolo sul nastro può   perciò       alla fine hanno 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 state mappate

(mi rendo conto del salto da macchine di Turing alle macchine Von Neuman insiti in questa domanda)

Answer 1

Leggere quello che hai scritto direi basta:

• Un'istruzione incremento diretta (per aggiungere la posizione corrente del nastro)
• Un'istruzione incremento indiretta (per spostare il nastro)
• Qualcosa di agire in risposta al valore posizione attuale del nastro

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

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, su ciascuno dei quali un simbolo può essere stampato.

  

chiamata di lasciare che un array di int. int[] Symbols

  

    

In ogni momento v'è un simbolo nella macchina; si chiama il simbolo digitalizzata.

  

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 digitalizzata   

Symbols[inxSym] = newSymbol;

  

    

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

  

switch(scannedSymbol) {....}

(A livello di CPU, si tratta di "eseguendo un'istruzione" Non esiste un codice op per dirgli di farlo;.. È proprio quello della CPU fare)

  

    

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, questa è la maniglia con codici operativi JMP)

Answer 3

Non so se questo è corretta al 100% sono, ma sarebbe andare qualcosa come questo:

• Il capo macchina di Turing (quello che "scansiona" un simbolo in un dato momento) sarebbero equivalenti con il puntatore all'istruzione.
• L'Istruzione Fetch e le fasi di decodifica sono quindi equivalenti, con un'interpretazione del simbolo acquisita.
• Esecuzione sarebbe rappresentato come una sequenza di operazioni più complesse TM. Prendiamo una scrittura della memoria, ad esempio: spostare la testa per un determinato luogo di memoria, di spostamento dei dati da registri alla posizione, tornare alla posizione indirizzata da IP registrarsi e incrementarlo
.

Si noti che il controllo dei movimenti della testa è equivalente a scorrere istruzioni di controllo, vale a dire JMP e dei suoi fratelli.

Si noti inoltre che i registri sono un importante aggiunta al TM classica. Essi potrebbero essere rappresentati come cellule speciali (o insiemi di celle) sul nastro o come entità separate. Vedere la registrare la macchina per ulteriori dettagli.

Infine, è importante ricordare che, mentre Questo funziona perfettamente per l'architettura di Von Neumann, l'architettura di Harvard utilizza due nastri distinte, una per le istruzioni e uno per i dati.

Answer 4

Poiché la macchina di Turing è completamente determinato dalla definizione del alfabeto sul nastro e la macchina a stati che sta leggendo il nastro renderebbe più senso per rendere il linguaggio come una tabella

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

La macchina può quindi essere definito scrivendo il suo

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 transisition.

Questo ovviamente presuppone che ciò che è sul nastro viene interpretato come dati. Ma nulla ferma chiunque di creare la matrice di transizione per rendere l'istruzione statemachine Interprete dal nastro.

Per implementare questo avete sul lato sinistro una tupla e sul lato destro una tripla, quindi questo mappe su una ricerca in una matrice 2D di leggere la tripletta. Spostare lo stato con le #bits del carattere sul nastro e stare insieme. Multiply (ok, un'altra operazione di spostamento) per fare spazio per la tripletta, e l'uso che, come l'offset in una tabella per leggere il tripletta.

Scrivi il nuovo stato nel registro di stato, il char sul nastro, e decremento inc, se trovate i dati nella tripletta, o fermata di non ci sono dati lì. Dovrebbe essere divertente in assemblea.