Maquina de turing

|MAQUINA DE TURING |AUTOMATA DE PILA |
|Es un autómata que se mueve sobre una secuencia lineal de datos |Es un tipo de maquina teoría, que recibe una cadena |
|Existen diversas “variedades” de una maquina de Turing. |constituida por símbolos de un alfabeto,determina si esa |
| |cadena pertenece a dicho lenguaje que el autómata debe |
|Tiene una cinta de entrada y un mecanismo de control que puede |reconocer para aceptarlo. |
|encontrarse en uno entre un numero finitos de estados. Un estado se ||
|asigna como inicial, ya otro se le asigna un estado final (aceptación).|Solo puede leer un solo dato de la secuencia generalmente un |
| |carácter y realiza ciertas acciones en base a una tabla. |
|Hacen posibles el cambio de estados del autómata cada vez que se recibe||
|un carácter de la cinta de entrada, es posible realizar un cambio de |Existe la posibilidad de escribir nuevos datos en la |
|estado y al leer el ultimo carácter del alfabeto introducido de la |secuencia. |
|cadena debe permanecer en el estado final (aceptación) elautómata o |Recorrer la secuencia en ambos sentidos. |
|mecanismo de control indica que la cadena es aceptada por el autómata. |Combinar de estados entre un conjunto finito de estados |
| |posibles. |
|El mas simple debe cumplir:| |
|Un cabezal de lectura y escritura. |Debe tener los siguientes puntos: |
|Tiene una cinta sobre la cual puede desplazarse de izquierda a derecha.|Por ello es necesario que tenga los siguientes puntos: |
|La cinta contiene una seriede celdas y en ellas se escribe un símbolo |Insertar un símbolo en la pila |
|el cual es llamado el alfabeto de la maquina, o su valor puede ser nulo|Pasar a un nuevo estado |
|(representado por “0” o “#”) |Leer un símbolo de entrada |
|Puedecontener tantas celdas sean necesarias para la izquierda así como|Extraer un símbolo de la pila |
|la derecha. | |
| |En los modelos didácticos computarizados la tabla suele|
|Es representado por las siguientes letras; |definirse mediante una matriz de 5 columnas que contiene: |
|{p,x,s,q,y} |Estado |
|Donde: |Carácter leído|
|p=representa el estado actual |Carácter a escribir |
|s= el símbolo que es extraído de la pila |Movimiento |
|q=la cantidad de estados en el autómata |Nuevo estado...