MAQUINAS DE TURING

MAQUINAS DE TURING

CONTENIDO:

• DEFINICIÓN FORMAL DE LAS M.T.
• CONSTRUCCIÓN DE LAS M.T.
• LENGUAJES DE ACEPTACIÓN PARA LAS M.T.
• M.T COMO E NUMERADORES.
• M.T RESTRINGIDAS.

MAQUINAS 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.

Originalmente fue definida por el matemático inglés Alan Turing como una «máquina automática» en 1936, en la revista Proceedings of the London Mathematical Society,​ La máquina de Turing no está diseñada como una tecnología de computación práctica, sino como un dispositivo hipotético que representa una máquina de computación. Las máquinas de Turing ayudan a los científicos a entender los límites del cálculo mecánico.

Turing dio una definición sucinta del experimento en su ensayo de 1948, «Máquinas inteligentes». Refiriéndose a su publicación de 1936, Turing escribió que la máquina de Turing, aquí llamada una máquina de computación lógica, consistía en:

... una ilimitada capacidad de memoria obtenida en la forma de una cinta infinita marcada con cuadrados, en cada uno de los cuales podría imprimirse un símbolo. En cualquier momento hay un símbolo en la máquina; llamado el símbolo leído. La máquina puede alterar el símbolo leído y su comportamiento está en parte determinado por ese símbolo, pero los símbolos en otros lugares de la cinta no afectan el comportamiento de la máquina. Sin embargo, la cinta se puede mover hacia adelante y hacia atrás a través de la máquina, siendo esto una de las operaciones elementales de la máquina. Por lo tanto cualquier símbolo en la cinta puede tener finalmente una oportunidad.

• DEFINICIÓN FORMAL DE LAS M.T.

Una máquina de Turing ​es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma.

Este modelo está formado por un alfabeto de entrada y uno de salida, un símbolo especial llamado blanco (normalmente b, ${\displaystyle \Delta }$ 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 puede ser infinita) pertenecientes al alfabeto de entrada. La máquina va leyendo una celda de la cinta en cada paso, borrando el símbolo en el que se encuentra posicionado su cabezal y escribiendo un nuevo símbolo perteneciente al alfabeto de salida, para luego desplazar el cabezal a la izquierda o a la derecha (solo una celda a la vez). Esto se repite 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.

Una máquina de Turing con una sola cinta puede definirse como una 7-tupla

${\displaystyle M=(Q,\Sigma ,\Gamma ,s,b,F,\delta ),\!}$

donde:⁵​

