La máquina de Turing

Una máquina de Turing es un autómata que se mueve sobre una secuencia lineal de

datos. En cada instante, la máquina puede leer un único dato de la secuencia (generalmente

un carácter) y realizar ciertas acciones en base a una tabla que tiene en cuenta

su estado actual (interno) y el último dato leído. Entre las acciones que puede realizar,

está la posibilidad de escribir nuevos datos en la secuencia, recorrer la secuencia en ambos

sentidos y cambiar de estado dentro de un conjunto finito de estados posibles.

Un sistema Turing completo es aquel que puede simular el comportamiento de

una máquina de Turing. Dejando de lado las limitaciones impuestas por la capacidad

de almacenamiento o la memoria, las computadoras actuales y los lenguajes de

programación de propósito general definen sistemas Turing completos.

Independientemente de su forma concreta, cualquier dispositivo que se comporte

como un sistema Turing completo puede en principio ejecutar cualquier cálculo

que realice cualquier computadora; lógicamente, esta afirmación no considera la

posible dificultad de escribir el programa correspondiente o el tiempo que pueda requerir

realizar el cálculo en cuestión.