Historia de La Máquina de Turing

               Historia de La Máquina de Turing 

La Máquina de Turing respondía a un intento de alcanzar una solución para uno de los problemas matemáticos más importantes a principios del siglo XX: el Entscheidungsproblem o Problema de Decisión. A pesar del nombre, cuando Alan Turing propuso su máquina en 1936, nunca pensó en una implementación física de la misma.Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo con una tabla de reglas. A pesar de su simplicidad, una máquina de Turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de una CPU dentro de un computador.Inspirada en el modo de proceder de los calculistas humanos,  consistía en una cinta infinita con casillas que podían registrar ceros y unos, y una máquina de estados finitos (o cabezal) que podía avanzar o retroceder sobre la cinta y leer dígitos o escribirlos según el estado en que se encontrara. Inicialmente cada máquina computaba una única función, pero Turing se dio cuenta de que el programa para calcular una función u otra se podía codificar en la misma cinta que los datos de entrada, lo que dio lugar a la Máquina Universal de Turing, modelo teórico del computador digital. Dicha Máquina Universal podía emular cualquier máquina de Turing al recibir como entrada la codificación de una máquina particular al mismo tiempo que los datos. Al almacenar el programa en el mismo formato que los datos, quedaban delimitados los papeles que iban a desempeñar el hardware (de propósito general) y el software (tanto de sistema como de aplicaciones) en la informática actual.

Alan Turing introdujo el concepto de máquina de Turing en el trabajo On computable numbers, with an application to the Entscheidungsproblem, publicado por la Sociedad Matemática de Londres en 1936, en el que se estudiaba la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método definido que pueda aplicarse a cualquier sentencia matemática y que nos diga si esa sentencia es cierta o no. Turing ideó un modelo formal de computador, la máquina de Turing, y demostró que existían problemas que una máquina no podía resolver.[6]​

Con este aparato extremadamente sencillo es posible realizar cualquier cómputo que un computador digital sea capaz de realizar.[7]​

Mediante este modelo teórico y el análisis de la complejidad de los algoritmos, fue posible la categorización de problemas computacionales de acuerdo a su comportamiento, apareciendo así, el conjunto de problemas denominados P y NP, cuyas soluciones pueden encontrarse en tiempo polinómico por máquinas de Turing deterministas y no deterministas, respectivamente.

Precisamente, la tesis de Church-Turing formulada por Alan Turing y Alonzo Church, de forma independiente a mediados del siglo xx caracteriza la noción informal de computabilidad con la computación mediante una máquina de Turing.[8]​

La idea subyacente es el concepto de que una máquina de Turing puede verse como un autómata ejecutando un procedimiento efectivo definido formalmente, donde el espacio de memoria de trabajo es ilimitado, pero en un momento determinado solo una parte finita es accesible.

Descripción informal

                                 Descripción informal 

La máquina de Turing modela matemáticamente a una máquina que opera mecánicamente sobre una cinta. En esta cinta hay símbolos que la máquina puede leer y escribir, uno a la vez, usando un cabezal lector/escritor de cinta. La operación está completamente determinada por un conjunto finito de instrucciones elementales como "en el estado 42, si el símbolo visto es 0, escribe un 1; Si el símbolo visto es 1, cambia 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 Entscheidungsproblem"), Turing no imagina un mecanismo, sino una persona a la que él llama la "computadora", quien ejecuta servilmente estas reglas mecánicas deterministas (o como Turing pone, "de una manera desganada").

Más precisamente, una máquina de Turing consta de:

