La máquina de Turing

La máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo con una tabla de reglas. De una manera muy simple, que puedes ser adaptada para la simulación lógica de algoritmos de  un computador que le es útil para diversas funciones del CPU. El termino máquina automática fue definida por el matemático Alan Turing en 1936 , la máquina Turing no es un diseño como tecnología de computación práctica sino como dispositivo hipotético que representa la máquina de computación. Las máquinas de Turing ayudan a los científicos a entender los límites del cálculo mecánico.

En una cinta infinita que está marcada con cuadros se guarda memoria que se ejemplifica con símbolos, de los cuales puede ser alterado así como su comportamiento de manera individual y así no afecta a los otros símbolos en la parte de la cinta.

Sin embargo, la cinta se puede mover hacia adelante y hacia atrás a través de la máquina, siendo esto una de las operaciones elementales de la máquina. Por lo tanto cualquier símbolo en la cinta puede tener finalmente una oportunidad.

La importancia de la máquina de Turing en la historia de la computación es doble: primero, la máquina de Turing fue uno de los primeros modelos teóricos para las computadoras, viendo la luz en 1936. Según sus propiedades abstractas, la máquina de Turing ha servido de base para mucho desarrollo teórico en las ciencias de la computación y en la teoría de la complejidad. Una razón para esto es que las máquinas de Turing son simples, y por tanto amenas al análisis. Dicho esto, cabe aclarar que las máquinas de Turing no son un modelo práctico para la computación en máquinas reales, las cuales precisan modelos más rápidos como los basados en RAM.

El funcionamiento de la máquina de Turing consiste 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.

Visualización de una máquina de Turing, en la que se ve el cabezal y la cinta que se lee.

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) {\displaystyle \rightarrow }\rightarrow  (nuevo estado, nuevo valor, dirección)

Esta tabla toma como parámetros el estado actual de la máquina y el carácter leído de la cinta, dando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a escribir en la cinta.

La memoria es la cinta de la máquina que se divide en espacios de trabajo denominados celdas, donde se pueden escribir y leer símbolos. Inicialmente todas las celdas contienen un símbolo especial denominado “blanco”. Las instrucciones que determinan el funcionamiento de la máquina tienen la forma, “si estamos en el estado x leyendo la posición y, donde hay escrito el símbolo z, entonces este símbolo debe ser reemplazado por este otro símbolo, y pasar a leer la celda siguiente, bien a la izquierda o bien a la derecha”.

...