La maqina de turing

Maquina de Turing

Historia de la máquina de Turing:

Alan Mathison Turing (1912–1954) fue un hombre extremadamente talentoso, que tuvo influencia en el desarrollo de la informática y proporcionó una formalización del concepto del algoritmo y la computación con su famosa máquina Turing , desempeñando un papel importante en la creación de Computadora moderna. Turing descubrió algo que habría deleitado a Leibniz: descubrió que, en principio, era posible idear una única máquina universal que, por sí sola, pudiera realizar cualquier cálculo posible.

Turing describió por primera vez la máquina Turing en su artículo de 1936 sobre números computables, con una aplicación al problema Entscheidungs .

La máquina Turing es un dispositivo informático idealizado, que consiste en un cabezal de lectura / escritura (o escáner ) con una cinta de papel que lo atraviesa. La cinta se divide en cuadrados, cada cuadrado con un solo símbolo ( 0 o 1 , por ejemplo). Esta cinta es el medio de almacenamiento de propósito general de la máquina, que sirve tanto como vehículo para la entrada y salida como una memoria de trabajo para almacenar los resultados de los pasos intermedios de la computación. En el artículo original de 1936, Turing en realidad no imagina una máquina mecánica, sino una persona a la que llama la computadora , que ejecuta estas reglas mecánicas deterministas de una manera descuidada .

La entrada que está inscrita en la cinta antes de que comience el cálculo debe consistir en un número finito de símbolos. Sin embargo, la cinta tiene una longitud ilimitada, ya que el objetivo de Turing era mostrar que hay tareas que estas máquinas no pueden realizar, incluso con memoria de trabajo ilimitada y tiempo ilimitado. El cabezal de lectura / escritura es programable. Para calcular con el dispositivo, debe programarlo, inscribir la entrada en la cinta, colocar la cabeza sobre el cuadrado que contiene el símbolo de entrada más a la izquierda y poner la máquina en movimiento. Una vez que se completa el cálculo, la máquina se detendrá con la cabeza colocada sobre el cuadrado que contiene el símbolo más a la izquierda de la salida (o en otro lugar si está programado).

La máquina Turing puede realizar seis tipos de operaciones fundamentales: leer, escribir, moverse hacia la izquierda, moverse hacia la derecha, cambiar de estado y detenerse. Un cálculo complicado puede consistir en cientos de miles, o incluso millones de tales operaciones. A pesar de la simplicidad de la máquina Turing, es capaz de calcular cualquier cosa que cualquier computadora moderna pueda calcular.

Turing dio una breve definición del experimento mental en su ensayo de 1948, Intelligent Machinery . Refiriéndose a su publicación de 1936, escribe que la máquina de Turing, llamada aquí Máquina de computación lógica , consistía en:
... una capacidad de memoria infinita obtenida en forma de una cinta infinita marcada en cuadrados en cada uno de los cuales se podría imprimir un símbolo. 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á determinado en parte por ese símbolo, pero los símbolos en la cinta en otro lugar 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 esta una de las operaciones elementales de la máquina. Por lo tanto, cualquier símbolo en la cinta puede eventualmente tener entradas.

En Intelligent Machinery, Turing también afirmó que una máquina de pensar debería tener la mente en blanco de un bebé en lugar de una mente adulta llena de opiniones e ideas. El ensayo contenía una discusión temprana de redes neuronales. calculó que tomaría una batería de programadores 50 años llevar esta máquina de aprendizaje desde la madurez mental de la infancia hasta la de adultos.

En 1950, Turing publicó un documento seminal sobre el tema de la inteligencia artificial: Maquinaria de computación e inteligencia , en el que describió la "Prueba de Turing" para determinar si una máquina es "inteligente".

La mayor contribución de Turing al desarrollo de la computadora digital es:
   1. La idea de controlar la función de una máquina informática almacenando un programa de instrucciones codificadas simbólica o numéricamente en la memoria de la máquina.
   2. Su prueba de que, por este medio, una sola máquina (una máquina universal) es capaz de realizar todos los cálculos que cualquier otra máquina de Turing puede llevar a cabo. Afirmó: Las computadoras electrónicas están destinadas a llevar a cabo cualquier proceso de regla general que podría haber sido realizado por un operador humano que trabaja de manera disciplinada pero no inteligente .

