Maquina De Turing
Páginas: 2 (481 palabras)
Publicado: 2 de diciembre de 2012
ng
MAQUINA DE TURING
¿Qué es y su funcionamiento?
Es un dispositivo de reconocimientos de lenguajes, es más general que cualquiera de los autómatas finito (AF) y los autómatas de pila (AP),debido a que las maquinas pueden reconocer tanto los lenguajes regulares, como lenguajes independientes de contexto y muchos otros lenguajes.
Una Maquina de Turing (MT) puede considerarse comouna cinta infinita dividida en casillas, donde cada una de ellas contiene un símbolo. Sobre dicha cinta actúa un dispositivo que puede adoptar diversos estados y que en cada instante, lee un símbolo dela casilla sobre la que está situado.
En función del símbolo que ha leído y del estado que se encuentre, realiza tres acciones que son:
• Pasa a un nuevo estado.
• Imprime unsímbolo en lugar del que acaba de leer
• Se desplaza una posición hacia la izquierda, o hacia la derecha, o bien la maquina se para.
El funcionamiento de una maquina de Turing puede representarsemediante una tabla de doble entrada. Las filas están encabezadas por los estados, las columnas por los símbolo es escritos en la cinta. En cada posición de la tabla hay tres elementos: el estadosiguiente, el símbolo que escribe la cinta y el movimiento de la cabeza (I, D, P), también puede haber posiciones en blanco.
[pic]
En las casillas de la cinta de esta máquina de Turing puede habertres símbolos: 0,1, o la casilla puede estar en blanco (lo que se representa en la tabla con la letra b).
Se observa en la tabla:
• Estado P: mientras se encuentra el símbolo 0, lo ignora yavanza a la izquierda. En cuanto encuentra el símbolo 1 lo sustituye por cero, pasa al estado q y avanza a la derecha. Si encuentra una casilla en blanco, pasa al estado t y avanza hacia la derecha.• Estado q: mientras encuentra los símbolos 0 y 1, los ignora y avanza hacia la derecha. En cuanto encuentra un blanco, escribe un cero, pasa al estado p y avanza a la izquierda. Su función...
MAQUINA DE TURING
¿Qué es y su funcionamiento?
Es un dispositivo de reconocimientos de lenguajes, es más general que cualquiera de los autómatas finito (AF) y los autómatas de pila (AP),debido a que las maquinas pueden reconocer tanto los lenguajes regulares, como lenguajes independientes de contexto y muchos otros lenguajes.
Una Maquina de Turing (MT) puede considerarse comouna cinta infinita dividida en casillas, donde cada una de ellas contiene un símbolo. Sobre dicha cinta actúa un dispositivo que puede adoptar diversos estados y que en cada instante, lee un símbolo dela casilla sobre la que está situado.
En función del símbolo que ha leído y del estado que se encuentre, realiza tres acciones que son:
• Pasa a un nuevo estado.
• Imprime unsímbolo en lugar del que acaba de leer
• Se desplaza una posición hacia la izquierda, o hacia la derecha, o bien la maquina se para.
El funcionamiento de una maquina de Turing puede representarsemediante una tabla de doble entrada. Las filas están encabezadas por los estados, las columnas por los símbolo es escritos en la cinta. En cada posición de la tabla hay tres elementos: el estadosiguiente, el símbolo que escribe la cinta y el movimiento de la cabeza (I, D, P), también puede haber posiciones en blanco.
[pic]
En las casillas de la cinta de esta máquina de Turing puede habertres símbolos: 0,1, o la casilla puede estar en blanco (lo que se representa en la tabla con la letra b).
Se observa en la tabla:
• Estado P: mientras se encuentra el símbolo 0, lo ignora yavanza a la izquierda. En cuanto encuentra el símbolo 1 lo sustituye por cero, pasa al estado q y avanza a la derecha. Si encuentra una casilla en blanco, pasa al estado t y avanza hacia la derecha.• Estado q: mientras encuentra los símbolos 0 y 1, los ignora y avanza hacia la derecha. En cuanto encuentra un blanco, escribe un cero, pasa al estado p y avanza a la izquierda. Su función...
Leer documento completo
Regístrate para leer el documento completo.