1. 6.1 Definicion formal MT
1.1. 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.
1.2. 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.
1.3. 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:
1.4. ¿Por qu´e creemos que las m´aquinas de Turing son una buena formalizaci´on del concepto de algoritmo? ◮ Porque cada programa de una m´aquina de Turing puede ser implementado ◮ Porque todos los algoritmos conocidos han podido ser implementados en m´aquinas de Turing ◮ Porque todos los otros intentos por formalizar este concepto fueron reducidos a las m´aquinas de Turing ◮ Los mejores intentos resultaron ser equivalentes a las m´aquinas de Turing ◮ Todos los intentos “razonables” fueron reducidos eficientemente ◮ Tesis de Church: Algoritmo = M´aquina de Turing
2. 6.2 Construccion Modular de una MT
2.1. El objetivo de la creación modular de una maquina de Turing es poder desarrollar máquinas complejas a partir de bloques elementales, a partir de maquinas más pequeñas, mediante diagramas de transiciones. La construcción de máquinas de Turing se lleva a cabo mediante los diagramas de transición y combinarlos de manera parecida a lo que se realiza en la formación de la unión y concatenación de los autómatas finitos.
2.2. Pasos para la construcción de una máquina de Turing: 1. Elimine las características de inicio de los estados iniciales de las maquinas, excepto la de aquel donde iniciara la maquina compuesta. 2. Elimine las características de detención de los estados de parada de todas la maquinas e introduzca un nuevo estado de parada que nos se encuentre en ninguno de los diagramas que se combinan. 3. Para cada uno de los antiguos estados de parada p y cada x en y.
2.2.1. Un sistema Turing completo es aquel que puede simular el comportamiento de una máquina de Turing. Es evidente que salvando los problemas de memoria, los ordenadores modernos y los lenguajes de programación de uso general, son sistemas de Turing completos. También es evidente, que con independencia de su forma concreta, cualquier dispositivo que se comporte como un sistema de Turing completo, puede en principio ejecutar cualquier cálculo que realice cualquier computador.
2.2.2. Una máquina de Turing es un autómata que se mueve sobre una secuencia lineal de datos. En cada instante la máquina puede leer un solo dato de la secuencia (generalmente un carácter) y realiza ciertas acciones en base a una tabla que tiene en cuenta su "estado" actual (interno) y el último dato leído. Entre las acciones está la posibilidad de escribir nuevos datos en la secuencia; recorrer la secuencia en ambos sentidos y cambiar de "estado" dentro de un conjunto finito de estados posibles.
3. 6.3 Lenguanjes aceptados por la MT
3.1. De acuerdo a la clasificación de los lenguajes formales realizada por el norteamericano Avram Chomsky, la Máquina de Turing acepta los lenguajes más generales, o tipo cero (0), también llamados lenguajes recursivamente enumerables.
3.2. Un lenguaje recursivamente enumerable es un lenguaje formal para el cual existe una máquina de Turing que acepta y se detiene con cualquier cadena del lenguaje, pero que puede parar y rechazar, o bien iterar indefinidamente, con una cadena que no pertenece al lenguaje. Todos los lenguajes, regulares, independientes de contexto, dependientes de contexto y recursivos son recursivamente enumerables.
3.3. Los lenguajes formales que son aceptados por una máquina de Turing son exactamente aquellos que pueden ser generados por una gramática formal. El cálculo Lambda es una forma de definir funciones. Las funciones que pueden se computadas con el cálculo Lambda son exactamente aquellas que pueden ser computadas con una máquina de Turing. Estos tres formalismos, las máquinas de Turing, los lenguajes formales y el cálculo Lambda son formalismos muy disímiles y fueron desarrollados por diferentes personas. Sin embargo, ellos son todos equivalentes y tienen el mismo poder de expresión. Generalmente se toma esta notable coincidencia como evidencia de que la tesis de Church-Turing es cierta, que la afirmación de que la noción intuitiva de algoritmo o procedimiento efectivo de cómputo corresponde a la noción de cómputo en una máquina de Turing.
3.3.1. Los computadores electrónicos, basados en la arquitectura Von Neumann así como las máquinas cuánticas tendrían exactamente el mismo poder de expresión que el de una máquina de Turing si dispusieran de recursos ilimitados de tiempo y espacio. Como consecuencia, los lenguajes de programación tienen a lo sumo el mismo poder de expresión que el de los programas para una máquina de Turing y en la práctica no todos lo alcanzan. Los lenguajes con poder de expresión equivalente al de una máquina de Turing se denominan Turing completos.