Máquina de Turing: ¿Qué Es?, ¿Cómo Funciona?, e Importancia
Una máquina de Turing es un modelo computacional abstracto de un dispositivo capaz de realizar cualquier tipo de algoritmo de acuerdo a un conjunto de reglas predefinidas mediante el uso de una cinta de longitud infinita… Pero, ¿qué significa todo esto?
Nota: Para este artículo se utiliza la definición informal de una MT.
¿Cómo Funciona una Máquina de Turing?
Para entender cómo funciona una máquina de Turing es necesario entender ciertos conceptos; en primer lugar, estas máquinas consisten en una cinta, un cabezal, un registro de estado y una tabla de instrucciones.
La cinta es una serie de casillas de longitud bilateral (o unilateral) infinita que actúa como la memoria/almacenamiento de la máquina de Turing. Cada casilla está prevista para almacenar uno o más símbolos de un alfabeto finito o permanecer en blanco hasta su inminente lectura/escritura. Por otro lado, el cabezal lee y escribe datos a lo largo de la cinta, una sola casilla a la vez.
Nota: Cuando se habla de un alfabeto finito, se refiere a la cantidad de símbolos adecuados para realizar una función en una MT, es decir, si el alfabeto es binario, la máquina solo utilizará un alfabeto con dos símbolos (0 y 1).
El registro de estado es una forma de almacenar cada estado posible en una máquina de Turing, es decir, almacena todas las configuraciones posibles que puede ejecutar la máquina; entre estas, se encuentra el estado de inicio especial con que se inicializa el registro de estado. La tabla de instrucciones específica como la MT debe comportarse según el símbolo que esté leyendo el cabezal de lectura/escritura y en qué estado se encuentra la máquina.
Nota: En algunos conceptos de MT, es la cinta que se mueve mientras el cabezal se queda inmóvil.
¿Cómo se Lee/Escriben Datos en una Máquina de Turing?
Una máquina de Turing lee y escribe datos a través del cabezal de lectura/escritura, que, dependiendo del símbolo que se esté leyendo en la casilla actual y el estado en que se encuentra la máquina, consultará la tabla de instrucciones para determinar la acción siguiente a tomar, es decir, si borra o escribe un símbolo en la casilla actual, si mueve el cabezal hacia la izquierda o la derecha, o si asume el mismo o un estado diferente. Este proceso de lectura, escritura y movimiento del cabezal se repite hasta que la MT alcanza un estado de aceptación o rechazo.
Ejemplo de un Programa en una Máquina de Turing
Para este ejemplo, utilizaremos un alfabeto binario, es decir, 0s y 1s, y la máquina posee los siguientes tres estados: E0 (estado inicial), E1 (estado de procesamiento) y E2 (estado de aceptación).
La máquina de Turing inicia en el estado E0. Si la casilla de la cinta tiene un símbolo “0”, el cabezal procederá a escribir un “1”, moverse a la derecha y cambiar el estado de la máquina a E1. En el caso de leer un “1”, el cabezal procederá a escribir “0” y cambiar el estado de la máquina a E1. Por último, si la casilla de la cinta tiene un símbolo en blanco, se mueve a la derecha y entra en el estado E2, indicando la finalización del programa.
En el caso del estado E1, si la casilla de la cinta tiene un símbolo “0”, el cabezal procede a escribir un “1”, moverse a la izquierda y permanecer en el estado E1. En el caso de leer un “1”, el cabezal procederá a escribir “0”, moverse a la izquierda y permanecer en el estado E1. Por último, si la casilla de la cinta tiene un símbolo en blanco, se mueve a la derecha y entra en el estado E2, indicando la finalización del programa.
Nota: Para un mayor entendimiento de la MT, visite el siguiente video.
¿Para qué sirven una Máquina de Turing?
Aunque es simple en su estructura y funcionamiento, la máquina de Turing es capaz de realizar cualquier algoritmo informático que sea teóricamente posible. La importancia de la misma radica en que proporciona un marco conceptual y simple para entender la teoría de la computabilidad y los fundamentos de la informática.
Tipos de Máquinas de Turing
Existen varias variantes de una máquina de Turing; aunque no son pocos, los nombres que reciben son autoexplicativos; por lo tanto, no es necesario definirlos a detalle para este artículo.
- MT de múltiples vías
- MT de cinta infinita bidireccional
- MT con cinta multidimensional
- MT Multicinta
- MT de cabezales múltiples
- MT no determinista
- MT de múltiples cabezales y cintas múltiples
