UNIDAD 6
6. Máquinas de Turing. Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo a una tabla de reglas. A pesar de su simplicidad, una máquina de Turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de una CPU dentro de un computador. 6.1 Definición formal MT 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 transicio...