¿Cuáles serían las equivalentes en lenguaje ensamblador de las operaciones en la máquina original de Turing ser?

Question

Si se toma la definición original máquina de Turing de la siguiente manera:

  

... una capacidad de memoria infinita   obtenido en forma de un infinito   cinta de marcado       en cuadrados, en cada uno de los cuales se podría imprimir un símbolo. En cualquier momento   Ahi esta       un símbolo en la máquina; se le llama el símbolo leído. La máquina   puede alterar       el símbolo escaneado y su comportamiento está en parte determinada por la   símbolo, pero el       símbolos en la cinta en otro lugar no afectan el comportamiento de la   máquina. Sin embargo,       la cinta se puede mover hacia atrás y adelante a través de la máquina, siendo esta   uno de los       operaciones elementales de la máquina. Cualquier símbolo en la cinta puede   por lo tanto       llegar a tener una posibilidad. (Turing 1948, p. 61)

Si desea asignar estas operaciones a las que se realizan en un procesador capaz de interpretar ensamblador / instrucciones binarias - ¿qué operaciones se asignan

(soy consciente del salto de las máquinas de Turing a las máquinas de Von Neuman inherentes a esta pregunta)

Answer 1

Lectura lo que has escrito yo diría que sólo tiene:

• Una instrucción de incremento directo (a añadir a la ubicación actual de la cinta)
• una instrucción de incremento indirecto (para mover la cinta)
• Algo para actuar en respuesta del valor de la ubicación actual de la cinta

En un ARM-como el montaje, por ejemplo, si usted tiene R0 que contiene la dirección de la cinta se debe sólo necesita

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

A continuación, las ramas para hacer cosas en el caso de ciertos valores asumidos por el símbolo actual

BEQ Somewhere

Esto es más o menos cómo funciona Brainfuck.

Answer 2

  

    

una capacidad de memoria infinita obtenido en la forma de una cinta infinita marcado en cuadrados, en cada uno de los cuales un símbolo puede ser impreso.

  

Vamos llamada que una matriz int. int[] Symbols

  

    

En cualquier momento hay un símbolo en la máquina; se le llama el símbolo leído.

  

int inxSym;
int scannedSymbol = Symbols[inxSym]; 

(a nivel de CPU, esto se conoce como "memoria principal" o en sistema moderno "segmento de programa".

  

    

La máquina puede alterar el símbolo escaneado

  

Symbols[inxSym] = newSymbol;

  

    

y su comportamiento está en parte determinada por ese símbolo,

  

switch(scannedSymbol) {....}

(A nivel de la CPU, esto es "capaz de ejecutar una instrucción" No hay código de operación para indicarle que debe hacerlo;.. Es sólo lo hacen CPU)

  

    

pero los símbolos en la cinta en otra parte no afectan el comportamiento de la máquina.

  

No hay nada que hacer allí.

  

    

Sin embargo, la cinta se puede mover hacia atrás y adelante a través de la máquina, siendo esta una de las operaciones elementales de la máquina.

  

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

(A nivel de la CPU, se trata de mango con códigos op JMP)

Answer 3

No estoy seguro si esto es 100% correcto soy, pero sería algo parecido a esto:

• La cabeza de la máquina de Turing (el que "escanea" un símbolo en un momento dado) serían equivalentes con el puntero de instrucción.
• La extracción de instrucción y las fases Decodificar son, por tanto, equivalente con una interpretación del símbolo escaneada.
• Ejecución estaría representada como una secuencia más compleja de las operaciones de TM. Vamos a tomar una escritura de memoria, por ejemplo: mover la cabeza a una posición de memoria dada, al mover los datos de los registros de la ubicación, volver a la posición direccionada por el IP registrarse y se incrementará
.

Nota que el control de movimiento de la cabeza es equivalente a fluir instrucciones de control, es decir, JMP y sus hermanos.

También tenga en cuenta que los registros son una importante adición a la TM clásica. Ellos podrían ser representados como células especiales (o conjuntos de células) en la cinta o como entidades separadas. Ver el registrar máquinas para más detalles.

Por último, es importante mencionar que si bien esto funciona perfectamente para la arquitectura Von Neumann, la arquitectura Harvard utiliza dos cintas distintas, una para instrucciones y otra para datos.

Answer 4

Desde la máquina de Turing está completamente determinado por la definición del alfabeto en la cinta y la máquina de estado que está leyendo la cinta que tendría más sentido para hacer que el lenguaje como una mesa

Le permite llamar a los estados Qn, los caracteres del alfabeto Ai leer desde la cinta. La máquina determina el siguiente estado de la tabla de transisiton una y escribe Ao a la cinta y se mueve en la dirección D: L / R

La máquina puede entonces ser definida por escrito su

QnAi -> QmAoD

El programa de la adición de Wikipedia se convertiría entonces en

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

ingenio un el estado de aceptación y r el estado rechazar. Esto es bastante compacto y una presentación legible de la matriz transisition.

Por supuesto, esto supone que lo que está en la cinta se interpreta como datos. Pero nada detiene a nadie de crear la matriz de transición para hacer la instrucción StateMachine interprete de la cinta.

Para implementar esta tiene en el lado izquierdo y una tupla en el lado derecho un triple, por lo que esta mapas en una búsqueda en una matriz 2D para leer el triplete. Cambiar el estado con los #bits del personaje en la cinta y les peguen. Multiplicar (ok, otra operación de desplazamiento) para hacer espacio para el triplete, y el uso que, como el desplazamiento en una mesa para leer el triplete.

Escribir nuevo estado en el registro de estado, el carbón en la cinta, y decremento inc, si encuentra datos en el triplete de parada, o de que no hay datos allí. Debe ser divertido en el montaje.