¿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.
El concepto de máquina de Turing
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.