Turing era homosexual, y esto resultó en un enjuiciamiento penal en 1952 (los actos homosexuales eran ilegales en el Reino Unido en ese momento), y aceptó el tratamiento con hormonas femeninas (castración química), como alternativa a la prisión. Murió en 1954, varias semanas antes de cumplir 42 años, de un envenenamiento por cianuro aparentemente autoadministrado. El 10 de septiembre de 2009, luego de una campaña en Internet, el primer ministro británico, Gordon Brown, hizo una disculpa pública oficial en nombre del gobierno británico por la forma en que Turing fue tratado después de la guerra.

Características de la máquina de Turing:

La máquina de Turing modela matemáticamente una máquina que opera mecánicamente en una cinta. En esta cinta hay símbolos, que la máquina puede leer y escribir, uno a la vez, usando un cabezal de cinta. La operación está totalmente determinada por un conjunto finito de instrucciones elementales como "en el estado 42, si el símbolo visto es 0, escriba un 1; si el símbolo visto es 1, cambie al estado 17; en el estado 17, si el símbolo visto es 0, escribe un 1 y cambia al estado 6; " etc. En el artículo original (" Sobre números computables, con una aplicación al problema Entscheidungs ", ver también las referencias a continuación ), Turing no imagina un mecanismo, sino una persona a la que llama la "computadora", que ejecuta servilmente estas reglas mecánicas deterministas. (o como dice Turing, "de una manera desganada").

La cabeza siempre está sobre un cuadrado particular de la cinta; solo se muestra un tramo finito de cuadrados. La instrucción a realizar (q 4 ) se muestra sobre el cuadrado escaneado. (Dibujo según Kleene (1952) p. 375.)

Aquí, el estado interno (q 1 ) se muestra dentro de la cabeza, y la ilustración describe la cinta como infinita y precargada con "0", el símbolo en blanco. El estado completo del sistema (su "configuración completa") consiste en el estado interno, cualquier símbolo que no esté en blanco en la cinta (en esta ilustración "11B") y la posición del cabezal con respecto a esos símbolos, incluidos los espacios en blanco, es decir, "011B ". (Dibujo según Minsky (1967) p. 121.)

Una máquina de Turing consiste en:

• Una cinta dividida en celdas, una al lado de la otra. Cada celda contiene un símbolo de un alfabeto finito. El alfabeto contiene un símbolo especial en blanco (aquí escrito como '0') y uno o más símbolos. Se supone que la cinta se puede extender arbitrariamente hacia la izquierda y hacia la derecha, de modo que la máquina Turing siempre se suministra con tanta cinta como sea necesaria para su cálculo. Se supone que las celdas que no se han escrito antes se rellenan con el símbolo en blanco. En algunos modelos, la cinta tiene un extremo izquierdo marcado con un símbolo especial; la cinta se extiende o es indefinidamente extensible a la derecha.
• Un cabezal que puede leer y escribir símbolos en la cinta y mover la cinta de izquierda a derecha (y solo una) celda a la vez. En algunos modelos, la cabeza se mueve y la cinta está parada.
• Un registro de estado que almacena el estado de la máquina Turing, uno de finitos. Entre estos se encuentra el estado de inicio especial con el que se inicializa el registro de estado. Estos estados, escribe Turing, reemplazan el "estado mental" en el que normalmente estaría una persona que realiza los cálculos.
• Una tabla finita [19] de instrucciones [20] que, dado el estado (q i ) en el que se encuentra actualmente la máquina y el símbolo (a j ) que está leyendo en la cinta (símbolo actualmente debajo de la cabeza), le dice a la máquina que haga lo siguiente en secuencia (para los modelos de 5 tuplas):

1. Borre o escriba un símbolo (reemplazando una j por una j1 ).
2. Mueva la cabeza (que se describe por d k y puede tener valores: 'L' para un paso a la izquierda o 'R' para un paso a la derecha o 'N' para permanecer en el mismo lugar).
3. Asuma el mismo estado o uno nuevo según lo prescrito (vaya al estado q i1 ).

En los modelos de 4 tuplas, borrar o escribir un símbolo (a j1 ) y mover la cabeza hacia la izquierda o hacia la derecha (d k ) se especifican como instrucciones separadas. La tabla le dice a la máquina que (ia) borre o escriba un símbolo o (ib) mueva la cabeza hacia la izquierda o hacia la derecha, y luego (ii) asuma el mismo estado o uno nuevo según lo prescrito, pero no ambas acciones (ia) e (ib ) en la misma instrucción. En algunos modelos, si no hay una entrada en la tabla para la combinación actual de símbolo y estado, la máquina se detendrá; otros modelos requieren que se completen todas las entradas.

...