Máquinas O de Turing

Las máquinas O son un tipo de máquina abstracta. Generan una salida digital a partir de una entrada digital por medio de un procedimiento paso a paso que consiste en aplicaciones repetidas de un número pequeño y fijo de operaciones atómicas.

El procedimiento se desarrolla bajo el control de un programa finito de instrucciones que (como ocurre con la máquina universal de Turing se almacena en forma de datos en la cinta de la máquina.

Turing introdujo el concepto de máquina O en su tesis doctoral (la tesis que fue supervisada por Alonzo Church).

La Tesis de Turing-Church

Esto se publicó posteriormente como ‘Systems of Logic Based on Ordinals’, Proceedings of the London Mathematical Society, serie 2, vol. 45 (1939): 161-228. Este artículo es ahora un clásico de la teoría de funciones recursivas.

Las operaciones atómicas de una máquina de Turing son seis:

  1. Mover la cinta un cuadrado hacia la izquierda
  2. Mover la cinta un cuadrado a la derecha
  3. Leer (es decir, identificar) el símbolo actualmente debajo del encabezado
  4. Escribir un símbolo en el cuadrado de cinta actualmente debajo del encabezado (después de borrar primero el símbolo ya escrito allí, si lo hay)
  5. Cambiar de estado
  6. Detenerse

Estas operaciones primitivas están disponibles mediante subdispositivos no especificados de la máquina – ‘cajas negras’. Una máquina O es una máquina de Turing aumentada con una o más operaciones atómicas, cada una de las cuales devuelve los valores de alguna función (sobre los números naturales) que *no es *una máquina de Turing computable.

Cada operación atómica adicional está disponible mediante una caja negra. Turing se refiere a estas cajas negras como ‘oráculos’. Él comenta que un oráculo funciona por ‘medios no especificados’ y dice que ‘no necesitamos profundizar más en la naturaleza de estos oráculos’.

¿Qué es una máquina de Turing?

Cada oráculo devuelve los valores de una función de dos valores. Deje que estos valores se escriban 0 y 1. Sea p una de las operaciones primitivas adicionales. p es llamado a la acción por medio de un estado especial c, el estado de llamada.

(Donde una máquina O tiene varias de estas primitivas adicionales, se requiere un número correspondiente de estados de llamada).

La máquina inscribe los símbolos que formarán la entrada de p en cualquier bloque de cuadrados conveniente de su cinta, usando ocurrencias de un símbolo especial µ, el símbolo de marcador, para indicar el comienzo y el final de la cadena de entrada.

Tan pronto como una instrucción en el programa de la máquina pone a la máquina en el estado c, la entrada se entrega al subdispositivo que efectúa p, que luego devuelve el valor correspondiente de la función.

¿Quién es Alan Turing?

El subdispositivo que afecta p podría simplemente escribir este valor en la cinta.

En la forma de manejar los asuntos de Turing, el valor no está escrito en la cinta; más bien se emplea un par de estados, el estado 1 y el estado 0, para registrar los valores de la función.

Una llamada a p termina con un subdispositivo que coloca la máquina en uno u otro de estos dos estados según el valor de la función sea 1 o 0.

Cuando una función g es computable por una máquina-O cuyo (único) oráculo sirve para devolver los valores de una función f, entonces se dice que g es computable en relación con f.

Una máquina O en particular, la máquina con función de parada, tiene como parte “clásica” la máquina universal de Turing especificada por Turing en su artículo de 1936 (“Sobre números computables, con una aplicación al problema Entscheidung”) y como su parte “no clásica” part una operación primitiva que devuelve los valores de la función de detención H(x,y).

La función de detención se define así:

  • H(x,y)=1 si y solo si la máquina de Turing x finalmente se detiene si se pone en movimiento con el número entero y inscrito en su cinta, digamos en código binario (piense en y como la entrada de la máquina)
  • H(x,y)=0 en caso contrario.

La máquina de función de parada puede calcular muchas funciones que no son computables por la máquina de Turing. Esto se debe al conocido fenómeno de la reducibilidad de una función a otras (en el sentido de que la multiplicación es reducible a la suma, por ejemplo).

Todas las funciones reducibles a la función de parada y/o las operaciones atómicas de una máquina de Turing ordinaria son computables por la máquina de función de parada.

Relacionados