Are There Problems Computers Can't Solve?

Information, entertainment, work, education, quick solutions to complex problems... we usually have a solid idea of what we want when we use a computer. In fact, there are times when a system seems capable of solving everything, and that leads us to a very interesting logical exercise: imagine a computer with infinite time, energy, and processing power. Is there something that, despite those advantages, it cannot solve? The short answer is "yes", but we need Tom Scott's help for the rest.

Hilbert's Entscheidungsproblem

How many times has it happened? A simple question throws us into a black hole of logic and reason. Mathematician David Hilbert (the same one from the infinite hotel) found himself trapped in that situation alongside his colleague Wilhelm Ackermann in 1928, when they presented the challenge of the Entscheidungsproblem, or the "Decision Problem". In very relaxed terms, the problem asks: is it possible to determine whether a given statement or sentence is provable or not? With enough time and energy, can we find the answer to anything?

Now, what does this have to do with computers? Actually, Hilbert's question can be adapted to the computing universe in a very particular way: imagine the code of a program—any program. Is it possible to analyze that code and automatically determine whether it will stop or enter an infinite loop? At this point, someone might suggest an example like:

10 PRINT “HOLA MUNDO”
20 GOTO 10
RUN

Obviously, this piece of code leads to an infinite loop... but the difference is that it was designed that way. Determining whether some programs stop or run forever is easy. The idea of taking any code—all code—and analyzing it to definitively establish whether it finishes or loops may seem simple on the surface, but it is mathematically impossible. How do we know? Thanks to a certain gentleman named Alan Turing and the famous machine that bears his surname, from the year 1936.

The Paradox of Self-Reference

This is where Tom Scott comes to the rescue with his explanation: imagine a program called "Halts" that can look at any piece of code and determine whether it will stop (we don't need to know how it does it; the important thing is that it works). "Halts" sees the code and answers "yes" (it stops) or "no" (infinite loop). Now, picture a second program connected to "Halts" that does exactly the opposite of its response: if "Halts" says the code stops, the second program enters an infinite loop; if it says the code loops, the second program stops.

This system is called "Opposite", because it essentially does the opposite of what you input... but this is where Turing breaks everything with his proposal: take the complete code that makes up "Opposite" and have it analyze itself. The result... is that there is no result. It is a paradox, a mathematical impossibility. Even with ideal initial conditions, a minimal variation collapses the process. And there is our answer to the original question: there is at least one thing that computers cannot and will not be able to resolve.