M Quina De Turing
Páginas: 4 (866 palabras)
Publicado: 19 de marzo de 2015
Máquina de Turing
La Máquina de Turing (MT) fue introducida por Alan M. Turing en 1936, y puede considerarse como un modelo abstracto que formaliza la idea Intuitiva de algoritmo.
Es un modelocomputacional 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 desalida, un símbolo especial llamado blanco (normalmente b, Δ o 0), un conjunto de estados finitos y un conjunto de transiciones entre dichos estados.
Su funcionamiento se basa en una función detransición, que recibe un estado inicial y una cadena de caracteres (la cinta, la cual es finita por la izquierda) pertenecientes al alfabeto de entrada. Luego va leyendo una celda de la cinta, borrando elsímbolo, escribir el nuevo símbolo perteneciente al alfabeto de salida y finalmente avanza a la izquierda o a la derecha (solo una celda a la vez), repitiendo esto según se indique en la función detransición, para finalmente detenerse en un estado final o de aceptación, representando así la salida.
Está constituida por los siguientes elementos:
MT = (E, A, B, e0, F, f)
E =Conjunto de estados, no vacío.
A = Conjunto de símbolos de entrada.
B = Conjunto de símbolos auxiliares.
e0 = Estado inicial.
F = Conjunto de estados finales.
f = Función de control, definida:
Dónde: f:(E - F) x (A È B ) Þ E x ( A È B) x ( I, O, D )
I = movimiento del cabezal a la izquierda.
O = movimiento nulo.
D = movimiento a la derecha.
La máquina de Turing consta de un cabezallector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:Avanzar el cabezal lector/escritor para la derecha.
Avanzar el cabezal lector/escritor para la izquierda.
Construcción modular de una MT.
El objetivo de la creación modular de una máquina de...
La Máquina de Turing (MT) fue introducida por Alan M. Turing en 1936, y puede considerarse como un modelo abstracto que formaliza la idea Intuitiva de algoritmo.
Es un modelocomputacional 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 desalida, un símbolo especial llamado blanco (normalmente b, Δ o 0), un conjunto de estados finitos y un conjunto de transiciones entre dichos estados.
Su funcionamiento se basa en una función detransición, que recibe un estado inicial y una cadena de caracteres (la cinta, la cual es finita por la izquierda) pertenecientes al alfabeto de entrada. Luego va leyendo una celda de la cinta, borrando elsímbolo, escribir el nuevo símbolo perteneciente al alfabeto de salida y finalmente avanza a la izquierda o a la derecha (solo una celda a la vez), repitiendo esto según se indique en la función detransición, para finalmente detenerse en un estado final o de aceptación, representando así la salida.
Está constituida por los siguientes elementos:
MT = (E, A, B, e0, F, f)
E =Conjunto de estados, no vacío.
A = Conjunto de símbolos de entrada.
B = Conjunto de símbolos auxiliares.
e0 = Estado inicial.
F = Conjunto de estados finales.
f = Función de control, definida:
Dónde: f:(E - F) x (A È B ) Þ E x ( A È B) x ( I, O, D )
I = movimiento del cabezal a la izquierda.
O = movimiento nulo.
D = movimiento a la derecha.
La máquina de Turing consta de un cabezallector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:Avanzar el cabezal lector/escritor para la derecha.
Avanzar el cabezal lector/escritor para la izquierda.
Construcción modular de una MT.
El objetivo de la creación modular de una máquina de...
Leer documento completo
Regístrate para leer el documento completo.