Are There Problems That Computers Can’t Solve?

¿Hay problemas que las
computadoras no pueden resolver? Incluso si trabaja con los programadores más inteligentes,
incluso si tiene tiempo y energía infinitos y más poder de cómputo del que
podría existir en el universo, ¿hay algunas cosas que siempre
serán imposibles de resolver para una computadora? ¡La respuesta corta es sí! La respuesta larga sería una serie completa de
conferencias de introducción a la informática. La respuesta bastante corta que espero no haber
simplificado demasiado… es el resto de este video. Una de las mejores cosas de las computadoras antiguas
como estas BBC Micros era que el sistema operativo, lo primero que tenías cuando las
encendías, también estaba en algún lugar donde
podías escribir código. Entonces, si fueras un dependiente de una tienda que
vendiera estos en los años 80, tendrías que tener cuidado cuando
los niños no estaban en la escuela, porque mientras estabas distraído, algún nerd podría colarse y escribir
algo como esto en silencio.

Y de repente, su modelo de pantalla
escribía sin cesar algo grosero hasta que presionaba la tecla "pausa" o
apagaba y encendía la computadora nuevamente. Ese es un ejemplo realmente simple de un programa
que nunca se detendrá. Y está escrito deliberadamente de esa manera. Pero los programas que nunca se detienen
también pueden escribirse accidentalmente: todos hemos tenido ese momento en el que
algo en lo que estamos trabajando se congela, atrapado en un bucle sin fin haciendo…
¿algo? Y tienes ese horrible momento de tratar
de recordar si guardaste recientemente o no. Sería genial poder analizar el código,
cualquier código, y decir definitivamente: "sí", eventualmente se detendrá o "no", hay un punto allí donde
seguirá en bucle para siempre, si esto sucede. Lo que suena como un problema simple.
En realidad es imposible. Literalmente, matemáticamente, imposible. Y la forma en que descubrimos eso proviene incluso de antes
de que se inventaran las computadoras electrónicas. A principios del siglo XX, un matemático llamado David Hilbert planteó
una serie de problemas que pensó que las matemáticas
deberían poder resolver.

Uno de ellos llegó a ser conocido como el… …el, eh… el "Problema de decisión". Que es, en resumen: "¿Podemos determinar si cualquier
declaración dada", es decir, absolutamente cualquier declaración o
problema lógico en el universo, "es demostrable o no demostrable?" Con el tiempo suficiente, ¿podríamos encontrar una respuesta
a todo? Hilbert era optimista de que
la respuesta sería sí. Otros matemáticos demostraron que estaba equivocado. Uno de esos matemáticos fue Alan Turing. Y para explicar su prueba, primero debemos
mirar la herramienta que solía hacerlo. Turing estaba mirando la mecanización de la
lógica y la computación. Una "computadora", en este punto, no era
algo electrónico, era una descripción de trabajo, personas que se sentaban en habitaciones haciendo cálculos específicos
una y otra vez. una y otra vez, se les llamó computadoras. Porque computaban. Turing estaba fascinado con la idea de automatizar
ese proceso. El sueño era que si todo pudiera codificarse
en números y si tuviéramos métodos mecánicos para trabajar
con esos números, entonces, tal vez, cualquier cosa se podía resolver.

Se le ocurrió una hipotética
máquina calculadora, que terminó por llevar su nombre. Una Máquina de Turing estaría hecha, primero: de una cinta. Esta cinta sería, gracias a esto existente
en la filosofía mágica hipotética. y, infinitamente largo, y dividido en celdas. En términos modernos, eso es memoria de computadora. Luego, un cabezal de lectura y escritura, que puede moverse hacia la
izquierda o hacia la derecha sobre esa cinta, leyendo lo que hay allí o cambiándolo. Luego tiene un registro de estado y
una tabla de instrucciones, que en términos modernos son el código. Hay muchas cosas complicadas que
estoy pasando por alto sobre cómo funciona todo, pero en resumen
: es algo de código. La máquina sigue ese código, que puede incluir instrucciones como
"mover a la izquierda", "mover a la derecha", "cambiar lo que hay en esta parte de la cinta"
o "leer lo que hay en esta parte de la cinta", y qué instrucciones se utilizan pueden depende
de lo que digan esos trozos de cinta.

