Máquina de Turing: Fundamentos, Componentes y Operación
Clasificado en Informática
Escrito el en 
español con un tamaño de 2,95 KB
Máquina de Turing
¿Qué es y cómo funciona la Máquina de Turing?
Es un dispositivo de reconocimiento de lenguajes, más general que cualquier autómata finito y cualquier autómata de pila, debido a que puede reconocer tanto los lenguajes regulares, como los lenguajes independientes de contexto y, además, muchos otros tipos de lenguajes.
¿Por qué es importante la Máquina de Turing?
Cualquier modelo de computación que intente capturar el concepto de "lo que es computable" debe ser equivalente a la Máquina de Turing.
Definición de la Máquina de Turing
Es un modelo computacional que realiza una lectura/escritura automática sobre una entrada llamada cinta, generando una salida en esta misma.
Componentes de una Máquina de Turing
Una Máquina de Turing está formada por:
- Un alfabeto de entrada
- Un alfabeto de salida
- Un símbolo especial llamado blanco (normalmente b, Δ o 0)
- Un conjunto de estados finitos
- Un conjunto de transiciones entre dichos estados.
Funcionamiento Formal de la Máquina de Turing
Se basa en una función de transición, que recibe un estado inicial y una cadena de caracteres del alfabeto de entrada (la cinta, que puede ser infinita). La máquina lee una celda a la vez, borra el símbolo que acaba de leer y escribe un nuevo símbolo del alfabeto de salida. Luego, se desplaza a la izquierda o derecha (una celda a la vez). Este proceso se repite según indique la función de transición, para finalmente detenerse en un estado final o de aceptación, representando así la salida.
Funcionamiento Detallado
La Máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:
- Mover el cabezal lector/escritor hacia la derecha
- Mover el cabezal lector/escritor hacia la izquierda.
El cómputo se determina a partir de una tabla de estados de la forma:
(estado, valor) → (nuevo estado, nuevo valor, dirección)
Representación de la Máquina de Turing
Las Máquinas de Turing se pueden representar mediante grafos particulares, también llamados diagramas de estados finitos, de la siguiente manera: