¿Existen problemas que los ordenadores no puedan resolver?

Información, entretenimiento, trabajo, educación, soluciones rápidas a problemas complejos… por lo general, tenemos una idea bastante sólida de lo que queremos a la hora de usar un ordenador. De hecho, hay momentos en los que un sistema parece capaz de resolverlo todo, y eso nos lleva a un ejercicio de lógica muy interesante: Imagina un ordenador con tiempo, energía, y poder de procesamiento infinitos. ¿Acaso existe algo que a pesar de esas ventajas no pueda resolver? La respuesta corta es «sí», pero necesitamos la ayuda de Tom Scott para el resto…

---

¿Cuántas veces ha sucedido? Una pregunta sencilla nos arroja a un agujero negro de lógica y razón. El matemático David Hilbert (el mismo del hotel infinito) quedó atrapado en esa situación junto a su colega Wilhelm Ackermann en 1928, año en el que ambos presentaron el desafío del Entscheidungsproblem o «Problema de Decisión». En términos extremadamente relajados, el problema propone lo siguiente: ¿Acaso es posible determinar si una declaración o sentencia dada es demostrable o no? Con el tiempo y la energía suficiente, ¿podemos encontrar la respuesta a cualquier cosa?

---

---

Ahora, ¿qué tiene que ver esto con los ordenadores? En realidad, esa duda de Hilbert puede ser adaptada al universo informático de una forma muy particular: Imagina el código de un programa, cualquier programa. ¿Acaso es posible analizar ese código y determinar de forma automática si se detendrá o entrará en un bucle infinito? En este punto es cuando alguien sugiere un ejemplo como:

10 PRINT “HOLA MUNDO”
20 GOTO 10
RUN

Obviamente, esta pieza de código lleva a un bucle infinito… pero la diferencia es que fue diseñada de ese modo. Determinar si algunos programas se detienen o siguen para siempre, eso es fácil. La idea de tomar cualquier código, todos los códigos, y analizarlos para establecer definitivamente si finalizan o entran en bucle puede parecer simple en la superficie, sin embargo, es matemáticamente imposible. ¿Cómo lo sabemos? Gracias a cierto caballero llamado Alan Turing, y la famosa Máquina que lleva su apellido, del año 1936.

Aquí es cuando Tom Scott nos rescata con su explicación: Imaginemos un programa bautizado «Halts» que puede ver una muestra de cualquier código, y determinar si se detendrá (no necesitamos saber cómo lo hace, lo importante aquí es que funciona). Una vez más: «Halts» ve el código, y responde «sí» (se detiene) o «no» (bucle infinito). Ahora, visualicemos un segundo programa conectado a «Halts», que hace exactamente lo opuesto a su respuesta. O sea, si «Halts» dijo que el código se detiene, el segundo programa entra en bucle infinito, y si dijo que entra en bucle, se detiene.

---

Paradoja de Jevons, o por qué ahorrar energía nos lleva a consumir más

---

Este sistema es llamado «Opuesto», porque en esencia hace lo contrario a lo que ingresas en él… pero aquí es cuando Turing quiebra todo con su propuesta: Tomar el código completo que compone a «Opuesto», y que se analice a sí mismo. El resultado… es que no hay resultado. Es una paradoja, una imposibilidad matemática. Aún con las condiciones iniciales ideales, una mínima variación colapsa el proceso. Y allí está nuestra respuesta a la pregunta original: Existe al menos una cosa que los ordenadores no pueden ni podrán resolver.

---