¿Que es la Maquina de Turing?

¿Qué es una Máquina de Turing? 

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.

Originalmente fue definida por el matemático inglés Alan Turing como una «máquina automática» en 1936 en la revista Proceedings of the London Mathematical Society​. La máquina de Turing no está diseñada como una tecnología de computación práctica, sino como un dispositivo hipotético que representa una máquina de computación. Las máquinas de Turing ayudan a los científicos a entender los límites del cálculo mecánico.

Turing dio una definición sucinta del experimento en su ensayo de 1948, «Máquinas inteligentes». Refiriéndose a su publicación de 1936, Turing escribió que la máquina de Turing, aquí llamada una máquina de computación lógica, consistía en:

... una ilimitada capacidad de memoria obtenida en la forma de una cinta infinita marcada con cuadrados, en cada uno de los cuales podría imprimirse un símbolo. En cualquier momento hay un símbolo en la máquina; llamado el símbolo leído. La máquina puede alterar el símbolo leído y su comportamiento está en parte determinado por ese símbolo, pero los símbolos en otros lugares de la cinta 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 esto una de las operaciones elementales de la máquina. Por lo tanto cualquier símbolo en la cinta puede tener finalmente una oportunidad.

Tipos de Maquina de Turing

•  1. Máquina de Turing con cinta multipista.
•  2. Máquina de Turing multicinta.
•  3. Máquina de Turing multidimensional.

A CONTINUACIÓN EN EL MENÚ ENCONTRARA LOS DIFERENTES TIPOS DE MAQUINA DE TURING:

Multidimensional

 Máquina de Turing Multidimensional

La máquina de Turing multidimensional es aquella que permite que la cinta tenga muchas dimensiones. Por ejemplo, una cinta de dos dimensiones que se extienda hacia abajo y hacia arriba, al igual que hacia la derecha y hacia la izquierda. Dependiendo del estado actual de la máquina de Turing y del símbolo analizado, cambia de estado, escribe un símbolo en la celda actual y se mueve a la izquierda, al derecha, hacia arriaba o hacia abajo. Por tanto, la función de transición para esta máquina de Turing será de la forma:

d : Q x G ® Q x G x {R, L, U, D}

Una máquina de Turing multidimensional simula una máquina de Turing estándar. Simplemente realizando todas sus computaciones en una única dimensión. Una máquina de Turing estándar también puede simular una máquina de Turing multidimensional y, por tanto, la complejidad y la flexibilidad adicional que se debe a la múltiple dimensión, no es una capacidad real. Para simular una máquina de Turing de dos dimensiones mediante una máquina de Turing estándar, primero se asociara una dirección a todas las celdas de la cinta. Una forma de hacerlo es fijar, de forma arbitraria, un lugar en la cinta a partir del cual se asignarán las coordenadas a las celdas de la misma forma que se realiza en un plano de coordenadas.

Entonces, se usara una cinta de dos pistas para simular la máquina de Turing. Una pista se encargará de almacenar el contenido de las celdas y la otra las coordenadas, utilizando un símbolo (*) para separar los valores de las coordenadas. Para simular un movimiento de una máquina de Turing de dos dimensiones, está máquina calcula la dirección de la celda a la que se moverá la máquina de Turing dos dimensiones. Entonces, localiza la pista inferior la celda con dicha dirección y cambia el contenido de la celda en la pista superior.

Multicinta

  Maquina de Turing Multicinta

La máquina de Turing multicinta tiene varias cintas, cada una de las cuales tiene su propia cabeza de lectura/escritura. Las cabezas de lectura/escritura se controlan independientemente (es decir, al mismo tiempo, no tienen que moverse en la misma dirección, ni realizar el mismo número de movimientos, ni incluso, hacer nada a la vez). En un solo movimiento, esta máquina de Turing:

1. Cambia de estado dependiendo del estado actual y del contenido de las celdas de todas las cintas, que están analizando actualmente las cabezas de lectura/escritura.

