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.
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.
