Modelo abstracto de máquina automática para la resolución de problemas ideada por Alan Turing en 1936, para precisar el concepto de algoritmo. Con esta máquina se establecieron las bases de los modernos ordenadores digitales. La máquina de Turing es un modelo computacional formado por una máquina de estados finitos, una cabeza de lectura/grabación, y una cinta secuencial ilimitada. Dependiendo del estado actual y del símbolo leído en la cinta, la máquina puede cambiar su estado y mover el cabezal a la izquierda o la derecha. Salvo indicación en contra, una máquina de Turing es determinista.