Una cinta que se divide en celdas, una al lado de la otra. Cada celda contiene un símbolo de algún alfabeto finito. El alfabeto contiene un símbolo especial llamado blanco (aquí escrito como 'B') y uno o más símbolos adicionales. La cinta se supone que es arbitrariamente extensible hacia la izquierda y hacia la derecha, es decir, la máquina de Turing siempre es provista con tanta cinta como necesite para su computación. Las celdas que no se hayan escrito previamente se asumen que están rellenas con el símbolo blanco. En algunos modelos la cinta tiene un extremo izquierdo marcado con un símbolo especial; la cinta se extiende o es indefinidamente extensible hacia la derecha.Un cabezal que puede leer y escribir símbolos en la cinta y mover la cinta a la izquierda y a la derecha una (y solo una) celda a la vez. En algunos modelos el cabezal se mueve y la cinta es estacionaria.Un registro de estado que almacena el estado de la máquina de Turing, uno de los estados finitos. Hay un estado inicial especial con el que el registro de estado se inicia. Turing escribe que estos estados reemplazan el "estado de la mente" en que ordinariamente estaría una persona realizando cálculos.Una tabla finita de instrucciones (llamada ocasionalmente como tabla de acción o función de transición). Las instrucciones son usualmente 5-tuplas: qiaj→qi1aj1dk, (a veces 4-tuplas), que, dado el estado (qi) en que la máquina se encuentra actualmente y el símbolo (aj) que se está leyendo en la cinta (el símbolo actualmente debajo del cabezal) le indica a la máquina hacer lo siguiente en secuencia (para los modelos de 5-tupla):Borra o escribe un símbolo (reemplazando aj con aj1), y entoncesMueve el cabezal (que es descrito por dk y puede tener los valores: 'L' para un paso a la izquierda, o 'R' para un paso a la derecha, o 'N' para permanecer en el mismo lugar) y luegoAsume el mismo o un nuevo estado como prescrito (ve al estado qi1).En los modelos de 4-tupla, son especificadas como instrucciones separadas: borrar o escribir un símbolo (aj1) y mover el cabezal a la izquierda o la derecha (dk). Específicamente, la tabla indica a la máquina: (ia) borrar o escribir un símbolo o (ib) mover el cabezal a la izquierda o a la derecha, y luego (ii) asumir el mismo o un nuevo estado, pero no las dos acciones (ia) y (ib) en la misma instrucción. En algunos modelos, si no hay ninguna entrada en la tabla para la actual combinación de símbolo y estado, la máquina se detendrá; otros modelos requieren que estén llenas todas las entradas.

Note que cada parte de la máquina — su estado y colecciones de símbolos — y sus acciones — imprimir, borrar, movimiento de la cinta — es finito, discreto y distinguible; es la cantidad potencialmente ilimitada de cinta lo que le da una cantidad ilimitada de espacio de almacenamiento.

Definición Formal

                                     Definición Formal

Una máquina de Turing es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma.

Este modelo está formado por un alfabeto de entrada y uno de salida, un símbolo especial llamado blanco (normalmente b, Δ o 0), un conjunto de estados finitos y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe un estado inicial y una cadena de caracteres (la cinta, la cual puede ser infinita) pertenecientes al alfabeto de entrada. La máquina va leyendo una celda de la cinta en cada paso, borrando el símbolo en el que se encuentra posicionado su cabezal y escribiendo un nuevo símbolo perteneciente al alfabeto de salida, para luego desplazar el cabezal a la izquierda o a la derecha (solo una celda a la vez). Esto se repite según se indique en la función de transición, para finalmente detenerse en un estado final o de aceptación, representando así la salida.

Una máquina de Turing con una sola cinta puede definirse como una 7-tupla

M = (Q, Σ, Γ, 8, 6, F, δ),

donde:

• Qes un conjunto finito de estados.

• Σ es un conjunto finito de símbolos distinto del espacio en blanco, denominado alfabeto de máquina o de entrada.

