la maquina de turing
Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo a una tabla de reglas. A pesar de su simplicidad, una máquina de Turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de una CPU dentro de un computador.
click to edit
Funcionamiento de la máquina de Turing
click to edit
a 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:
Mover el cabezal lector/escritor hacia la derecha.
Visualización de una máquina de Turing, en la que se ve el cabezal y la cinta que se lee.
Mover el cabezal lector/escritor hacia la izquierda.
El cómputo se determina a partir de una tabla de estados de la forma:
(estado, valor) {\displaystyle \rightarrow } \rightarrow (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 escribir en la cinta.
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.
click to edit
Representación como diagrama de estados
Las máquinas de Turing pueden representarse mediante grafos particulares, también llamados diagramas de estados finitos, de la siguiente manera:
Esta máquina de Turing está definida sobre el alfabeto {\displaystyle \Sigma ={a,b,c}} \Sigma ={a,b,c}, posee el conjunto de estados {\displaystyle Q={q{o},q{1},q{2},q{3},q{4},q{5},q{6}}} Q={q{o},q{1},q{2},q{3},q{4},q{5},q{6}},
con las transiciones que se pueden ver. Su estado inicial es {\displaystyle q{0}} q{0} y el estado final es {\displaystyle q{2}} q{2}, el lenguaje de salida
{\displaystyle \Gamma ={X,Y,Z,B}} \Gamma ={X,Y,Z,B} siendo {\displaystyle B} B el símbolo denominado "blanco".
Esta máquina reconoce la expresión regular de la forma {\displaystyle a^{n}b^{n}c^{n}} a^{n}b^{n}c^{n} con {\displaystyle n>=0} n>=0.
Los estados se representan como vértices, etiquetados con su nombre en el interior.
Una transición desde un estado a otro, se representa mediante una arista dirigida que une a estos vértices, y está rotulada por símbolo que lee el cabezal/símbolo que escribirá el cabezal, movimiento del cabezal.
El estado inicial se caracteriza por tener una arista que llega a él y que no proviene de ningún otro vértice.
El o los estados finales se representan mediante vértices que están encerrados a su vez por otra circunferencia.
click to edit
Máquina de Turing con movimiento de espera
La función de transición de la MT sencilla está definida por
{\displaystyle \delta :Q\times \Gamma \rightarrow Q\times \Gamma \times {L,R},} \delta :Q\times \Gamma \rightarrow Q\times \Gamma \times {L,R},
la cual puede ser modificada como
{\displaystyle \delta :Q\times \Gamma \rightarrow Q\times \Gamma \times {L,R,S}.} \delta :Q\times \Gamma \rightarrow Q\times \Gamma \times {L,R,S}.
Donde {\displaystyle S!} S! significa «permanecer» o «esperar», es decir no mover el cabezal de lectura/escritura. Por lo tanto,
{\displaystyle \delta (q,\sigma )=(p,\sigma ',S)!} \delta (q,\sigma )=(p,\sigma ',S)! significa que se pasa del estado q al p, se escribe {\displaystyle \sigma '} \sigma ' en la celda actual y la cabeza se queda sobre la celda actual.
Máquina de Turing con cinta infinita a ambos lados
Esta modificación se denota al igual que una MT sencilla, lo que la hace diferente es que la cinta es infinita tanto por la derecha como por la izquierda, lo cual permite realizar transiciones iniciales como {\displaystyle \delta (q{0},x)=(q{1},y,L)!} \delta (q{0},x)=(q{1},y,L)!.
Máquina de Turing con cinta multipista
Es aquella que mediante la cual cada celda de la cinta de una máquina sencilla se divide en subceldas
. Cada celda es así capaz de contener varios símbolos de la cinta. Por ejemplo, la cinta de la figura tiene cada celda subdividida en tres subceldas.
Se dice que esta cinta tiene múltiples pistas puesto que cada celda de esta máquina de Turing contiene múltiples caracteres, el contenido de las celdas de la cinta puede ser representado mediante n-tuplas ordenadas. Los movimientos que realice esta máquina dependerán de su estado actual y de la n-tupla que represente el contenido de la celda actual. Cabe mencionar que posee un solo cabezal al igual que una MT sencilla.
Máquina de Turing multicinta
Una MT con más de una cinta consiste de un control finito con k cabezales lectores/escritores y k cintas. Cada cinta es infinita en ambos sentidos. La MT define su movimiento dependiendo del símbolo que está leyendo cada uno de sus cabezales, da reglas de sustitución para cada uno de los símbolos y dirección de movimiento para cada uno de los cabezales. Inicialmente la MT empieza con la entrada en la primera cinta y el resto de las cintas en blanco.
Máquina de Turing multidimensional
Una MT multidimensional es aquella cuya cinta puede verse como extendiéndose infinitamente en más de una dirección, el ejemplo más básico sería el de una máquina bidimensional cuya cinta se extendería infinitamente hacia arriba, abajo, derecha e izquierda.
En la modificación bidimensional de MT que se muestra en la figura también se agregan dos nuevos movimientos del cabezal {U,D} (es decir arriba y abajo). De esta forma la definición de los movimientos que realiza el cabezal será {L,R,U,D}.