La Maquina De Turing
Enviado por eagc_2 • 19 de Abril de 2015 • 745 Palabras (3 Páginas) • 214 Visitas
Equipo: “Los Lefios”.
4.1 DEFINICION FORMAL DE UNA MAQUINA 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.
(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 entre dichos 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 de entrada. 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 a la 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.
Una máquina de Turing con una sola cinta puede ser definida como una 7-tupla;
donde:
es un conjunto finito de estados.
Es un conjunto finito de símbolos distinto del espacio en blanco, denominado alfabeto de máquina o de entrada.
Es un conjunto finito de símbolos de cinta, denominado alfabeto de cinta.
Es el estado inicial.
Es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.
Es el conjunto de estados finales de aceptación.
Es una función parcial denominada función de transición, donde es un movimiento a la izquierda y es el movimiento a la derecha.
La máquina de Turing puede considerarse como un autómata capaz de reconocer lenguajes formales. En ese sentido es capaz de reconocer los lenguajes recursivamente enumerarles, de acuerdo a la jerarquía de Chomsky.
Su potencia es, por tanto, superior a otros tipos de autómatas, como el autómata finito, o el autómata con pila, o igual a otros modelos con la misma potencia computacional. Las máquinas de Turing se pueden representar mediante grafos particulares, también llamados
...