En términos simples, uno puede pensar en una máquina de Turing como una caja negra que recibe una cadena de caracteres, la procesa de alguna manera y devuelve si acepta o rechaza la entrada.
Esto puede parecer extraño al principio, pero es común en lenguajes de bajo nivel como C, C++ o incluso bash script. Cuando escribimos código en uno de estos lenguajes, a menudo devolvemos 0 al final de nuestro script para indicar una ejecución exitosa. Es posible que en su lugar devuelva un 1 en caso de un error genérico.
#include <stdio.h>int main()
{
printf("Hello World!");
return 0;
}
Estos valores luego pueden ser verificados por el sistema operativo u otros programas. Los lenguajes de programación también permiten la devolución de números mayores que 1 para especificar un tipo particular de error, pero la esencia general sigue siendo la misma. En cuanto a lo que significa que una máquina acepte o rechace una determinada entrada, eso depende totalmente de quien la diseñó.
Detrás de la cortina, la máquina se compone de dos componentes centrales: un bloque de control y una cinta. La cinta es infinito y corresponde a la memoria del modelo. El bloque de control puede interactuar con la cinta a través de un cabezal móvil que Puede leer y escribir en la cinta.. La cabeza puede moverse hacia la izquierda y hacia la derecha a través de la cinta. Puede ir infinitamente hacia la derecha, pero no puede ir más hacia la izquierda que el elemento inicial de la cinta, ya que la cinta solo se expande indefinidamente hacia un lado.
Al principio, la cinta está vacía, llena sólo de símbolos en blanco (⊔). Cuando la máquina lee la cadena de entrada, se coloca en la parte más izquierda de la cinta. El cabezal también se mueve a la posición más a la izquierda, lo que permite que la máquina comience a leer la secuencia de entrada desde allí. En el bloque de control se define cómo se lee la entrada, si se escribe sobre ella y cualquier otro detalle de implementación.
El bloque de control está formado por un conjunto de estados interconectados por una función de transición. Las transiciones definidas en la función de transición especifican cómo moverse entre estados dependiendo de lo que se lee de la cinta, así como qué escribir en ella y cómo mover su cabeza.
En la transición anterior, el primer término se refiere a lo que se lee en la cinta. Siguiendo la flecha, se escribirá el siguiente término en la cinta. La cinta no sólo permite escribir en ella cualquiera de los caracteres de la entrada, sino que también permite el uso de símbolos adicionales presentes sólo en la cinta. Después de la coma, el último término es la dirección en la que se mueve la cabeza: R significa correcto y l significa izquierda.
El siguiente diagrama describe el funcionamiento interno de una máquina de Turing que acepta cualquier cadena de al menos 2 de longitud que comience y termine con 0, con una cantidad arbitraria de 1 en el medio. Las transiciones se colocan junto a flechas que apuntan de un estado a otro. Cada vez que la máquina lea un carácter de la cinta, comprobará todas las transiciones que salen de su estado actual. Luego, pasa a lo largo de la flecha que contiene ese símbolo al siguiente estado.
La máquina de Turing tiene 3 estados especiales: a a partir deun aceptacióny un rechazo estado. El estado inicial se indica en el diagrama mediante una flecha que solo conecta en un extremo y, como su nombre indica, es el estado en el que arranca la máquina. Los 2 estados restantes son igualmente sencillos: si la máquina llega al estado de aceptación, acepta la entrada, y si llega al estado de rechazo, la rechaza. Tenga en cuenta que También puede repetirse eternamente, sin llegar a ninguno de ellos..
El diagrama utilizado fue el de una máquina determinista de Turing. Eso significa que cada estado tuvo una transición dejándola para cada símbolo posible que haya leído de la cinta. En una máquina de Turing no determinista, este no sería el caso. Es una de las muchas variaciones de la máquina de Turing. Algunos pueden adoptar más de una cinta, otros pueden tener una “impresora” adjunta, etc. Lo único que hay que tener en cuenta con las variaciones del modelo es que todos son equivalentes en términos de potencia. Es decir, cualquier cosa que cualquier variación de la máquina de Turing pueda calcular también puede calcularse mediante el modelo determinista.
La siguiente imagen es de un modelo físico simple de una máquina de Turing construida por Mike Davey. Tiene una cinta que puede moverse hacia la izquierda o hacia la derecha mediante dos motores giratorios y en su centro se encuentra un circuito que puede leer y escribir en la cinta, capturando perfectamente el concepto de Turing.
