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.

Relacionado

¿Quién es Fujio Masuoka? El creador de las memorias flash

Hoy vamos a conocer a un personaje muy importante dentro de la historia de las computadoras, el creador de las memorias Flash: Fujio Masuoka. Biografía Completa de Fujio Masuoka Fujio Masuoka, ingeniero japonés nacido el 8 de mayo de 1943, que trabajó para Toshiba y en ¡SEGUIR LEYENDO!

Identificador de objeto digital (DOI) y Crossmark – Guía del investigador

Esta guía se centra en informar sobre que es "Crossmarks e Digital Object Identifier (DOI)" en español, identificador de objeto digital. El DOI es uno de los elementos esenciales en un trabajo de investigación. ¿Qué es el identificador de objeto digital o DOI? El DOI es ¡SEGUIR LEYENDO!

Sociedad e Internet

Lo que comenzó como un universo en gran medida técnico y limitado de diseñadores y usuarios se convirtió en uno de los medios más importantes de finales del siglo XX y principios del XXI. Como observó Pew Charitable Trust en 2004, tomó 46 años cablear el ¡SEGUIR LEYENDO!

¿Qué es la prueba de Turing y por qué es importante para la IA?

Si has estado alrededor de la Inteligencia Artificial (IA) sin duda has oído hablar de la prueba de Turing. Esta prueba fue propuesta por primera vez por Alan Turing en 1950 y se diseño para ser el último experimento sobre si una IA es capaz de ¡SEGUIR LEYENDO!

Explicación del motor analítico de Charles Babbage: Todo lo que necesita saber

Creado por Charles Babbage, el motor analítico era una computadora digital mecánica de propósito general, completamente controlada por programa, sin intervención humana. Fue diseñado para ser programado mediante tarjetas perforadas, algo que fue una de sus características más rompedoras. El motor analítico estaba destinado a ser ¡SEGUIR LEYENDO!