¿Qué es?, Definición y Uso

¿Qué es?

La máquina es un módulo de reconocimiento de lenguaje más general que cualquier autómata finito y de pila, pues tiene la capacidad de reconocer los lenguajes regulares y, los independientes de contexto, además de muchos otros tipos de lenguajes.

·     Definición

Es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo con 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.

·   Uso

La máquina de Turing ha sido utilizada como:

• Generadora de lenguajes, pues este tipo de máquina posee varias cintas incluyendo una cinta de salida que al inicio está vacía y luego se va llenando con palabras de lenguaje.

• En compiladores I y II, máquinas de estado, máquinas autómatas y generadores de códigos.

• En la antigüedad fue utilizado en máquinas como la “Bombe” para poder descifrar señales cifradas por la máquina alemana “enigma” durante la Segunda Guerra Mundial. También en las máquinas “colossus” que descifraban los mensajes cifrados interceptados en las comunicaciones de los nazis.