Maquinas de Turing

INFORMATICA UNIVERSIDAD

CONCLUSIÓN

Una Máquina de Turing, o MT, se considerar una cinta infinita dividida en casillas, cada una de las cuales contiene un símbolo, y sobre la cual actúa un dispositivo que puede adoptar diversos estados, y que lee un símbolo de la casilla sobre la que está situado. En función de dicho símbolo y del estado actual, se pueden realizar tres acciones siguientes: pasa a un nuevo estado, imprime un símbolo en lugar del que acaba de leer y se desplaza a una posición hacia la izquierda, derecha, o se detiene. Existen diversas clasificaciones de las Máquinas de Turing, atendiendo a los estados reconocidos, tipo de cinta, cantidad o división de dichas cintas: MT con directiva de permanecer, MT con cinta infinita en una dirección, MT en dos direcciones, MT multicinta, MT Multidimensional, MT No determinista.


Las MT, de acuerdo a la clasificación de los lenguajes formales de Chomsky, acepta los lenguajes tipo cero (0), llamados lenguajes recursivamente enumerables. La creación modular de una máquina de Turing permite desarrollar máquinas complejas a partir de bloques elementales, mediante diagramas de transiciones. La construcción de máquinas de Turing se lleva a cabo mediante dichos diagramas de transición, y sus combinaciones. Las MT han sido aplicadas en el desarrollo de la teoría computacional y en las llamadas máquinas oráculo, generadores de funciones, calculadoras de funciones, y generadores de lenguaje.

(Puede quitar la publicidad ampliando la cuenta)