Maquina De Turing

Máquina de Turing
La Máquina de Turing (MT) 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á 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 entredichos 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 deentrada. 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 ala 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.
Representación como diagrama deestados.
Las maquinas de Turing se pueden representar mediante grafos particulares, también llamados diagramas de estados finitos, de la siguiente manera:
Esta Máquina de Turing está definido sobre elalfabeto Σ={a,b,c}, posee el conjunto de estados Q={qo,q1,q2,q3,q4,q5,q6}, con las transiciones que se pueden ver. Su estado inicial es q1 y el estado final es q2, el lenguaje de salida
={X,Y,Z,B}siendo B el símbolo denominado Blanco . Esta Máquina reconoce la expresión regular de la forma {a^n b^n c^n,n>=0} .
* Los estados se representan como vértices, etiquetados con su nombre en elinterior.
* Una transición desde un estado a otro, se representa mediante una arista dirigida que une a estos vértices, y esta 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, proveniente de ningún otro vértice.
* El o los estados finales se representan mediante...