Pregúntale al oráculo: El lado no computable de las matemáticas

Desde la antigüedad, la noción de algoritmo ha jugado un papel importante en el desarrollo de las matemáticas. Los griegos ya hacían referencia a este concepto al hablar de construcciones geométricas y el algoritmo de la división; sin embargo, no fue hasta el siglo XX que se formalizó matemáticamente con los trabajos de Church, Turing y Gödel, entre otros. A partir de la formulación de la tesis de Church-Turing, el averiguar la complejidad computacional de un problema se convirtió en una pregunta matemática de gran interés, un excelente ejemplo de esto nos lo da el problema “P vs NP” cuya solución conlleva una recompensa de US$1,000,000 por parte del Clay Mathematics Institute.

En esta plática, atacaremos el problema de la complejidad computacional desde otra perspectiva; consideraremos cualquier problema computable como “sencillo” -sin preocuparnos por el tiempo de cómputo- e introduciremos la noción de computabilidad con oráculos, la cual nos brindará una excelente herramienta para clasificar la dificultad de problemas que no tienen una solución algorítmica, en el sentido tradicional.