Maquina De Turing

A continuación abordaremos los temas de la UNIDAD TEMÁTICA IV –MAQUINAS DE TURING (MT), la cual posee los siguientes contenidos:



1. DESCRIPCIÓN FORMAL.
2. MT UNIVERSAL Y VARIACIONES DEL MODULO BÁSICO.
3. COMPUTABILIDAD Y NO COMPUTABILIDAD.
4. TESIS DE CHURCH/TURING.
5. DECIDIBILIDAD DE PROBLEMAS, PROBLEMAS DE PARADA.



1.DESCRIPCIÓN FORMAL


A continuaciónestudiaremos la Maquina de Turing (MT), la cual consiste en un conjunto de celdas de almacenamiento que se extiende infinitamente en ambas direcciones, almacenando un símbolo en cada celda. Tiene una cabeza de lectura / escritura que avanza bi-direccionalmente. Su almacenamiento es ilimitado. La maquina de Turing puede reconocer tanto lenguajes regulares, lenguajes libres de contexto, como todo tipo delenguajes.

Una Maquina de Turing (MT) es una 7-upla de elementos M = ((,(,(,Q, q0,F,() donde:
• ( es el alfabeto de cinta infinito por ambos lados.
• ( ( ( es el alfabeto de entrada.
• ( ( ( (( ( () es el símbolo de espacio en blanco, string vació (lambda).
• Q conjunto de estados
• q0 ( Q es el estado inicial
• F ( Q conjunto de estados finales ode aceptación (de parada).
• (: Q x ( ( Q x ( x { I, D, H} es la función de transición que puede ser parcial, porque no necesariamente esta definida para todos lo pares Q, ( ; pudiendo haber pares sin imagen definida.

DESCRIPCIÓN INSTANTÁNEA:

Dada una MT M=((,(,(,Q,q0,F,() sea X1....Xi-1qXi.....Xn con X1,...,Xn ( ( y q ( Q, indica que M esta en el estado q, que la cabeza de lecturaescritura se encuentra situado sobre la Xi y que todas la casillas a la izquierda de X1 y todas las casillas de la derecha de Xn contienen (.
Al ser de longitud infinita, todas aquellas que no poseen un símbolo de ( tendrán inscripto el símbolo de ( por lo que es posible que existan transacciones definidas sobre dicho símbolo para algún estado dado.

El movimiento se expresa de la siguientemanera├M: hay tres alternativas dependiendo de el sentido del movimiento indicado por las directivas I (izquierda), D (derecha) o H (se mantiene).

X1....Xi-1qXi.....Xn├M X1....pXi-1Y....Xn si ((q,Xi)=(p,Y,I).
X1....Xi-1qXi.....Xn├M X1....Xi-1Yp....Xn si ((q,Xi)=(p,Y,D).
X1....Xi-1qXi.....Xn├M X1....Xi-1pY....Xn si ((q,Xi)=(p,Y,H).

Se utiliza la notación ├M para indicar un solomovimiento y ├M * para indicar cero o mas movimientos.


Esquema de La Maquina De Turing.

Cinta infinita
|... |








2.MT UNIVERSAL Y VARIACIONES DEL MODULO BÁSICO.

MT UNIVERSAL
Una computadora tiene la capacidad de interpretar algoritmos y obtener la misma respuesta que obtendría el algoritmo en sí. ¿Será factible pensar que existe una Máquina de Turingque se comporta de la misma forma que una computadora?
La respuesta es afirmativa, dado que existe una máquina capaz de interpretar una máquina cualquiera, y es conocida como Máquina de Turing Universal.
Esta máquina es capaz de ejecutar Máquinas de Turing; de hecho, esta es la base de la existencia de las computadoras, ya que no son más que una generalización de la Máquina de Turing Universal.La máquina de Turing Universal podemos definirla como una máquina que, a partir de una descripción adecuada de cualquier Máquina de Turing M y una cadena de entrada w, simula el comportamiento de M sobre w.

. Programa: máquina de Turing simulada codificada + cinta de entrada (con un 1 al principio y un 1 al final).

- Constan de 3 cintas:
. 1ª cinta: programa + cadena de entrada.* Contendrá la salida de la máquina.
. 2ª cinta: área de trabajo (manipulación de datos).
. 3ª cinta: estado actual de la máquina simulada.
- La máquina universal:
. Copia la cadena de entrada de la cinta 1 a la cinta 2.
. Graba el código del estado inicial en la cinta 3.
. Busca una transición aplicable en la máquina codificada de la cinta 1. Cuando la...