• Γes un conjunto finito de símbolos de cinta, denominado alfabeto de cinta (Σ (Γ).

⚫s EQ es el estado inicial.

• be es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.

• FCQes el conjunto de estados finales de aceptación.

• δ: Q × → Q× × {L, R} es una función parcial denominada función de transición, donde L es un movimiento a la izquierda y R es el movimiento a la derecha. Existe en la literatura un abundante número de definiciones alternativas, pero todas ellas tienen el mismo poder computacional, por ejemplo se puede añadir el símbolo S como símbolo de "no movimiento" en un paso de cómputo.

Funcionamiento De La Máquina De Turing

    Funcionamiento De La Máquina De Turing 

La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:

Mover el cabezal lector/escritor hacia la derecha.

Mover el cabezal lector/escritor hacia la izquierda.

El cómputo se determina a partir de una tabla de estados de la forma:

(estado, valor) → (nuevo estado, nuevo valor, dirección)

Esta tabla toma como parámetros el estado actual de la máquina y el carácter leído de la cinta, dando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a escribir en la cinta.

La memoria es la cinta de la máquina que se divide en espacios de trabajo denominados celdas, donde se pueden escribir y leer símbolos. Inicialmente todas las celdas contienen un símbolo especial denominado "blanco". Las instrucciones que determinan el funcionamiento de la máquina tienen la forma, "si estamos en el estado x leyendo la posición y, donde hay escrito el símbolo z, entonces este símbolo debe ser reemplazado por este otro símbolo, y pasar a leer la celda siguiente, bien a la izquierda o bien a la derecha".

La máquina de Turing puede considerarse como un autómata capaz de reconocer lenguajes formales. En ese sentido, es capaz de reconocer los lenguajes recursivamente enumerables, de acuerdo a la jerarquía de Chomsky. Su potencia es, por tanto, superior a otros tipos de autómatas, como el autómata finito, o el autómata con pila, o igual a otros modelos con la misma potencia computacional.

Representación como diagrama de estados

    Representación como diagrama de estados

Las máquinas de Turing pueden representarse mediante grafos particulares, también llamados diagramas de estados finitos, de la siguiente manera:

∑ = {a, b, c}, posee el conjunto de estados Q = {90, 91, 92, 93, 94, 95, 96}, con las transiciones que se pueden ver. Su estado inicial es qo y el estado final es q3, el lenguaje de salida Γ = {X, Y, Z, B} siendo B el símbolo denominado "blanco". Esta máquina reconoce la expresión regular de la

forma a b c con n >= 0.

• Los estados se representan como vértices, etiquetados con su nombre en el interior.

• Una transición desde un estado a otro, se representa mediante una arista dirigida que une a estos vértices, y está rotulada por símbolo que lee el cabezal/símbolo que escribirá el cabezal, movimiento del cabezal.

• El estado inicial se caracteriza por tener una arista que llega a él y que no proviene de ningún otro vértice.

• El o los estados finales se representan mediante vértices que están encerrados a su vez por otra circunferencia.

Descripción Instantánea

                             Descripción Instantánea

Es una secuencia de la forma a1 qa2 donde 01, 02 Є Г* y q∈Q que escribe el estado de una máquina de Turing. La cinta contiene la cadena 01 02 seguida de infinitos blancos. El cabezal señala el primer símbolo de A2.

Por ejemplo, para la máquina de Turing

MT = ({p, q}, {0, 1}, {0, 1, x}, p, A, {q},

con las transiciones

б(р, 1) = (p, x, R),

б(p, 0) = (p, 0, R) у

δ(p, A) = (q, A, R).

La descripción instantánea para la cinta 1011

es:

p1011∆∆

xp01144

x0p11∆∆

x0 x x q∆∆

Definimos una máquina de Turing sobre el alfabeto {0,1}, donde 0 representa el símbolo blanco. La máquina comenzará su proceso situada sobre un símbolo "1" de una serie. La máquina de Turing copiará el número de símbolos "1" que encuentre hasta el primer blanco detrás de dicho símbolo blanco. Es decir, posiciona el cabezal sobre el 1 situado en el extremo izquierdo, doblará el número de símbolos 1, con un 0 en medio. Así, si tenemos la entrada "111" devolverá "1110111", con "1111" devolverá "111101111", y sucesivamente.

 El conjunto de estados es {81, 82, 83, 84, 85} y el estado inicial es s₁. La tabla que describe la función de transición es la siguiente:

El funcionamiento de una computación de esta máquina puede mostrarse con el siguiente ejemplo (en negrita se resalta la posición de la cabeza lectora/escritora):

La máquina realiza su proceso por medio de un bucle, en el estado inicial s1, reemplaza el primer 1 con un 0, y pasa al estado s2, con el que avanza hacia la derecha, saltando los símbolos 1 hasta un 0 (que debe existir), cuando lo encuentra pasa al estado s3, con este estado avanza saltando los 1 hasta encontrar otro 0 (la primera vez no habrá ningún 1). Una vez en el extremo derecho, añade un 1. Después comienza el proceso de retorno; con s4 vuelve a la izquierda saltando los 1, cuando encuentra un 0 (en el medio de la secuencia), pasa a s5 que continúa a la izquierda saltando los 1 hasta el 0 que se escribió al principio. Se reemplaza de nuevo este 0 por 1, y pasa al símbolo siguiente, si es un 1, se pasa a otra iteración del bucle, pasando al estado s1 de nuevo. Si es un símbolo 0, será el símbolo central, con lo que la máquina se detiene al haber finalizado el cómputo.