Finalmente, la máquina de Turing llega al
final de sus instrucciones y se detiene. O entra en un bucle sin fin. Era, básicamente, el mínimo ordenador posible. Pero resulta que también es cada computadora. Cualquier programa que escriba
en cualquier lenguaje de programación puede convertirse en algo que pueda ejecutarse
en una máquina de Turing. Entonces, usando esa máquina, Turing replanteó el
problema de decisión: "¿Podemos determinar si un programa dado se
detendrá o no?" Misma pregunta, formulada de otra manera. ¿Encontrará la máquina una solución,
probará una declaración o seguirá funcionando para siempre? Recuerde, la gran pregunta que
estamos tratando de responder es: ¿hay alguna pregunta que
una computadora no pueda resolver? Entonces, Turing propuso una serie de pasos. Y sí, lo sé, los informáticos observan, esta es una simplificación deliberada, sé que hay muchas cosas sutiles que
me estoy saltando. Pero: Turing propuso una serie de pasos.

Primero: imagina que creamos
una máquina de Turing, un programa, que puede mirar un código y averiguar si ese programa se detendrá. En este punto, no necesitamos saber cómo
lo hace realmente esa máquina, supongamos que funciona de alguna manera. Llamemos a esta máquina, a este programa, "Paradas". "Halts" toma el código de un programa como
entrada y genera una de dos respuestas: "Sí", ese programa se detiene. O "No", se repite para siempre. ¿Hasta aquí todo bien, no? Entonces, vamos a atornillar otra máquina,
otro programa, al final de "Halts". Y dependiendo de la salida de "Halts"
, hará una de dos cosas. Si "Halts" da como resultado "sí", sabiendo que
el programa que ha ingresado eventualmente se detendrá, entonces esa máquina
entra en un ciclo infinito.

Tal vez solo imprime algo grosero una
y otra vez. Y si Halts emite un 'no', si Halts resuelve que el código que hemos ingresado
se repetiría para siempre, entonces esta nueva máquina simplemente se detiene. ¿Bueno? Entonces, si Halts lee el código
y dice "eso se detendrá", entonces la nueva máquina realiza un bucle. Si Halts dice que un programa se repetirá,
la nueva máquina se detiene. Pondremos un cuadro alrededor de ambos y llamaremos a
esta nueva máquina "Opuesta". Porque hace lo contrario de
cualquier código que ingrese. Con todo eso configurado, aquí es donde Turing
lanza la trampa. Propone que tomemos este nuevo
programa combinado, Opuesto, tomemos su código, y alimentemos su propio código en sí mismo. ¿Qué hará? Pasemos por la lógica. Si cree que la respuesta es: este código se detendrá y
luego se repetirá.

Pero entonces la respuesta es: se repetirá. Entonces se detendrá. Pero luego se detendrá. Entonces se repetirá. Pero entonces, será… daaagh.
Y se desvanece en un soplo de lógica. Para ser claros, eso no es un bucle en sí mismo. Eso es una paradoja.
Eso es una imposibilidad lógica y matemática. Y esa es la respuesta de Turing
al Problema de Decisión. Si alguna vez tiene un programa que puede determinar,
con certeza, si un programa en particular
se detendrá o se repetirá , puede modificarlo un poco fácilmente,
dejar que se contradiga y causar esa paradoja.
Y eso es imposible. Entonces, un programa para hacer eso no puede existir. Lo que significa que definitivamente hay una excepción, definitivamente hay al menos una cosa
que las computadoras nunca pueden resolver, incluso con tiempo y poder infinitos. La respuesta al problema de decisión,
la respuesta a la pregunta "¿Podemos determinar si todos los programas se
detendrán o no?" no es.

Ahora, obviamente hay muchos programas en los que puede saber fácilmente de un vistazo si se
detendrán o no. Este código se repetirá para siempre. Este código saldrá y se detendrá. El problema de decisión no se trata de saber
si algunos programas se detendrán o se repetirán.
Eso es fácil. Se trata de cada programa. Se trata del hecho fundamental de que
definitivamente hay algunas cosas que las computadoras nunca pueden resolver. Lo que supuso un duro golpe para aquellos matemáticos
como David Hilbert que creían que las matemáticas puras
tenían la capacidad de resolver cualquier cosa. Las computadoras parecían máquinas increíbles que
podían calcular cualquier problema que se les presentara, si se les daba suficiente tiempo.

Pero incluso antes de que existiera la primera
computadora digital, Alan Turing había descubierto que todavía
tienen límites..