Problemas fáciles, difíciles y muy difíciles

Dr. Santiago Figueira

    Una computadora puede resolver muchos problemas. Hay problemas que son fáciles y hay problemas que parecen más difíciles porque necesitan procesadores más poderosos o memorias gigantescas.

    Pero hay problemas que ninguna computadora (ni actual ni futura, sin importar que tan rápida y poderosa sea) puede resolver. Y no se trata de un problema que nadie pudo resolver hasta ahora, ¡sino de un problema que se demuestra (usando la lógica) sin solución! Es decir, podemos demostrar que ninguna computadora, jamás, lo va a poder resolver.

    Este problema se llama problema de la detención o halting problem y fue descubierto por Alan Turing hace 70 años, cuando todavía no existían las computadoras. Es cierto, en ese tiempo no existían las computadoras, pero ya se había empezado a pensar en los métodos efectivos, es decir, en los problemas que podían ser resueltos de una manera mecánica o efectiva.

    Pero ¿qué es lo efectivo? ¿Por qué algunos matemáticos y lógicos empezaron a pensar en estos métodos efectivos? ¿Quién fue Turing? ¿Qué es una máquina de Turing? Y finalmente, ¿en qué consiste este problema misterioso que ninguna computadora puede resolver?

    Estas son algunas de las preguntas que voy a explicar en esta charla.