TECNOLÓGICO NACIONAL DE MÉXICO
Instituto Tecnológico de Villahermosa
Lenguajes Autómatas 1
Máquinas de Turing
Docente:
Manuel Antonio Rodríguez Magaña
Alumno:
José Alberto Agüero Ramón
Fecha:
27/05/2019
Carretera Villahermosa-Frontera Km. 3.5 Cd. Industrial C.P. 86010 Apdo 424
Tels. 01 (993) 353-02-59, 353-26-49, Fax 137. Villahermosa, Tabasco, México
www.itvillahermosa.edu.mx
TECNOLÓGICO NACIONAL DE MÉXICO
Instituto Tecnológico de Villahermosa
MÁQUINAS DE TURING
En 1931, el matemático checo Kurt Godel descubrió que había teoremas
matemáticos que eran verdaderos aun cuando no se pudiesen probar. Ante esto,
Alan Turing se puso a investigar aquellos que sí podían ser probados. Quería
intentar demostrar la vieja idea de que las matemáticas no son un arte misterioso,
sino una ciencia exacta regida por reglas lógicas.
Para hacerlo, ideó una máquina imaginaria capaz de realizar de manera
totalmente mecánica los procesos que normalmente llevaría a cabo un
matemático. Había una máquina para cada proceso; así, había una máquina que
sumaba, otra que multiplicaba, etc. Estas máquinas acabarían por recibir el
nombre de "Máquinas de Turing". Básicamente, lo que quería era hacer una lista
de los problemas que una máquina sería capaz de resolver siguiendo reglas
lógicas. Si esta lista abarcaba todos los problemas matemáticos, entonces su tesis
quedaría demostrada, y con ella la teoría de la computabilidad.
Tras estudiar con detenimiento el funcionamiento de sus máquinas, concluyó que
era posible diseñar un artilugio único capaz de cumplir las funciones de cualquier
otra máquina de Turing. A ésta se le llamó la "Máquina Universal de Turing".
Llamamos Máquina de Turing (ó MT) a
M=(Q,Σ,T,δ,q0,B,F)
donde
Q es el conjunto finito de estados que denotaremos por
q0,q1,q2,...
Σ es el alfabeto: el conjunto finito de símbolos de entrada.
Τ es el conjunto de símbolos de cinta. El alfabeto es un subconjunto de Τ.
q0 es el estado inicial: el estado en el que se encuentra inicialmente la MT .
B es un elemento de Σ: el símbolo en blanco. Se encuentra en todas las
casillas de la cinta que no tienen un símbolo de entrada.
F es el conjunto de estados finales.
δ es la función de transiciones.
Carretera Villahermosa-Frontera Km. 3.5 Cd. Industrial C.P. 86010 Apdo 424
Tels. 01 (993) 353-02-59, 353-26-49, Fax 137. Villahermosa, Tabasco, México
www.itvillahermosa.edu.mx
TECNOLÓGICO NACIONAL DE MÉXICO
Instituto Tecnológico de Villahermosa
La expresión
δ(q,X)=(p,Y,D)
indica que en el estado q, si la cabeza de la MT señala al símbolo de cinta X,
entonces la MT escribe el símbolo de cinta Y en la casilla actual (cambia X por Y)
y mueve la cabeza una casilla hacia D (D puede ser derecha, R; o izquierda, L) y
pasa al estado p.
La cinta de la MT está formada por infinitas casillas.
Inicialmente, la palabra de entrada (una concatenación de símbolos del alfabeto)
se encuentra escrita en casillas consecutivas de la cinta y la cabeza señala al
primer símbolo de la palabra. Todas las otras casillas (hacia la izquierda y la
derecha) contienen el símbolo en blanco.
Lenguaje de una Máquina de Turing
El lenguaje de una Máquina de Turing
M=(Q,Σ,T,δ,q0,B,F)
es
L(M):={w∈Σ∗ : q0w⊢∗ αpβ,p∈F,α,β∈T∗}
Es decir, las w de Σ* tales que la máquina de Turing alcanza un estado de
aceptación.
Lenguaje Recursivo
Sea L el lenguaje de una máquina de Turin g M, es decir, L = L(M), y además,
si w es una palabra de L, entonces M se para (y alcanza un estado de
aceptación)
si w no es una palabra de L, entonces M se para (pero no alcanza un
estado de aceptación)
entonces se dice que L es un lenguaje recursivo.
Carretera Villahermosa-Frontera Km. 3.5 Cd. Industrial C.P. 86010 Apdo 424
Tels. 01 (993) 353-02-59, 353-26-49, Fax 137. Villahermosa, Tabasco, México
www.itvillahermosa.edu.mx
TECNOLÓGICO NACIONAL DE MÉXICO
Instituto Tecnológico de Villahermosa
Una máquina de Turing consiste, básicamente, en una cinta infinita, dividida en
casillas. Sobre esta cinta hay un dispositivo capaz de desplazarse a lo largo de
ella a razón de una casilla cada vez. Este dispositivo cuenta con un cabezal capaz
de leer un símbolo escrito en la cinta, o de borrar el existente e imprimir uno nuevo
en su lugar. Por último, contiene además un registro capaz de almacenar un
estado cualquiera, el cual viene definido por un símbolo.
Los símbolos que definen el estado del dispositivo no tienen por qué coincidir con
los símbolos que se pueden leer o escribir en la cinta.
Los posibles símbolos a leer o escribir en la cinta son el 0 y el 1, y los posibles
estados se representan con letras mayúsculas. En el emulador, existe un cambio
en la representación del estado, usando para ello los números del 0 al 99, para
permitir un mayor número de ellos.
una máquina de Turing consta de:
1. Una cinta que se divide en celdas, una al lado de la otra. Cada celda
contiene un símbolo de algún alfabeto finito. El alfabeto contiene un símbolo
especial llamado blanco (aquí escrito como 'B') y uno o más símbolos
adicionales. La cinta se supone que es arbitrariamente extensible hacia la
izquierda y hacia la derecha, es decir, la máquina de Turing siempre es
suministrada con tanta cinta como necesite para su computación. Las
celdas que no se hayan escrito previamente se asumen que están rellenas
con el símbolo blanco. En algunos modelos la cinta tiene un extremo
izquierdo marcado con un símbolo especial; la cinta se extiende o es
indefinidamente extensible hacia la derecha.
2. Un cabezal que puede leer y escribir símbolos en la cinta y mover la cinta a
la izquierda y a la derecha una celda a la vez. En algunos modelos el
cabezal se mueve y la cinta es estacionaria.
3. Un registro de estado que almacena el estado de la máquina de Turing, uno
de los estados finitos. Hay un estado inicial especial con el que el registro
de estado se inicia. Turing escribe que estos estados reemplazan el "estado
Carretera Villahermosa-Frontera Km. 3.5 Cd. Industrial C.P. 86010 Apdo 424
Tels. 01 (993) 353-02-59, 353-26-49, Fax 137. Villahermosa, Tabasco, México
www.itvillahermosa.edu.mx
TECNOLÓGICO NACIONAL DE MÉXICO
Instituto Tecnológico de Villahermosa
de la mente" en que ordinariamente estaría una persona realizando
cálculos.
4. Una tabla finita de instrucciones. Las instrucciones son usualmente 5-
tuplas: qiaj→qi1aj1dk, que, dado el estado (qi) en que la máquina se
encuentra actualmente y el símbolo (aj) que se está leyendo en la cinta (el
símbolo actualmente debajo del cabezal) le indica a la máquina hacer lo
siguiente en secuencia:
o Borra o escribe un símbolo (reemplazando aj con aj1), y entonces
o Mueve el cabezal (que es descrito por d k y puede tener los valores:
'L' para un paso a la izquierda, o 'R' para un paso a la derecha, o 'N'
para permanecer en el mismo lugar) y luego
o Asume el mismo o un nuevo estado como prescrito (ve al estado q i1).
En los modelos de 4-tupla, son especificadas como instrucciones separadas:
borrar o escribir un símbolo (aj1) y mover el cabezal a la izquierda o la derecha (d k).
Específicamente, la tabla indica a la máquina: (ia) borrar o escribir un
símbolo o (ib) mover el cabezal a la izquierda o a la derecha, y luego (ii) asumir el
mismo o un nuevo estado, pero no las dos acciones (ia) y (ib) en la misma
instrucción.
En algunos modelos, si no hay ninguna entrada en la tabla para la actual
combinación de símbolo y estado, la máquina se detendrá; otros modelos
requieren que estén llenas todas las entradas.
La máquina tiene un funcionamiento totalmente mecánico y secuencial. Lo que
hace es leer el símbolo que hay en la casilla que tiene debajo. Después toma el
símbolo del estado en que se encuentra. Con estos dos datos accede a una tabla,
en la cual lee el símbolo que debe escribir en la cinta, el nuevo estado al que debe
pasar y si debe desplazarse a la casilla izquierda o derecha.
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.
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 escribir en la cinta.
Carretera Villahermosa-Frontera Km. 3.5 Cd. Industrial C.P. 86010 Apdo 424
Tels. 01 (993) 353-02-59, 353-26-49, Fax 137. Villahermosa, Tabasco, México
www.itvillahermosa.edu.mx
TECNOLÓGICO NACIONAL DE MÉXICO
Instituto Tecnológico de Villahermosa
La memoria es la cinta de la máquina que 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.
Para comprender mejor, vamos a ver un simple ejemplo: sea la máquina de Turing
capaz de leer o escribir los símbolos 0 y 1 en la cinta (en la definición original de
Turing, el número de símbolos a usar podía ser cualquiera, con la única condición
de ser un número finito, y no tenían por qué ser números; sin embargo, en
aplicaciones prácticas se suelen limitar a estos dos), y que puede tener los
estados A, B y C (una máquina de Turing puede tener cualquier número de
estados; la única condición es que sea un número finito).
Supongamos que definimos la siguiente tabla:
estado símbolo nuevo nuevo sentido de
inicial leído estado símbolo avance
A 0 B 1 DERECHA
A 1 B 0 IZQUIERDA
B 0 A 1 DERECHA
B 1 C 0 DERECHA
C 0 A 0 IZQUIERDA
C 1 C 0 DERECHA
La cual vamos a simplificar de la siguiente manera:
0 1
Carretera Villahermosa-Frontera Km. 3.5 Cd. Industrial C.P. 86010 Apdo 424
Tels. 01 (993) 353-02-59, 353-26-49, Fax 137. Villahermosa, Tabasco, México
www.itvillahermosa.edu.mx
TECNOLÓGICO NACIONAL DE MÉXICO
Instituto Tecnológico de Villahermosa
A B,1,> B,0,<
B A,1,> C,0,>
C A,0,< C,0,>
Hemos puesto los posibles estados en columna, y los posibles símbolos en fila, y
hemos expresado el nuevo estado, símbolo y sentido todo junto. El sentido lo
expresamos con la dirección en la que apunta el símbolo < o >.
Vamos a poner nuestra máquina sobre esta cinta:
cabezal
v
... 0 0 0 0 0 1 0 0 0 0 ...
Indicaremos el estado actual de la máquina encima del cabezal. Veamos los
sucesivos pasos de esta máquina si partimos del estado A:
1) A El estado es A y leemos un cero;
v luego debemos cambiar al estado B,
... 0 0 0 0 0 1 0 0 0 0 ... escribir un 1 y movernos a la
derecha
2) B El estado es B y leemos un cero;
v luego debemos cambiar al estado A,
... 0 0 0 1 0 1 0 0 0 0 ... escribir un 1 y movernos a la
derecha
3) A El estado es A y leemos un uno;
v luego debemos cambiar al estado B,
... 0 0 0 1 1 1 0 0 0 0 ... escribir un 0 y movernos a la
izquierda
4) B El estado es B y leemos un uno;
v luego debemos cambiar al estado C,
... 0 0 0 1 1 0 0 0 0 0 ... escribir un 0 y movernos a la
izquierda
5) C El estado es C y leemos un uno;
v luego debemos cambiar al estado C,
... 0 0 0 1 0 0 0 0 0 0 ... escribir un 0 y movernos a la
derecha
Carretera Villahermosa-Frontera Km. 3.5 Cd. Industrial C.P. 86010 Apdo 424
Tels. 01 (993) 353-02-59, 353-26-49, Fax 137. Villahermosa, Tabasco, México
www.itvillahermosa.edu.mx
TECNOLÓGICO NACIONAL DE MÉXICO
Instituto Tecnológico de Villahermosa
6) C El estado es C y leemos un cero;
v luego debemos cambiar al estado A,
... 0 0 0 0 0 0 0 0 0 0 ... escribir un 0 y movernos a la
izquierda
7) A El estado es A y leemos un cero;
v luego debemos cambiar al estado B,
... 0 0 0 0 0 0 0 0 0 0 ... escribir un 1 y movernos a la
derecha
La ejecución de esta máquina seguiría indefinidamente, rellenando la cinta con
unos y ceros de una manera más o menos aleatoria. Realmente, una máquina de
Turing útil debería poder detenerse; esto es, tener un estado en el que se detiene.
Dicho estado se alcanzaría igual que cualquier otro estado. Esto es, supongamos
que el estado D es el de paro; lo único que debemos hacer es que, cuando la
máquina haya terminado el cálculo, pase a estado D; de este modo se detiene y
permite examinar la cinta para buscar el resultado.
Vemos que esta máquina no hace gran cosa. Sin embargo, una máquina de
Turing puede hacer cosas útiles, tales como sumar dos números, multiplicarlos,
copiarlos, etc. Disponiendo de una máquina con el suficiente número de estados,
podríamos hacer con ella cualquier operación que un ordenador normal pudiese
realizar.
Las máquinas de Turing plantean una deducción bastante curiosa: dado que en
ellas se puede realizar cualquier trabajo computable, es posible programarlas para
que simulen el comportamiento de un potente ordenador. Y como una máquina de
Turing puede ser codificada en cualquier ordenador, por pequeño que sea, sería
posible emular en nuestro ordenador de casa una máquina de Turing que simule
un superordenador. Esto significa que todos los ordenadores pueden realizar
exactamente el mismo tipo de tareas, y que los cálculos que pueda realizar el más
grande los puede llevar a cabo también el más pequeño. La única diferencia sería,
obviamente, la velocidad.
Una de las tareas más simples que puede llevar a cabo una máquina de Turing es
la suma de dos números. Para ello debemos definir primero una convención para
representar dichos números en la cinta. En principio, podríamos pensar que, al
usar los símbolos 0 y 1, podemos representar los números directamente en
binario; sin embargo, la cantidad de operaciones necesarias para trabajar con
ellos hace que el número de estados de la máquina sumadora crezca
sorprendentemente, debido a que es un sistema de numeración posicional.
Copia de una cadena de unos a continuación de ella misma.
Carretera Villahermosa-Frontera Km. 3.5 Cd. Industrial C.P. 86010 Apdo 424
Tels. 01 (993) 353-02-59, 353-26-49, Fax 137. Villahermosa, Tabasco, México
www.itvillahermosa.edu.mx
TECNOLÓGICO NACIONAL DE MÉXICO
Instituto Tecnológico de Villahermosa
Una posibilidad para copiar una cadena de N unos es usar una máquina de N
estados; sin embargo, esto hace aumentar su número de manera poco menos que
incontrolable; por eso nos conviene hallar un sistema que no consuma tantos
estados, y, sobre todo, que funcione para cualquier cadena, no solo para las de
longitud N.
Una de las maneras más cómodas es usar un cero como contador. Esto es:
colocamos un cero en lugar del primer uno de la cadena, nos desplazamos hasta
el final de ella, colocamos un uno, y volvemos hasta donde esté el cero. Lo
cambiamos a un uno, pasamos a la siguiente casilla, ponemos un cero y
repetimos el proceso. De este modo, el cero se irá corriendo a lo largo de la
cadena original, y cada vez que se desplace una posición, aparecerá un nuevo
uno al final de la cadena copiada.
La máquina se detendrá en cuanto intente poner un cero en el lugar que ocupe
otro cero en vez de un uno, pues significará que ha llegado al cero de separación
de la cadena original y la cadena copia.
Veamos un programa que cumple lo expuesto, comentado:
0 1
A 0,A,> Nos movemos hacia la derecha 0,B,> Ponemos un cero en el
hasta el principio de la cadena. primer uno de la cadena.
B 0,C,> Vamos a la derecha, a través de 1,B,> Vamos desde el marcador
la separación entre cadenas. hasta la separación.
C 1,D,< Ponemos un uno en el extremo 1,C,> Vamos hacia la derecha
de la cadena copia. de la cadena copia.
D 0,E,< Vamos hacia la izquierda desde 1,D,< Vamos hacia la izquierda
la separación. por la copia.
E 1,H,< El marcador está a la izquierda 1,F,< Vamos hacia la izquierda
de la separación. Fin de la copia. desde la separación.
F 1,G,> Iniciamos el cambio de lugar 1,F,< Seguimos hasta encontrar
del marcador. el marcador.
H ----- Nunca se da esta condición. No 0,B,> Terminamos el desplaza-
programar o poner un bloque miento del marcador y
ficticio. recomenzamos.
I 0,@ La cadena ya está copiada. 1,I,> Nos movemos hasta el
la máquina debe detenerse. inicio de la cadena original.
Producto de dos números.
Carretera Villahermosa-Frontera Km. 3.5 Cd. Industrial C.P. 86010 Apdo 424
Tels. 01 (993) 353-02-59, 353-26-49, Fax 137. Villahermosa, Tabasco, México
www.itvillahermosa.edu.mx
TECNOLÓGICO NACIONAL DE MÉXICO
Instituto Tecnológico de Villahermosa
Si analizamos el producto de dos números, vemos que se trata simplemente de
sumar el primero a sí mismo tantas veces como indica el segundo. Y como
trabajando con nuestro particular sistema de numeración, la suma no es más que
unir dos cadenas, vemos que esta es una tarea perfecta para nuestra rutina de
copiado.
La manera de hacerlo es muy simple: debido a una casualidad totalmente
intencionada, si hay dos números seguidos (con el cero de separación entre ellos)
y mandamos a nuestra rutina que copie el primero, lo hará a continuación del
segundo, pero sin separarlo; en otras palabras, habrá sumado al segundo una
copia del primero. De este modo, si activamos la rutina de copia sobre el segundo
número a multiplicar, tantas veces como indique el primero, lo que haremos será
sumar el segundo número a sí mismo tantas veces como indique el primero. Los
habremos multiplicado.
Para que la rutina de copia se active tantas veces como indica el primer número,
haremos un contador con un cero, de la misma manera que hicimos en la propia
rutina de copia.
Veamos un programa de máquina de Turing que lo hace. Los estados de la A a la
H son los mismos que los de la rutina de copia, para ahorrar espacio en el artículo.
Esto significa que la máquina no se debe poner en marcha en el estado A, sino en
el estado J.
0 1 0 1
I 0,L,< 1,I,< M 1,N,> 1,M,<
J 0,J,> 0,K,> N ----- 0,K,>
K 0,A,> 1,K,> O 0,@ 1,O,<
L 1,O,< 1,M,<
El bloque “-----“significa que esa condición nunca puede darse, por lo que se
debe dejar sin rellenar o bien poner un bloque ficticio.
La rutina borra cintas.
Un programa que, en principio, no pasa de ser una mera curiosidad, es el
programa borra cintas. Lo único que hace es colocar la cinta de una máquina de
Turing a cero, eliminando todos los posibles unos que pudiese contener. Dado que
el número de unos existentes no lo podemos conocer a priori, y dado que la cinta
es infinita, esta máquina, para que realmente sea eficiente, no podrá detenerse
nunca. De todos modos, el número de unos no puede ser infinito, pues entonces
nunca conseguiríamos borrar totalmente la cinta (por mucho tiempo que
tuviésemos la máquina en funcionamiento, siempre quedarían unos sin borrar).
Veamos como diseñarla.
Carretera Villahermosa-Frontera Km. 3.5 Cd. Industrial C.P. 86010 Apdo 424
Tels. 01 (993) 353-02-59, 353-26-49, Fax 137. Villahermosa, Tabasco, México
www.itvillahermosa.edu.mx
TECNOLÓGICO NACIONAL DE MÉXICO
Instituto Tecnológico de Villahermosa
Una posible opción sería hacer una máquina de un solo estado que, encuentre lo
que encuentre, escriba un cero y pase a la casilla siguiente. Su listado sería:
0 1
A 0,A,> 0,A,>
Sin embargo, que esta máquina no es totalmente efectiva, pues sólo elimina los
unos que se hallen a la derecha de la posición de origen. Podríamos diseñar una
máquina borra cintas que trabaje hacia la izquierda, y usar primero una y luego
otra; pero como la cinta es infinita, nunca sabríamos cuando podemos parar, pues
pueden quedar aún unos por eliminar. Por eso debemos diseñar otra máquina
más versátil que ésta.
Carretera Villahermosa-Frontera Km. 3.5 Cd. Industrial C.P. 86010 Apdo 424
Tels. 01 (993) 353-02-59, 353-26-49, Fax 137. Villahermosa, Tabasco, México
www.itvillahermosa.edu.mx
TECNOLÓGICO NACIONAL DE MÉXICO
Instituto Tecnológico de Villahermosa
La segunda versión de la máquina borra cintas usa dos estados. Se trata de una
unión de las dos máquinas borra cintas anteriores. Lo que hace es desplazarse en
un sentido hasta que encuentra un uno. En cuanto llega a él lo cambia por un cero
y se desplaza en el sentido contrario hasta encontrar otro uno, repitiendo el
proceso. Su listado sería:
0 1 0 1
A 0,A,> 0,B,< B 0,B,< 0,A,>
Si bien esta máquina es notablemente superior, vemos que puede darse el caso
de que haya más unos hacia el lado derecho de la posición inicial que hacia el
lado izquierdo (no olvidemos que el número de unos es finito). Si se diese esta
situación, en cuanto se acabasen los unos en uno de los lados, la máquina se
escaparía por él, dejando los del otro lado sin borrar. Por fortuna, en esta vida todo
tiene solución, y este problema no iba a ser menos.
Para conseguir eliminar todos los unos, podemos hacer que, cada vez que la
máquina encuentre uno, lo ponga a cero, coloque un uno en la siguiente posición,
e invierta su sentido. De este modo, los nuevos unos se comportarán como
barreras. Cada vez que la máquina llega a una, la desplaza una posición e invierte
su sentido. De este modo, la máquina siempre recorrerá por igual los dos sentidos.
Una precaución consiste en colocar al principio dos unos seguidos, pues puede
ocurrir que en uno de los dos sentidos no haya unos, y la máquina se pierda. De
este modo, al colocar esos dos unos, inicializamos las barreras. A cada vuelta, las
barreras se irán ensanchando más. Cuando una barrera se pone encima de un
uno, lo anula, de modo que al siguiente paso del cabezal quedará eliminado.
El programa puede ser el siguiente:
0 1 0 1
A 1,B,> 1,B,> D 1,E,> 1,E,>
B 1,C,< 1,C,< E 0,E,> 0,F,>
C 0,C,< 0,D,< F 1,C,< 1,C,<
Los estados A y B sirven para inicializar las dos barreras. El código del programa
empieza en C, desplazándose hacia la izquierda hasta encontrar un uno, momento
en que lo cambia por un cero y pasa al estado D, que pone un uno una posición
más hacia la izquierda e inicia el desplazamiento hacia la derecha, pasando al
estado E. En el cabezal se desplaza hacia la derecha hasta encontrar un uno,
cambiándolo por un cero y pasando al estado F en la siguiente casilla. En este
estado, se pone un uno y se comienza el desplazamiento hacia la izquierda,
volviendo al estado C y cerrando el bucle.
Carretera Villahermosa-Frontera Km. 3.5 Cd. Industrial C.P. 86010 Apdo 424
Tels. 01 (993) 353-02-59, 353-26-49, Fax 137. Villahermosa, Tabasco, México
www.itvillahermosa.edu.mx
TECNOLÓGICO NACIONAL DE MÉXICO
Instituto Tecnológico de Villahermosa
Los castores afanosos.
El problema del castor afanoso es uno de los más interesantes, trabajando con
máquinas de Turing. Un castor afanoso es, simplemente, una máquina de Turing
de N estados, la cual, una vez puesta en marcha sobre una cinta totalmente a
cero, imprime más unos que cualquier otra máquina de Turing de N estados.
Además de esto, debe cumplir la condición de detenerse tras haber impreso la
serie de unos. No es indispensable que los unos estén seguidos en la cinta; puede
haber ceros de separación entre ellos.
Es la base de la teoría de la computabilidad de una función. Precisamente, el
máximo número de unos que puede imprimir una máquina de Turing de N estados
es una función no computable; es decir, si queremos hacer un castor afanoso de N
estados, no podemos saber, a priori, cual es el número de unos que imprimirá.
Se sabe el máximo de unos para las máquinas de 1,2,3 y 4 estados, que son 1, 4,
6 y 13 unos, respectivamente. Para más estados, el número exacto no se puede
determinar.
Vamos a ver los programas de algunos castores afanosos:
Castor afanoso de 1 estado:
0 1
A 1,@ 1,@
Castor afanoso de 2 estados:
0 1
A 1,B,> 1,B,<
B 1,A,< 1,@
Castor afanoso de 3 estados:
0 1
A 1,B,> 1,C,<
B 1,A,< 1,B,>
C 1,B,< 1,@
Castor afanoso de 5 estados:
Para intentar resolver el problema del castor afanoso de cinco estados, en 1982 se
anunció un concurso. Para participar, había que presentar un castor afanoso
Penta estado, y ganaría el que más “unos” fuese capaz de imprimir antes de
detenerse.
Carretera Villahermosa-Frontera Km. 3.5 Cd. Industrial C.P. 86010 Apdo 424
Tels. 01 (993) 353-02-59, 353-26-49, Fax 137. Villahermosa, Tabasco, México
www.itvillahermosa.edu.mx
TECNOLÓGICO NACIONAL DE MÉXICO
Instituto Tecnológico de Villahermosa
El vencedor del concurso, celebrado en enero de 1983, fue la máquina presentada
por Uwe Schult, la cual fue capaz de imprimir 501 unos en la cinta. Su programa
es el siguiente:
0 1 0 1
A 1,B,> 0,C,< D 0,E,> 1,@
B 1,C,> 1,D,> E 1,C,< 1,A,>
C 1,A,< 0,B,>
Una vez puesta en marcha, parece seguir un curso cíclico, a medida que va
aumentando el número de unos de la cinta. De hecho, parece que nunca se va a
detener; sin embargo, como castorcito afanoso que es, se detiene una vez
cumplida su misión: imprimir 501 unos.
Máquina de Turing Cuántica
En 1985, Deutsch presentó el diseño de la primera Máquina cuántica basada en
una máquina de Turing. Con este fin enunció una nueva variante la tesis de
Church-Turing dando lugar al denominado "principio de Church-Turing-Deutsch".
La estructura de una máquina de Turing cuántica es muy similar a la de una
máquina de Turing clásica. Está compuesta por los tres elementos clásicos: una
cinta de memoria infinita en donde cada elemento es un qubit, un procesador finito
y un cabezal.
El procesador contiene el juego de instrucciones que se aplica sobre el elemento
de la cinta señalado por el cabezal. El resultado dependerá del qubit de la cinta y
del estado del procesador. El procesador ejecuta una instrucción por unidad de
tiempo.
La cinta de memoria es similar a la de una máquina de Turing tradicional. La única
diferencia es que cada elemento de la cinta de la máquina cuántica es un qubit. El
alfabeto de esta nueva máquina está formado por el espacio de valores del qubit.
La posición del cabezal se representa con una variable entera.
Carretera Villahermosa-Frontera Km. 3.5 Cd. Industrial C.P. 86010 Apdo 424
Tels. 01 (993) 353-02-59, 353-26-49, Fax 137. Villahermosa, Tabasco, México
www.itvillahermosa.edu.mx
TECNOLÓGICO NACIONAL DE MÉXICO
Instituto Tecnológico de Villahermosa
Máquina de Turing determinista y no determinista
La entrada de una máquina de Turing viene determinada por el estado actual y el
símbolo leído, un par (estado, símbolo), siendo el cambio de estado, la escritura
de un nuevo símbolo y el movimiento del cabezal, las acciones a tomar en función
de una entrada. En el caso de que para cada par (estado, símbolo) posible exista
a lo sumo una posibilidad de ejecución, se dirá que es una máquina de Turing
determinista, mientras que en el caso de que exista al menos un par (estado,
símbolo) con más de una posible combinación de actuaciones se dirá que se trata
de una máquina de Turing no determinista.
La función de transición δ en el caso no determinista, queda definida como sigue:
¿Cómo sabe una máquina no determinista qué acción tomar de las varias
posibles? Hay dos formas de verlo: una es decir que la máquina es "el mejor
adivino posible", esto es, que siempre elige la transición que finalmente la llevará a
un estado final de aceptación. La otra es imaginarse que la máquina se "clona",
bifurcándose en varias copias, cada una de las cuales sigue una de las posibles
transiciones. Mientras que una máquina determinista sigue un único "camino
computacional", una máquina no determinista tiene un "árbol computacional". Si
cualquiera de las ramas del árbol finaliza en un estado de aceptación, se dice que
la máquina acepta la entrada.
La capacidad de cómputo de ambas versiones es equivalente; se puede
demostrar que dada una máquina de Turing no determinista existe otra máquina
de Turing determinista equivalente, en el sentido de que reconoce el mismo
lenguaje, y viceversa. No obstante, la velocidad de ejecución de ambos
formalismos no es la misma, pues si una máquina no determinista M reconoce una
cierta palabra de tamaño n en un O(t(n)), la máquina determinista equivalente
reconocerá la palabra en un tiempo O(2t(n)). Es decir, el no determinismo permitirá
reducir la complejidad de la solución de los problemas, permitiendo resolver, por
ejemplo, problemas de complejidad exponencial en un tiempo polinómico.
Carretera Villahermosa-Frontera Km. 3.5 Cd. Industrial C.P. 86010 Apdo 424
Tels. 01 (993) 353-02-59, 353-26-49, Fax 137. Villahermosa, Tabasco, México
www.itvillahermosa.edu.mx
TECNOLÓGICO NACIONAL DE MÉXICO
Instituto Tecnológico de Villahermosa
Bibliografía
(s.f.).
Alfonseca, M. (26 de Junio de 2014). Sinewton. Obtenido de
http://www.sinewton.org/numeros/numeros/43-44/Articulo33.pdf
Anonimo. (24 de Febrero de 2015). EcuRed. Obtenido de https://www.ecured.cu/M
%C3%A1quina_de_Turing
Anonimo. (17 de Octubre de 2015). Matesfacil. Obtenido de
https://www.matesfacil.com/automatas-lenguajes/Maquina-Turing.html
Anonimo. (8 de Septiembre de 2016). Rastersoft. Obtenido de
https://www.rastersoft.com/articulos/turing.htm
Carretera Villahermosa-Frontera Km. 3.5 Cd. Industrial C.P. 86010 Apdo 424
Tels. 01 (993) 353-02-59, 353-26-49, Fax 137. Villahermosa, Tabasco, México
www.itvillahermosa.edu.mx
