Una máquina de Turing es un dispositivo imaginario capaz de leer en la unidad de tiempo un carácter del código externo, modificar o no su estado interno, sustituir o no el carácter que ha sido leído por un carácter del código de salida y moverse a la derecha o a la izquierda una posición.