• ${\displaystyle Q\!}$ es un conjunto finito de estados.
• ${\displaystyle \Sigma \!}$ es un conjunto finito de símbolos distinto del espacio en blanco, denominado alfabeto de máquina o de entrada.
• ${\displaystyle \Gamma \!}$ es un conjunto finito de símbolos de cinta, denominado alfabeto de cinta (${\displaystyle \Sigma \subseteq \Gamma }$).
• ${\displaystyle s\in Q}$ es el estado inicial.
• ${\displaystyle b\in \Gamma }$ es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.
• ${\displaystyle F\subseteq Q}$ es el conjunto de estados finales de aceptación.
• ${\displaystyle \delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\}}$ es una función parcial denominada función de transición, donde ${\displaystyle L\!}$ es un movimiento a la izquierda y ${\displaystyle 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 ${\displaystyle S\!}$ como símbolo de "no movimiento" en un paso de cómputo.

• CONSTRUCCIÓN DE LAS M.T.

El objetivo de la creación modular de una maquina de Turing es poder desarrollar máquinas complejas a partir de bloques elementales, a partir de maquinas más pequeñas, mediante diagramas de transiciones. La construcción de máquinas de Turing se lleva a cabo mediante los diagramas de transición y combinarlos de manera parecida a lo que se realiza en la formación de la unión y concatenación de los autómatas finitos.


Pasos para la construcción de una máquina de Turing:

1. Elimine las características de inicio de los estados iniciales de las maquinas, excepto la de aquel donde iniciara la maquina compuesta.

2. Elimine las características de detención de los estados de parada de todas la maquinas e introduzca un nuevo estado de parada que nos se encuentre en ninguno de los diagramas que se combinan.

3. Para cada uno de los antiguos estados de parada p y cada x en y.

Ejemplificación de dicha construcción.

Los diagramas compuestos para la construcción modular de una máquina de Turing: 


Son aquellos en los que cada uno de los bloques de construcción se representa como un nodo, con flechas entre dichos nodos para indicar las transiciones entre bloques.

Se puede combinar dos máquinas de Turing permitiendo que compartan la misma cinta y, que cuando una termine su ejecución, la otra empiece. El contenido de la cinta cuando comienza la ejecución de la segunda máquina de Turing, está formado por todo lo que dejó la primera máquina de Turing, y la cabeza de l/e de la segunda se situará, al comienzo de la ejecución, sobre la celda de la cinta sobre la que terminó la primera.

Un sistema Turing completo es aquel que puede simular el comportamiento de una máquina de Turing. Es evidente que salvando los problemas de memoria, los ordenadores modernos y los lenguajes de programación de uso general, son sistemas de Turing completos. También es evidente, que con independencia de su forma concreta, cualquier dispositivo que se comporte como un sistema de Turing completo, puede en principio ejecutar cualquier cálculo que realice cualquier computador.

Nota: Observe que la anterior afirmación no menciona para nada la posible dificultad de escribir el programa o del tiempo que pueda emplear en realizar el cálculo (cualquier cálculo que pueda hacer un ordenador puede teóricamente efectuarse con papel y lápiz).

Una máquina de Turing es un autómata que se mueve sobre una secuencia lineal de datos. En cada instante la máquina puede leer un solo dato de la secuencia (generalmente un carácter) y realiza ciertas acciones en base a una tabla que tiene en cuenta su "estado" actual (interno) y el último dato leído. Entre las acciones está la posibilidad de escribir nuevos datos en la secuencia; recorrer la secuencia en ambos sentidos y cambiar de "estado" dentro de un conjunto finito de estados posibles.


Maquinas de Turing Compuesta.

• LENGUAJES DE ACEPTACIÓN PARA LAS M.T.

Aceptan lenguajes formales que pueden ser generados por una gramática de tipo 0: recursivamente innumerable. Las maquinas de Turing son los reconocedores de lenguaje más poderosos que existen.

Lenguajes regulares: las gramáticas (de tipo 3) formales definen un lenguaje describiendo como se pueden generar las cadenas del lenguaje… Las gramáticas regulares (aquellos reconocidos por un autómata finito). Son las gramáticas más restrictivas. El lado derecho de una producción debe contener un símbolo Terminal y como máximo un símbolo no Terminal.

• M.T COMO E NUMERADORES.

Sea una máquina de Turing M multicinta que posee una cinta de solo escritura (salida) cuyo cabezal no se desplaza nunca a la izquierda. M escribe cadenas sobre la cinta de salida separadas por un símbolo especial de separación #. contenido de la cinta de salida: x1#x2# . . . #xn# . . . donde xi ∈ Σ∗ Lenguaje generado por M: G(M) = {x1#x2# . . . #xn# . . .} Notese que L = G(M) es finito a no ser que M no pare nunca Todo lenguaje recursivo puede ser generado por una máquina de Turing en orden lexicográfico.

• M.T RESTRINGIDAS.

Se pueden imponer ciertas restricciones a la TM y de todos modos mostrar que aceptan el mismo lenguaje. 

3.1. TM con cinta semi-infinita La cinta es infinita en un sentido, la cadena de entrada se coloca al principio de la cinta la cual no continua a la izquierda. Tambi´en se incluye la restricci´on de no poder escribir B (blank) en la cinta. 10 Se puede demostrar que un TM normal se puede simular con una TM semiinfinita usando dos caminos, uno que simula la cinta a la izquierda de la cadena de entrada y otro que simula la otra parte de la cinta. X0 X1 X2 . . . ∗ X−1 X−2 . . . Los estados en la TM semi-infinita son los que tiene la TM original junto con U o L para representar arriba (U) o abajo (L), adem´as de un par de estados para preparar la TM semi-infinita. Las transiciones en la cinta de arriba son iguales a las de la TM original, y las de abajo son contrarias (si la TM original se mueve a la derecha, la TM semi-infinita inferior se mueve a la izquierda y al rev´es, si se mueve a la izquierda la TM original la otra se mueve a la derecha). S´olo se tiene que tener cuidado en las situaciones en donde se cambia de un camino al otro. 

3.2. M´aquinas multistack Podemos pensar en una generalizaci´on de los PDAs cuando consideramos varios stacks. Una m´aquina de k-stacks es un PDA determinista con k stacks. Un movimiento en esta m´aquina, cambia el estado y reemplaza el s´ımbolo de arriba de cada stack con una cadena normalmente diferente para cada stack. La transici´on ser´ıa: δ(q, a, X1, X2, . . . , Xk) = (p, γ1, γ2, . . . , γk). Donde en estado q con Xi hasta arriba de cada uno de los i = 1, 2, . . . , k stacks, se consume el s´ımbolo a y se reemplaza cada Xi por γi . Se puede demostrar que un PDA con 2 stacks puede simular una TM. En la demostraci´on se asume que al final de la cadena de entrada existe un s´ımbolo especial que no es parte de la entrada. Lo primero que se hace es que se copia la cadena al primer stack, se hace pop de este stack y push en el segundo stack, con esto el primer elemento de la 11 cadena de entrada est´a hasta arriba del segundo stack, y luego se empiezan a simular las transiciones de estados. El primer stack vac´ıo nos representa todos los blanks a la izquierda de la cadena de entrada y en general lo que est´a a la izquierda de donde apunta la cabeza de la cinta de la TM. Si TM reemplaza X por Y y se mueve a la derecha, PDA introduce (pushes) Y en el primer stack y saca (pops) X del segundo ’emphstack. Si TM reemplaza X por Y y se mueve a la izquierda, PDA saca (pops) el primer elemento del primer stack (digamos Z) y reemplaza X por ZY en el segundo stack. 

3.3. M´aquinas contadoras (counter machines) Una m´aquina contadora tiene la misma estructura que una m´aquina multistack, s´olo que en lugar de stacks tiene contadores. Un contador tiene alg´un entero positivo y s´olo puede distinguir entre 0 (cero) o un contador diferente de cero. En cada movimiento, cambia de estado y suma o resta 1 del contador (que no puede volverse negativo). Tambi´en podemos verlo como una m´aquina multistack restringida que tiene dos s´ımbolos de stack Z0 (marca el fondo) y X. El tener XiZ0 nos identifica al contador i. Se puede demostrar que los lenguajes aceptados por una m´aquina de un contador son los CFL. Se puede demostrar que cualquier lenguaje recursivamente enumerable puede ser aceptado por una m´aquina de dos contadores. 

BIBLIOGRAFIA

https://ccc.inaoep.mx/~carranza/material/IntroMaquinasTuring.pdf

https://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing#Definici.C3.B3n_formal

http://users.dsic.upv.es/asignaturas/eui/alc/MTuring.pdf

A CONTINUACIÓN UN VÍDEO QUE EXPLICA UN POCO RESUMIDO EL TEMA............