A Turing machine is an abstract computational model that manipulates symbols on a tape.Formalmente, una máquina de Turing consta de una cinta infinita dividida en celdas, cada una de las cuales contiene un símbolo de un alfabeto finito; un dispositivo de control con una memoria finita de estados; y un cabezal capaz de leer, escribir y desplazarse una celda. La función de transición determina, a partir del estado actual y el símbolo leído, un nuevo símbolo, la dirección de desplazamiento (I/D) y un nuevo estado. La máquina comienza con la palabra de entrada en la cinta y puede detenerse en un estado de aceptación o de rechazo, o quedar atrapada en un bucle infinito. La máquina universal de Turing puede simular cualquier otra a partir de su descripción, lo que prefigura el concepto de computadora programable.
En 1936, Alan Turing, al abordar el Entscheidungsproblem (problema de decisión) de David Hilbert, introdujo el concepto de «a-machine» (máquina automática) en su artículo «On Computable Numbers». Su objetivo era formalizar la noción intuitiva de algoritmo. De forma independiente, Alonzo Church llegó al concepto equivalente del cálculo lambda. La tesis de Church-Turing afirma que cualquier proceso intuitivamente computable puede llevarse a cabo en una máquina de Turing. En 1945, John von Neumann utilizó este modelo en la arquitectura EDVAC, precursora de las computadoras modernas. En 1985, David Deutsch propuso la máquina cuántica de Turing, abriendo el camino a la computación cuántica.
La máquina de Turing computa manipulando cadenas de símbolos. Algorítmicamente, es equivalente a un lenguaje de programación con un único array de longitud infinita. Propiedades clave: existencia de una máquina universal (intérprete), indecidibilidad del problema de parada (no se puede determinar algorítmicamente si una máquina arbitraria se detendrá con una entrada dada), teorema de recursión (la máquina puede obtener su propia descripción). En teoría de la complejidad se consideran máquinas con oráculo (que reciben información adicional) y máquinas probabilísticas (con una fuente de bits aleatorios). Las máquinas cuánticas de Turing operan con estados en un espacio de Hilbert y usan transformaciones unitarias; no violan la tesis de Church-Turing, pero pueden ofrecer una aceleración exponencial para ciertos problemas.
Cualquier programa de computadora, desde una calculadora hasta un asistente con IA, se reduce a instrucciones que una máquina de Turing puede ejecutar. En ella se basa toda la teoría de la computación.
La máquina universal de Turing más sencilla, ideada por Marvin Minsky, utiliza solamente 7 estados y 4 símbolos, y aun así es capaz de calcular todo lo que puede un potente superordenador, aunque a una velocidad terriblemente lenta.










