¿Puede un ordenador calcular
cualquier cosa?
Al igual que Gödel en mátemáticas. Alan Turing estableció los límites de la computación, y hasta qué
punto un ordenador es capaz de calcular cualquier cosa.
Una máquina de Turing es un concepto de ordenador idealizado, es decir un
ordenador de papel y lápiz, o según lo concibió el propio Turing un
ordenador con un lector y una cinta
infinita que puede moverse hacia adelante o atrás siguiendo unas reglas
sencillas escritas en la propia cinta. A
pesar de esta gran simplicidad, una máquina de Turing se puede adaptar para ejecutar
cualquier algoritmo o programa.
Una máquina de Turing que es capaz de
simular cualquier otra máquina de Turing es llamada una máquina
universal de Turing (UTM,
o simplemente una máquina universal). Las máquinas de Turing sirven para
estudiar hasta qué punto se puede automatizar
cualquier noción de lógica o de matemáticas.