La máquina de Turing no es un objeto físico, sino un artificio matemático que nos proporciona un modelo de computación en el cual encuadramos el análisis de nuestros algoritmos. Es preciso decir que hay otros modelos igualmente válidos, pero no tan comunes en la literatura. Destacamos las máquinas de acceso aleatorio, mucho más realistas que la máquina de Turing en el sentido que emulan en su estructura un ordenador real. Todos los modelos son equivalentes, pero la máquina de Turing tiene un carácter más elemental que hace más sencillo comprender su aplicación en el estudio de algoritmos.
Una máquina de Turing consiste en un cabezal de lectura/escritura por el cual pasa una cinta infinita que puede moverse hacia adelante y hacia atrás. La cinta se encuentra dividida en casillas que pueden estar vacías o llevar un símbolo de un determinado alfabeto. De hecho, con un solo símbolo (además de la posibilidad de dejar la casilla vacía) es suficiente, ya que cualquier otro alfabeto lo podríamos expresar en secuencias de este símbolo y casillas vacías.
El cabezal se encuentra en cada instante en un estado concreto de entre un número finito de estados posibles diferentes. La máquina funciona paso a paso y cada uno de los pasos consiste en situar el cabezal delante de una casilla, y después de leer el contenido de la casilla, realizar de acuerdo con el resultado de la lectura y el estado interno de la máquina, las tres acciones siguientes: borrar la casilla y dejarla vacía, o bien, escribir un símbolo que puede ser el mismo que había antes, pasar a un nuevo estado (que puede ser el mismo) y finalmente mover la cinta a una casilla de una de las dos direcciones posibles, o bien, acabar el cómputo. La conducta global de la máquina viene determinada por un conjunto de instrucciones, las cuales indican, para cada posible estado y símbolo leído, las tres acciones que es preciso hacer. Si se han de dar datos iniciales, éstos se escriben en la cinta de acuerdo con el sistema de codificación considerado. El cabezal se sitúa en la casilla inicial y, una vez se acaba el cómputo, la máquina entra en un estado especial de parada y deja de funcionar. La posible respuesta se encontrará escrita en la misma cinta a partir de la posición donde se encuentra el cabezal. cada instrucción se puede representar con una quíntupla (ea, sa, ed, sd, m) donde ea indica el estado de la máquina cuando se lee el símbolo sa, y ed es el estado de la máquina después de dejar escrito el símbolo sd en la casilla procesada y mover la cinta a la derecha o la izquierda según indica m.
Ya que tanto el conjunto de estados como el de símbolos es finito, cualquier cómputo puede ser especificado completamente por un conjunto finito de quíntuplas. Supongamos también que el cómputo es determinístico en el sentido que, dados el estado de la máquina y el símbolo de la cinta antes de cualquier acción, existe una quíntupla que determina el nuevo estado de la máquina, el símbolo a escribir en la cinta y el movimiento que debe hacer, Se suele decir entonces que la máquina de Turing es determinista.
Gracias a la máquina de Turing, un algoritmo puede ser definido de forma precisa como una secuencia de instrucciones que determina totalmente la conducta de la máquina para la resolución del problema considerado. La hipótesis de Church-Turing dice que todo algoritmo puede ser descrito (o implantado) en una máquina de Turing.
