next up previous
Next: Hacia una interpretación física Up: Introducción Previous: Niels Henrik David Bohr

Alan Turing (1912-1954) y la Computabilidad

Pero ¿qué tiene que ver toda esta historia de la física con la computación? Para ello conviene dar un giro en el relato y recordar la memoria de Alan Turing. Alan Mathison Turing, nace en Padington Inglaterra el 23 de Junio de 1912. Segundo y último hijo de Julius Mathison y Ethel Sara Turing, en un hogar inglés de clase media alta. Desde joven muestra características excéntricas, solitarias, y geniales. Turing estudia en el King's College de Cambridge. Para 1933 Turing había desarrollado interés en la Principia Mathematica de Russell y Whitehead. En ella Bertrand Russel había ideado un programa para contestar una de las preguntas propuestas por Hilbert a inicios del siglo como reto a la matemática: formalizar todo el conocimiento matemático existente dentro de la lógica. Sin embargo, el objetivo de esta empresa fue burlado por Kurt Gödel cuando demostró en 1931 que todo sistema formal (en particular la lógica) es incompleto: para todo sistema formal, existen verdades que son imposibles de expresar en él.1.2

En 1935 en una exposición del topólogo M. H. A. Newman, Turing se enteró que existían otras preguntas planteadas por Hilbert que aún no tenían respuesta, en particular se interesó por el problema de la decidibilidad, o bien el Entscheidungsproblem, esto es: ¿Existe un método por el cual se logre determinar para cualquier afirmación matemática $ X$ si ésta es decidible o no?

Para contestar esta pregunta, Turing desarrolló una teoría totalmente novedosa y original. Sin basarse en ningún otro resultado matemático, desarrolló la noción de máquina de Turing y a partir de ésta pudo definir con precisión el concepto de algoritmo. Dentro de su modelo podían existir un sin fin de máquinas distintas, pero la complejidad de este problema quedó resuelta gracias al concepto de máquina universal de Turing. Turing argumenta convincentemente, que todas las máquinas capaces de efectuar cómputos son polinomialmente equivalentes a una máquina universal de Turing. Armado con estas herramientas, Turing contestó negativamente el Entscheidungsproblem planteado por Hilbert: no existe un procedimiento que pueda determinar la decidibilidad de cualquier afirmación.

Lamentablemente para Turing, poco antes de publicar sus resultados, el Logicista Alonzo Church logró resolver el mismo problema utilizando formalismos de la lógica matemática, y la tesis de que todas las máquinas capaces de efectuar cómputos son polinomialmente equivalentes llego a conocerse como la Tesis Church-Turing.

Dentro del campo de la computación, sin embargo, Turing cuenta hoy con mucho mayor peso que Church. Entre los motivos que hacen que el enfoque de Turing sea más atractivo son:

  1. La propuesta de Turing es fresca y no requiere de ningún conocimiento previo de lógica o matemática.
  2. La propuesta de Turing es constructiva. Turing diseña y analiza una máquina que es mecánica y físicamente realizable.

Lo que no es inmediatamente obvio de esta propuesta, y no lo fue por muchos años, es que Turing amarra la noción de computabilidad con las propiedades de la física clásica. En retrospectiva, es claro que las máquinas analizadas por Turing dependían fuertemente de sus propiedades físicas. Entre ellas están:

Estas tres propiedes, aunque parecen evidentes1.3, no son ciertas en la mecánica cuántica. Entonces, cabe preguntarse: ¿Es cierta la tesis de Church-Turing para sistemas cuánticos?


next up previous
Next: Hacia una interpretación física Up: Introducción Previous: Niels Henrik David Bohr
Jose Castro 2004-10-06