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

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 podría ser un símbolo impreso. En cualquier momento hay un símbolo en la máquina; se llama el símbolo escaneado. La máquina puede alterar el símbolo escaneado y su comportamiento está en parte determinado por ese símbolo , pero los símbolos en la cinta en otros lugares no afectan el comportamiento de la máquina . Sin embargo, la cinta se puede mover hacia adelante y hacia atrás a través de la máquina, siendo una de las operaciones elementales de la máquina. Cualquier símbolo en la cinta puede por lo tanto, finalmente tiene una posibilidad. (Turing 1948, p.161)

Si desea asignar estas operaciones a las realizadas en un procesador capaz de interpretar las instrucciones ensambladoras/binarias, ¿qué operaciones se mapearían?

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

Answer 1

leer lo que has escrito yo diría que sólo necesita:

• Un 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 de la corriente valor de posición de la cinta

En un conjunto de brazo-como, por ejemplo, si usted tiene R0 que contiene la dirección de la cinta se debe sólo tiene

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 se puede imprimir un símbolo.

Llamemos a una matriz int. int[] Symbols

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

int inxSym; 
int scannedSymbol = Symbols[inxSym]; 

(A nivel de la 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 "la ejecución de una instrucción". No hay un código de operación para decirle que lo haga; es solo lo que hace la CPU.)

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

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, esto es manejar con los códigos op JMP)

Answer 3

Puesto que 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

Permite llamar a los estados Qn , los personajes Alfabet Ai leen de la cinta. La máquina determina el siguiente estado de la una tabla transisiton 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 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 

un ingenio 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 es interpretada 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 este Maps en una búsqueda en una matriz 2D para leer el triplete.Cambia el estado con los # bits del personaje en la cinta y pégalos juntos. Multiplique (ok, otra operación de cambio) para dejar espacio para el triplete y utilícelo como el desplazamiento en una tabla para leer el triplete.

Escriba el nuevo estado en el registro de estado, el carácter en la cinta, y el decremento de inc, si encuentra datos en el triplete, o de no hay datos allí. Debería ser divertido en el montaje.

Answer 4

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

• cabezal de la máquina de Turing (el que "escanea" un símbolo en un momento dado) serían equivalente con el Puntero de Instrucción.
• Las fases de captación de instrucción y decodificación son, por lo tanto, equivalentes con una interpretación del símbolo escaneado.
• La ejecución se representaría como una secuencia más compleja de operaciones de TM. Tomemos una escritura de memoria, por ejemplo: mueva la cabeza a una ubicación de memoria determinada, mueva los datos de los registros a la ubicación, regrese a la ubicación dirigida por el registro de IP e increméntela.

Tenga en cuenta que el control del movimiento de la cabeza es equivalente a las instrucciones de control de flujo, es decir, JMP y sus hermanos.

También tenga en cuenta que los registros son una adición importante a la TM clásica. Podrían representarse como celdas especiales (o conjuntos de celdas) en la cinta o como entidades separadas. Vea el register machine para más detalles.

Finalmente, es importante mencionar que si bien esto funciona perfectamente para la arquitectura de Von Neumann, la arquitectura de Harvard utiliza dos cintas distintas, una para las instrucciones y otra para los datos.