La máquina de Turing (abreviado MT) tiene, un control finito, una cabeza lectora y
una cinta donde puede haber caracteres, y donde eventualmente viene la palabra de
entrada. La cinta es de longitud infinita hacia la derecha, hacia donde se extiende
indefinidamente, llenándose los espacios con el carácter blanco (que representaremos con “t”).
La cinta no es infinita hacia la izquierda, por lo que hay un cuadro de la cinta que es el
extremo izquierdo, la MT la cabeza lectora es de lectura y escritura, por lo que la cinta
puede ser modificada en curso de ejecución. Además, en la MT la cabeza se mueve
bidireccionalmente (izquierda y derecha), por lo que puede pasar repetidas veces sobre un
mismo segmento de la cinta.
Este modelo está conformado 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 es finita por la izquierda)
pertenecientes al alfabeto de entrada. Luego va leyendo una celda de la cinta, borrando el
símbolo, escribir el nuevo símbolo perteneciente al alfabeto de salida y finalmente avanza a
la izquierda o a la derecha(solo una celda a la vez), repitiendo esto 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.
¿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.
La traducción es como sigue: si la máquina se encuentra en el estado interno 0 y lee 1 en la cinta,
entonces pasará al estado interno 1101 (13), escribirá 1 y se moverá hacia la izquierda un paso
(la cinta se moverá hacia la derecha).
A continuación es conveniente inventar una notación para la secuencia del INPUT.
Esta notación se llama notación binaria expandida. Consiste en cambiar la secuencia original
binaria por otra construida de la siguiente forma: el 0 se cambia por 0 y el 1 por 10 y se ponen
un cero a la izquierda y/o a la derecha del resultado si empieza o acaba en 1 respectivamente.
Así por ejemplo, el número 13 que en binario es 1101 es en binario expandido 1010010 con
un cero delante por esta última regla 01010010. Para volver al original hay que contraer el
binario expandido con la siguiente regla:
Empezamos a leer por la izquierda el binario expandido. Cuando encontremos un 0 tomamos
nota de cuántos 1 hay hasta llegar al siguiente 0 y lo escribimos. Si encontramos que hay dos
0 seguidos, apuntaríamos un 0 porque no habría ningún 1.Veamos con el 13 cómo se haría.
El primer 0 se encuentra en la primera posición y el siguiente 0 está en la posición 3.
Entre los dos solo hay un 1. Lo anotamos. Seguidamente hay un 1, y después un 0, entonces
apuntamos 1 porque hay un 1 entre medias de ellos. Esto es lo que se hace sucesivamente
y encontramos: 1101 que es el número original.
No hay comentarios:
Publicar un comentario