El inicio de la computación moderna

Vvamos contar aquí sobre el paradójico inicio de la Ciencia de la Computación moderna. Y digo paradójico, porque llegó a la luz no cuando se buscaba una forma eficiente de hacer cuentas, sino cuando se intentaba mostrar que existían problemas no computables.

El héroe de esta historia es un tal de Alan Turing, que ya fue personaje de una película de Hollywood enEl Juego de la Imitacióny posee un premio de ciencias de la computación con su nombre, el Premio Turing, que se otorga anualmente a algún investigador que se haya destacado en el área. En 1937, demostró matemáticamente que existen problemas que no pueden ser computados. Sin embargo, para ello, tuvo que establecer lo que significa "ser computable" y, en este proceso, creó las Máquinas de Turing. Estas máquinas son conceptos matemáticos abstractos que formalizan la noción de computación, y un resultado matemático importante que descubrió muestra que existe una máquina especial, llamada Máquina Universal de Turing, que desempeña un papel central en la Teoría de la Computación. Esta Máquina Universal de Turing es la base para la construcción de los ordenadores como los conocemos hoy.

El artículo inicial de Turing tiene algunas cosas que llaman la atención y que están presentes en el propio título del artículo, traducido de forma libre aquí para:Sobre números computables y una aplicación al problema de decisión. ¿Cómo así, números computables? ¿Quiero decir que existen números no computables?

Sí, y no es tan difícil de ver. Pero antes, volvamos un poco en el tiempo, ya que los orígenes de la computación están íntimamente ligados a los números infinitos. En 1874, el matemático alemán Georg Cantor publicó un artículo en el que mostraba que existía más de un tipo de infinito. En particular, mostraba que el infinito de los números naturales 0,1,2,3, ... es menor que el infinito de los números reales. Quizás ya lo hayas notado, a partir de un simple dibujo. El infinito de los números reales corresponde a una línea continua (este conjunto se llama Continuo), y, sobre esta línea, bien espaciadamente, podemos insertar los números naturales o los números enteros (el tamaño del infinito de estos otros se llama Contable). Con una estrategia bastante innovadora, Cantor mostró que no es posible alinear los elementos del Continuo uno a uno con los elementos Contables, siempre sobra algún número que no queda alineado. De esta forma mostró que el continuo es estrictamente mayor que los números contables.

Entonces aparece Turing y demuestra que existen números reales no computables. Los números no computables siempre son elementos del Continuo. Por su definición, un número real es computable si existe un programa o, en la versión original, una Máquina de Turing, que imprime infinitamente sus dígitos. Pero cada programa y cada Máquina de Turing tienen un tamaño finito y se almacenan en un archivo. Un archivo nada más es un número natural, que puede ser muy grande. Entonces el número máximo de programas es un infinito contable, y no puede haber programas suficientes para imprimir todos los números reales. Muchos números reales no pueden ser impresos por ningún programa, y estos son los números reales no computables. Y ahora sabemos que la mayoría de los números reales no son computables, solo una pequeña proporción de ellos puede ser impresa por un programa o por una Máquina de Turing.

Una pequeña anécdota aquí. Cuando Turing escribió su artículo en 1936, sin que él lo supiera, otro matemático famoso, llamado Alonzo Church, ya había demostrado la existencia de números no computables, utilizando técnicas muy diferentes. Entonces los editores de la revista quedaron en duda si el artículo de Turing era verdaderamente original. El artículo quedó parado en alguna mesa hasta que alguien tuvo la idea de mostrar este artículo al propio Church, que encontró tan original la idea de Turing que lo invitó a ser su alumno de doctorado en Estados Unidos. Por esta demora, el artículo solo fue publicado en 1937. Turing terminó su doctorado en un año y regresó a Inglaterra cuando estalló la Segunda Guerra. Es ahí donde comienza la historia de la películaEl Juego de la Imitación, después de que Turing ya había hecho su gran contribución a la historia de la Ciencia de la Computación moderna.

Volviendo a los números, la primera reacción de la gente cuando aprenden que existen números no computables es la siguiente: "Por favor, muéstreme un ejemplo de número no computable". Y yo, con gusto, respondo: "No puedo mostrarlo. Si yo muestro el número, he de haberlo computado. Y un número no computable no se puede computar. ¿Obvio, no? Bueno, si no es obvio, acostúmense con la idea de que nunca podrán ver un número no computable, exactamente porque no es computable".

Pero, si el número no es computable, ¿cómo lo referimos? Bueno, tenemos que usar formas indirectas de definir el número sin hacer ninguna cuenta. Un ejemplo muy famoso es "la probabilidad de que un programa de ordenador se detenga". Esta expresión entre comillas es la definición del número. Se demuestra que este es un número no computable del que no podemos saber casi ninguna propiedad. No podemos saber si este número es menor que 0,5 o mayor que 0,00000001. Todas estas preguntas también son preguntas no computables.

Y esto nos lleva de vuelta al artículo inicial de Alan Turing. Él mostró que existen problemas no computables, es decir, que no pueden ser calculados por ninguna Máquina de Turing, incluido ese famoso Problema de Decisión (de la lógica de primer orden) que estaba en el título de su artículo.

Y así nació la computación moderna, mostrando que la computación tiene límites. Existen cosas que nunca podrán ser computadas, y tenemos que vivir dentro de los límites de lo que es posible hacer con una máquina de computación. El Teorema de Turing no depende de ningún lenguaje de programación ni de ningún tipo de ordenador. Por lo tanto, los problemas no computables permanecen no computables con cualquier tecnología, incluso con la más moderna inteligencia artificial o las tecnologías que se inventen en el futuro.

________________
(Las opiniones expresadas en los artículos publicados enEl Diario de la USPSon plenamente responsabilidad de sus autores y no reflejan opiniones del medio ni posiciones institucionales de la Universidad de São Paulo. Acceda aquí a nuestrosparámetros editoriales para artículos de opinión.)