2. Escriben un nuevo símbolo en cada una de las celdas barridas por sus cabezas de lectura/escritura.

3. Mueve cada una de sus cabezas hacia la izquierda o hacia la derecha (de forma independiente al resto de las cabezas).

Por tanto, la función de transición para una máquina de Turing con n cintas, es de la forma d : Q x G n ® Q x G n x {R, L} n donde una transición de la forma d (q, (s 1, s 2,…, s n)) = (p,(t 1, t 2, …, t n), (X1, X2, …, Xn)) significa que cambia del estado q a p, reemplaza s i por t i en la cinta i y mueve la cabeza de la cinta i en la dirección Xi.

Multipista

Máquina de Turing con cinta multipista

Es aquella mediante la cual cada celda de la cinta se divide en subceldas. Cada subcelda es capaz de contener símbolos de la cinta. La cinta tiene cada celda subdividida en tres subceldas. Se dice que esta cinta tiene múltiples pistas. Puesto que cada celda de esta máquina de Turing contiene múltiples caracteres, el contenido de las celdas de la cinta puede ser representado mediante n-tuplas ordenadas. En el ejemplo anterior, las celdas de la cinta contienen (B, a, a), (b, a, a) y (b, b, B). Por tanto, los movimientos que realice está máquina dependerán de su estado actual y de la n-tupla que represente el contenido de la celda actual.

Una máquina de Turing multipista no tiene más potencia que la máquina de Turing original. Sin embargo, hace que sea más fácil la construcción de máquinas de Turing que resuelvan ciertos problemas.

Ejemplo: Para una máquina de Turing que sume dos números binarios. Primero se construye una máquina de Turing de tres pistas. La entrada serán dos números binarios que ocupen las dos pistas superiores de la cinta. Suponiendo que sus dígitos se alinean por la derecha, que sus representaciones binarias son de la misma longitud (lo que se puede conseguir rellenándolas con tantos ceros como sea necesario) y que la cabeza de lectura/escritura se sitúa sobre la celda del extremo izquierdo de la cadena. Por tanto, si tuvieran que sumar 101 y 10, la cinta debería contener. 

La máquina de Turing realizará la suma en la tercera pista. Por tanto, el alfabeto de cinta estará formado por las ternas:

(B, B, B) (1, 1, B) (1, 1, 0) (1, 1, 1)

(0, 0, B) (0, 0, 0) (0, 0, 1) (B, B, 1)

(0, 1, B) (0, 1, 0) (0, 1, 1)

(1, 0, B) (1, 0, 0) (1, 0, 1)

Esta máquina de Turing buscará primero hacia la derecha el extremo derecho de los números que van a ser sumados. Entonces sumará pares de dígitos, desde la derecha hacia la izquierda, llevando la cuenta de los resultados que se obtengan y sumando a quienes corresponda.

Por tanto, se obtiene (suponiendo que q1 es el estado inicial):

d (q1, s ) = (q1, s , R), si s ¹ (B, B, B) ó (q2, s , L), si s =(B, B, B)

d (q2, (0, 0, B)) = (q2, (0, 0, 0), L) d (q3, (0, 0, B)) = (q2, (0, 0, 1), L)

d (q2, (0, 1, B)) = (q2, (0, 1, 1), L) d (q3, (0, 1, B)) = (q3, (0, 1, 0), L)

d (q2, (1, 0, B)) = (q2, (1, 0, 1), L) d (q3, (1, 0, B)) = (q3, (1, 0, 0), L)

d (q2, (1, 1, B)) = (q3, (1, 1, 0), L) d (q3, (1, 1, B)) = (q3, (1, 1, 1), L)

d (q2, (B, B, B)) = (q4, (B, B, B), S) d (q3, (B, B, B)) = (q4, (B, B, B), S)

Obsérvese que se necesita que esta máquina de Turing tenga la posibilidad de no moverse.