Page 38 - 06 Turing

programa, lo que se conoce como estructura de datos, proponiendo
una de las expresiones más célebres heredera del trabajo de Turing:
algoritmo+ estructura de datos = programa.

OTRAS MÁQUINAS DE TURING

En 1982, el premio Nobel de Física Richard Feynman (1918-1988)
planteó una cuestión realmente apasionante y que volverá a ser tra-
tada en el último capítulo. Predijo la clase de problemas que no
podrían ser tratados jamás con un ordenador, tras encontrar una
limitación en la capacidad computacional de las máquinas de Tu-
ring, además del denominado problema de la parada, que tratare-
mos en .el siguiente apartado. Feynman propuso que tanto las
máquinas de Tuling como los ordenadores en general no podían ser
aplicados a la simulación de fenómenos de naturaleza cuántica, es
decir, los que se observan en los átomos y para los que la física clá-
sica es insuficiente. Con esto quería decir que un fenómeno cuántico
es no computable y, por tanto, no podía ser tratado con un ordena-
dor convencional. Para que esto fuera posible, según Feynman, una
máquina de Turing tendría que ser capaz, entre otras peculiaridades,
de estar en varios estados simultáneamente o leer al mismo tiempo
varias celdas de la cinta. Extrapolando estas características a un
ordenador actual, el ordenador en cuestión tendría que poder mani-
pular, además de los estados O o 1, posibles «estados intermedios»
entre O y 1, y leer «a la vez» varios registros de la memoria RAM. No
obstante, una vez propuesto el límite en la aplicación de la máquina
de Turing, otro físico, el anglo-israelí David Deutsch (n. 1953), intr<>-
dujo en 1985 una nueva clase de máquina de Turing con la que esta
limitación quedaría definitivamente superada, la máquina de Turing
cuántica. Los ordenadores cuánticos podrían simular problemas no
computables, como son los fenómenos cuánticos, y, obviamente,
tendrían numerosas aplicaciones en el mundo real.
Además de la máquina original introducida por Turing y de su
versión cuántica, otros diseños han sido propuestos. Por ejemplo,
es posible construir una máquina de Turing policefálica, es decir,

38 WUÉ ES UN ORDENADOR?