maquina de turing
Páginas: 14 (3370 palabras)
Publicado: 11 de noviembre de 2013
UNIDAD 4
Maquinas de Turing
4.1 Definiciones Básicas
Las maquinas de Turing son mas generales que cualquier autómata finito, debido a que ellas pueden reconoces tanto lenguajes regulares como lenguajes independientes del contexto y muchos otros lenguajes.
Las maquinas de Turing constan de un mecanismo de control y un flujo de entrada que se concibe como una cinta; la diferenciaestriba en que la maquina de Turing pueden mover su cabeza de lectura hacia delante y hacia atrás y puede leer o escribir en la cinta.
El mecanismo de control de la maquina de Turing en cualquier momento puede encontrarse en un estado de entre un numero finito de estos.
Uno de estos estados se llama ESTADO INICIAL y representa el estado en el cual la maquina comienza los cálculos.
Otro deestos estados es el ESTADO DE PARADA, una vez que la maquina llega a este estado, terminan todos los cálculos, es decir la maquina se detiene al momento de llegar al estado de parada.
El estado inicial no puede ser el de parada, por lo tanto una maquina de Turing debe tener cuando menos dos estados.
La maquina de Turing esta equipada con una cabeza que puede emplearse para leer y escribir símbolosen la cinta de la maquina.
Esta cinta tiene extremos que se extiende indefinidamente a la derecha e izquierda.
Así una M. de Turing puede emplear la cinta como almacenamiento auxiliar.
Al utilizar la cinta con fines de almacenamiento auxiliar se permite que la M. de Turing lea y escriba símbolos que no aparecen en los datos de entrada; es decir maneja dos alfabetos.
El ALFABETO DEENTRADA que es un conjunto finito de símbolos en el que deben estar codificados los datos iniciales.
El ALFABETO DE CINTA, conjunto posiblemente mayor pero también finito de símbolos de cinta que la maquina puede leer o escribir.
El alfabeto de cinta puede incluir marcas especiales que no estén en el alfabeto de entrada.
Es fácil que el símbolo de espacio en blanco ocasione confusiones ymalas interpretaciones, para evitarlo adoptaremos el símbolo B para representar el espacio en blanco, por ejemplo las cadenas a b y a b las expresaremos aBb y aBBb respectivamente.
Las acciones específicas que puede realizar una M. de Turing consiste en operaciones de escritura y movimiento.
La operación de escritura consiste en remplazar un símbolo en la cinta con otro símbolo y luego cambiara un nuevo estado el cual puede ser el mismo en el que se encontraba.
La operación de movimiento comprende mover la cabeza una celda a la derecha o izquierda y luego pasar a un nuevo estado que puede ser el de partida.
La acción que se ejecutara en un momento determinado dependerá del símbolo actual, así como del estado en que se encuentre el mecanismo de control de la maquina.Una Maquina de Turing es una 7-tupla M= (Q, Σ, , s, B, F, ) donde:
Q Es el conjunto finito de estados (q1, q2, q3,……..)
Σ Es el alfabeto de entrada
Es el alfabeto de cinta (1, 2, 3,….)
s Estado inicial
B Es el símbolo de espacio en blanco y no esta en Σ.
F Estado de parada o de aceptación.
Función de transición Q x Q x x {L, R} que significan left y rightrespectivamente.
La función de transición transforma pares (q1, 1) formados por el estado actual (q1) y los símbolos (1) de la cinta, en ternas de la forma (q2, 2, X) donde q2 es el estado siguiente, 2 es el símbolo escrito en la cinta y X es el movimiento de la cabeza de lectura/escritura, que puede ser hacia la izquierda (L) o hacia la derecha (R).
Por ejemplo la transición (q1, a)=(q2, b, R) significa:
Si el estado actual es q1 y el símbolo actual es a, reemplazar el símbolo a por el símbolo b, mover la cabeza a la derecha y pasar al estado q2.
EJEMPLO 1
Sea la Maquina de Turing definida por:
Q={q1, q2 },
Σ={a, b },
={a, b, B },
F={q2 },
s={q1} y dada por (q1, a)= (q1, a, R)
(q1, b)= (q1, a, R)
(q1, B)= (q2, B, L)
Codificación de cinta...
Maquinas de Turing
4.1 Definiciones Básicas
Las maquinas de Turing son mas generales que cualquier autómata finito, debido a que ellas pueden reconoces tanto lenguajes regulares como lenguajes independientes del contexto y muchos otros lenguajes.
Las maquinas de Turing constan de un mecanismo de control y un flujo de entrada que se concibe como una cinta; la diferenciaestriba en que la maquina de Turing pueden mover su cabeza de lectura hacia delante y hacia atrás y puede leer o escribir en la cinta.
El mecanismo de control de la maquina de Turing en cualquier momento puede encontrarse en un estado de entre un numero finito de estos.
Uno de estos estados se llama ESTADO INICIAL y representa el estado en el cual la maquina comienza los cálculos.
Otro deestos estados es el ESTADO DE PARADA, una vez que la maquina llega a este estado, terminan todos los cálculos, es decir la maquina se detiene al momento de llegar al estado de parada.
El estado inicial no puede ser el de parada, por lo tanto una maquina de Turing debe tener cuando menos dos estados.
La maquina de Turing esta equipada con una cabeza que puede emplearse para leer y escribir símbolosen la cinta de la maquina.
Esta cinta tiene extremos que se extiende indefinidamente a la derecha e izquierda.
Así una M. de Turing puede emplear la cinta como almacenamiento auxiliar.
Al utilizar la cinta con fines de almacenamiento auxiliar se permite que la M. de Turing lea y escriba símbolos que no aparecen en los datos de entrada; es decir maneja dos alfabetos.
El ALFABETO DEENTRADA que es un conjunto finito de símbolos en el que deben estar codificados los datos iniciales.
El ALFABETO DE CINTA, conjunto posiblemente mayor pero también finito de símbolos de cinta que la maquina puede leer o escribir.
El alfabeto de cinta puede incluir marcas especiales que no estén en el alfabeto de entrada.
Es fácil que el símbolo de espacio en blanco ocasione confusiones ymalas interpretaciones, para evitarlo adoptaremos el símbolo B para representar el espacio en blanco, por ejemplo las cadenas a b y a b las expresaremos aBb y aBBb respectivamente.
Las acciones específicas que puede realizar una M. de Turing consiste en operaciones de escritura y movimiento.
La operación de escritura consiste en remplazar un símbolo en la cinta con otro símbolo y luego cambiara un nuevo estado el cual puede ser el mismo en el que se encontraba.
La operación de movimiento comprende mover la cabeza una celda a la derecha o izquierda y luego pasar a un nuevo estado que puede ser el de partida.
La acción que se ejecutara en un momento determinado dependerá del símbolo actual, así como del estado en que se encuentre el mecanismo de control de la maquina.Una Maquina de Turing es una 7-tupla M= (Q, Σ, , s, B, F, ) donde:
Q Es el conjunto finito de estados (q1, q2, q3,……..)
Σ Es el alfabeto de entrada
Es el alfabeto de cinta (1, 2, 3,….)
s Estado inicial
B Es el símbolo de espacio en blanco y no esta en Σ.
F Estado de parada o de aceptación.
Función de transición Q x Q x x {L, R} que significan left y rightrespectivamente.
La función de transición transforma pares (q1, 1) formados por el estado actual (q1) y los símbolos (1) de la cinta, en ternas de la forma (q2, 2, X) donde q2 es el estado siguiente, 2 es el símbolo escrito en la cinta y X es el movimiento de la cabeza de lectura/escritura, que puede ser hacia la izquierda (L) o hacia la derecha (R).
Por ejemplo la transición (q1, a)=(q2, b, R) significa:
Si el estado actual es q1 y el símbolo actual es a, reemplazar el símbolo a por el símbolo b, mover la cabeza a la derecha y pasar al estado q2.
EJEMPLO 1
Sea la Maquina de Turing definida por:
Q={q1, q2 },
Σ={a, b },
={a, b, B },
F={q2 },
s={q1} y dada por (q1, a)= (q1, a, R)
(q1, b)= (q1, a, R)
(q1, B)= (q2, B, L)
Codificación de cinta...
Leer documento completo
Regístrate para leer el documento completo.