Máquina de Turing

Modelo abstracto de computación que consta de una cinta infinita (o ilimitada) dividida en celdas, una cabeza de lectura/escritura que se mueve a la izquierda o derecha, un conjunto finito de estados y una función de transición que asigna (estado actual, símbolo actual) a (estado siguiente, símbolo a escribir, movimiento de la cabeza).