3. Qué es una Máquina de Turing y cómo funciona.

Una máquina de Turing es un dispositivo que transforma un INPUT en un OUTPUT después de algunos pasos. Tanto el INPUT como el OUPUT constan de números en código binario (ceros y unos). En su versión original la máquina de Turing consiste en una cinta infinitamente larga con unos y ceros que pasa a través de una caja. La caja es tan fina que solo el trozo de cinta que ocupa un bit (0 ó 1) está en su interior. La máquina tiene una serie de estados internos finitos que también se pueden numerar en binario. Para llevar a cabo algún algoritmo, la máquina se inicializa en algún estado interno arbitrario. A continuación, se pone en marcha y la máquina lee el bit que se encuentra en ese momento en su interior y ejecuta alguna operación con ese bit (lo cambia o no, dependiendo de su estado interno). Después se mueve hacia la derecha o hacia la izquierda, y vuelve a procesar el siguiente bit de la misma manera. Al final se para, dejando el resultado al lado izquierdo por ejemplo.



Definición formal

Una máquina de Turing con una sola cinta puede ser definida como una 7-tupla M={Q,Σ,Γ,s,b,F,δ}, donde:

• Q es 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 ∈ Q es el estado inicial.

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

• F⊆Q es el conjunto de estados finales de aceptación.

• δ:Q x Γ → Q x Γ x{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.

Existen 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

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:

• Avanzar el cabezal lector/escritor hacia la derecha.

• Avanzar el cabezal lector/escritor hacia la izquierda.

El cómputo es determinado 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 ser escrito en la cinta.

Escritura en una MT

La memoria será la cinta la cual 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.

Borrado en una MT

Por definición, al iniciar la operación de la MT, la cabeza lectora está posicionada en el carácter blanco a la izquierda de la palabra de entrada, el cual es el cuadro más a la izquierda de la cinta.

Decimos que en la MT se llega al “final de un cálculo” cuando se alcanza un estado especial llamado halt en el control finito, como resultado de una transición. Representaremos al halt por “h”. 1 Al llegar al halt, se detiene la operación de la MT, y se acepta la palabra de entrada. Ası, en la MT no hay estados finales. En cierto sentido el halt serıa entonces el único estado final, solo que además detiene la ejecución. Cuando queremos que una palabra no sea aceptada, desde luego debemos evitar que la MT llegue al halt. Podemos asegurarnos de ello haciendo que la MT caiga en un ciclo infinito (ver ejemplos adelante).

El lenguaje aceptado por una MT es simplemente el conjunto de palabras aceptadas por ella.

Para más información de las MT se pueden consultar: Definiciones y ejemplos de funcionamiento