.: Máquina de Turing :.

:: Máquina de Turing ::

---

---

Materia. Lenguajes de Programación
Hora. M1 -M3 (Martes)

Introducción.


A principios del siglo XX, en lo que fue el campo de las matemáticas, Hilbert había planteado ciertas cuestiones que fueron a parar en las teorias de la computación y la computabilidad.


En matemáticas se considera un método es efectivo para obtener un resultado cuando el procedimiento:

• Puede ser expresado por un algoritmo.
• Puede ser seguido sin error para conseguir el resultado.
• Puede ser seguido por un humano.
• No exige ninguna habilidad o inteligencia especial por parte de la persona que lo realiza.

Para dar una idea sólida sobre lo que es un algoritmo, Turing ideo un dispositivo que llamó Máquina de Computación Lógica (LCP), pero que es conocida en su honor como Máquina de Turing.

Lo que le da la importancia a este dispositivo es el hecho de que es capaz de resolver cualquier problema matemático con la condición de que haya sido reducido a un algoritmo.


De hecho Turing demostró con esto que hay problemas matemáticos que incluso no pueden tener solución.


Por consiguiente, a como lo comprendo, puedo decir que la máquina de turing es una ayuda para los problemas matemáticos, en los cuales podemos ver si hay o no una solución real para estos.

La Máquina de Turing

Es un dispositivo que se mueve sobre una secuencia lineal de datos. En cualquier momento puede leer un solo dato de la línea, realizar ciertas acciones en base a una tabla que toma de base su estado actual y el último dato leído.


Entre las acciones mencionadas, puede escribir nuevos datos en la secuencia, recorrer la misma en ambos sentidos (izquierda y derecha).


La máquina de Turing en sí no es una máquina sino una abstracción matemática. Se le denomina máquina por el hecho de que sus operaciones están descritas en procesos individuales que sugieren una implementación real muy simple.


Existen diversas variedades de la máquina de Turing, pero la más simple puede describirse como la que cumple con las condiciones siguientes:

• Tiene una cinta sobre la que puede desplazarse un cabezal de lectura/escritura de izquierda a derecha. La cinta tiene celdas donde se almacena un símbolo de cierto conjunto de datos. Este conjunto al que me pertenece ese símbolo en el alfabeto de la máquina. Al inicio, las celdas que no se hayan escrito antes contienen un carácter nulo o vacio (0 ó #). La cinta puede contener el número de celdas en ambos sentidos como sean necesarios para el funcionamiento de la máquina.
• El cabezal puede leer y escribir cualquier carácter de su alfabeto sobre la cinta, además de moverse a la izquierda (L) o a la derecha (R).

Existe un registro de estado que almacena el estado de la máquina, donde el número de estados tiene un límite. No se exige un estado específico para comenzar a funcionar.


Tenemos una tabla de acciones que indican las instrucciones a seguir de lo que hará el el programa del dispositivo, las cuales incluyen cuatro pasos:

1. Leer el carácter.
2. Escribir el nuevo símbolo correspondiente al estado de donde se encuentra.
3. Desplazar el cabezal en la dirección correspondiente para situarse en sobre otro caracter: izquierda o derecha.
4. Decidir el nuevo estado, y repetir los pasos anteriores.

En el momento que la lectura del carácter no concuerda con el estado actual del dispositivo, se detiene la ejecución y termina.


La tabla de acciones suele definirse como una matriz de cinco columnas, las cuales son:


Estado / Carácter Leído / Carácter A Escribir / Movimiento / Nuevo Estado


Una tabla por ejemplo, es la que se presenta más abajo en la actividad, la cual representa el comportamiento de una máquina de Turing capaz de sumar 1 a cualquier número unario. Su alfabeto sólo tiene dos símbolos: 0 (Vacio) y 1 (Valor)


NOTA. Hay quienes sostienen que la máquina de Turing original sólo utiliza un alfabeto unario.


Es importante para el buen funcionamiento (lograr un sistema de Turing completo) que la cinta pueda desplazarse indefinidamente de izquierda a derecha. También debe tener las siguientes funcionalidades:

• Almacenar datos de entrada.
• Funcionar como elemento de sálida.
• Y como almacenamiento de información intermedia durante el proceso.

Ejemplo:


Supongamos una máquina de Turing con un alfabeto unario, en la que el nulo lo señalamos con 0. La máquina puede tener cinco estados que denominamos {e0, e1, e2, e3, e4}. El estado inicial es e0.


La tabla debe contener al menos tantas filas como estados distintos.



• S: Estado anterior
• R: Símbolo leído
• W: Símbolo a escribir
• M: Movimiento (R, L).
• N: Nuevo estado.

Cada vez que se alcanza un estado para el que no exista una entrada para el carácter leído, la máquina se detiene. En nuestro caso la tabla señala acciones concretas para cualquier carácter leído (0 o 1) en cualquiera de los estados e1, e2, e3 y e4, pero si en el estado e0 se lee un 0, la máquina se detiene.


El programa hace que el dispositivo lea la cantidad y la repita a la derecha separada por un nulo (0). Por ejemplo, si encuentra 111100000 lo transforma en 111101111.


Dato de Entrada: 11000
Salida: 11011

Bibliografía.

• Zator. “Computación: Máquina de Turing”. http://www.zator.com/Cpp/E0_1_1.htm