Originalmente fue definida por el matemático inglés Alan Turing como una «máquina automática» en 1936 en la revista Proceedings of the London Mathematical Society[nota 1].
[3][4] Turing dio una definición sucinta del experimento en su ensayo de 1948, «Máquinas inteligentes».
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.
Alan Turing introdujo el concepto de máquina de Turing en el trabajo On computable numbers, with an application to the Entscheidungsproblem, publicado por la Sociedad Matemática de Londres en 1936, en el que se estudiaba la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método definido que pueda aplicarse a cualquier sentencia matemática y que nos diga si esa sentencia es cierta o no.
Turing ideó un modelo formal de computador, la máquina de Turing, y demostró que existían problemas que una máquina no podía resolver.
En el artículo original («Sobre números computables con una aplicación al Entscheidungsproblem»), Turing no imagina un mecanismo, sino una persona a la que él llama la «computadora», quien ejecuta servilmente estas reglas mecánicas deterministas (o como Turing pone, «de una manera desganada»).
Una máquina de Turing[10] es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma.
La máquina va leyendo una celda de la cinta en cada paso, borrando el símbolo en el que se encuentra posicionado su cabezal y escribiendo un nuevo símbolo perteneciente al alfabeto de salida, para luego desplazar el cabezal a la izquierda o a la derecha (solo una celda a la vez).
Esto se repite según se indique en la función de transición, para finalmente detenerse en un estado final o de aceptación, representando así la salida.
Una máquina de Turing con una sola cinta puede definirse como una 7-tupla donde:[11] Existe en la literatura un abundante número de definiciones alternativas, pero todas ellas tienen el mismo poder computacional, por ejemplo se puede añadir el símbolo
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».
Por ejemplo, para la máquina de Turing con las transiciones La descripción instantánea para la cinta 1011 es: Definimos una máquina de Turing sobre el alfabeto
La máquina comenzará su proceso situada sobre un símbolo «1» de una serie.
, reemplaza el primer 1 con un 0, y pasa al estado
, con este estado avanza saltando los 1 hasta encontrar otro 0 (la primera vez no habrá ningún 1).
Una razón para aceptar la máquina de Turing como un modelo general de cómputo es que el modelo que hemos definido anteriormente es equivalente a muchas versiones modificadas que en principio pareciera incrementar el poder computacional.
significa «permanecer» o «esperar», es decir no mover el cabezal de lectura/escritura.
Por ejemplo, la cinta de la figura tiene cada celda subdividida en tres subceldas.
Una MT multidimensional es aquella cuya cinta puede verse como extendiéndose infinitamente en más de una dirección, el ejemplo más básico sería el de una máquina bidimensional cuya cinta se extendería infinitamente hacia arriba, abajo, derecha e izquierda.
En la modificación bidimensional de MT que se muestra en la figura también se agregan dos nuevos movimientos del cabezal {U,D} (es decir arriba y abajo).
Para simplificar la codificación, suponemos que toda MT tiene un único estado inicial denotado por
-ésima transición de M. Puesto que el orden en que se representen las transiciones de una MT no es relevante, una misma MT tiene varias codificaciones diferentes.
Esto no representa ninguna desventaja práctica o conceptual ya que no se pretende que las codificaciones sean únicas.
Sin embargo, muchas de sus posibilidades son indecidibles, pues no admiten una solución algorítmica.
En general, se puede demostrar que cualquier cuestión no trivial sobre el comportamiento o la salida de una máquina de Turing es un problema indecidible.
La posición del cabezal se representa con una variable entera.
Dos modelos matemáticos equivalentes a los de las máquinas de Turing son las máquinas de Post, creadas en forma paralela por Emil Leon Post,[13] y el cálculo lambda, introducido por Alonzo Church y Stephen Kleene en los años 1930, y también usado por Church para demostrar en 1936 el Entscheidungsproblem.