in

GeekyGeeky

¿Existen problemas que los ordenadores no puedan resolver?

Paradojas matemáticas, y una dosis de Alan Turing para rematar


Ordenadores

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.


Reportar

¿Qué te pareció?

Legenda

Escrito por Lisandro Pardo

Moderador de ComunidadUsuario VerificadoVotadorAutor de contenidoCreador de GaleríasCreador de Listas

Comentarios

Leave a Reply
  1. Hablando de IA, habia algo con una paradoja de un Burro con hambre y sed vagando por el desierto, al llegar a un oasis encuentra donde saciar su sed y calmar su hambre, siendo un ser biologico dará igual de que aprovisionarse primero, pero si fuese una IA que basa sus decisiones en la logica a que se deciaria primero? a calmar su sed o su hambre? Si no hay una variable que incline la balanza (distancia a las fuentes de comida o liquido, p.e), se quedaría bloqueada pensando por siempre?

    • Yo pensé que irían por el lado de los números no computables, que por definición… No se pueden computar XD. Cualquier problema que los involucre (y hay alguno que otro famoso x ahi que ya fue planteado) no tiene posibilidad de ser resuelto. Ni por ordenadores, ni por ninguna teoría matemática conocida dicho sea de paso, pues su complejidad es a nuestros ojos “infinita” pero tampoco por ordenadores jaja.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.

Loading…

0
5G

¿El verdadero problema del 5G? Consume muchísima batería

El propósito de Solitario, Buscaminas, Carta Blanca y Corazones en Windows