The Problems That CPUs Can’t Solve

Off the jump, we can derive from the name “computer” that CPUs cannot solve any problem that is not able to be computed, obviously. But as we are discovering, even simple CPUs have signs of being able to handle nearly infinite variations of repeatable-computable problems, given the constraint that they finish and fit inside memory.

Therefore, learning the distinction between where computation is or isn’t a tool for problem solving will help us shine a more accurate light on what problems computers will be able to tackle in the future and thus tell us where to focus our efforts.

Having a set of off-limits bounds in a universal tool does not make it any less universal. A universal tool needs to have universal influence inside the bounds of its own universe, not the external universe. Instead, these limits should be thought of as creativity applied within constraints. For example, humans, despite our technological creativity, are bound to the laws of biology and physics. One reason we even deign to create external tools in the first place is because our biology is a deeply complex, and more importantly, finicky system that does not like to be thrown off balance, ergo external tools. Instead of heating our bodies, we heat our homes. Instead of running far on foot, we create vehicles. Instead of orating the same story over and over, we write. It would be interesting to imagine what problems humans could solve if augmentation was an internal process.

This limitation of “non-computable problems” also does not mean that CPU’s can’t compute specific examples of non computable logic with a bottom up approach of tackling parts of a problem at a time. These types of problems can be solved in piecemeal. It means in the general case that computers can’t help with these kinds of state transitions.

What is a Non Computable Problem?

Before we defined a problem as a state where an entity is uncomfortable, and a set of immediate actions that they can take to reach a new state where they are less uncomfortable. The entity is willing to take on a real energetic cost to conduct this transition. We now need to discuss what actions an entity could take that wouldn’t be considered in the simple CPU actions of read/write/decode/execute/jump/loop, for that entails problems that do not have a computable solution under the Turing machine architecture.

As for an exhaustive list, there are a host of non computable problems that are well defined, as well as a set of problems that are not well defined. Let’s go over a few.

The Halting Problem

The most common introduction to non computable problems for computer science students is the halting problem, which in essence states that there is no program able to be written that will tell if any other program will stop computing or run infinitely. Basically there is no external universal tool that in the general case will be able to tell if other universal tools ever finish doing their work. Comparing infinities and all, I suppose.

In the real world, we actually deal with finite memory on all of our machines, so every program technically “finishes” by returning successfully or devouring the entire resource space of the host to run a program and crashing the machine.

To go further, we can use the underlying theorem from the halting problem even more generally. A system cannot clearly comment on the totality of itself. There needs to be some external system that can verify or disprove that the system is comprised of X or Y or Z. It follows that if all programs (any program that could ever be written) were lined up one after another, there would not be any individual program in the set that could verify or disprove the rest of the programs, since the program that reads all of the programs would be inside the list of programs, creating a mutual dependency. (However, I am not fully convinced that there isn’t some kind of pairwise bonding that could be applied here, where each program has a sister program of sorts that’s sole duty is to watch the program, but I digress).

Paradoxes

Another set of non-computable problems are paradoxes. Paradoxes are common in universal tools where the rules are, well, made up. Here’s an example in human language: “This sentence is false”. This is a paradox because language in general is assumed to be comprised of true statements. However if what I said above is true, then the sentence is false. This means the sentence is both false and true, which logically can’t be the case. This is no problem in a system that isn’t reliant on the simple computation rules of the Turing machine universe. We as humans can see that sentence, shrug, and move on. This equanimity despite uncertainty was referred to by Leonardo Da Vinci as sfumato, having ease in knowing that some things are inherently uncertain, and that is not a issue!

A Turing machine will get trapped in a loop, forever trying to decide if the sentence is true or false. Paradoxes are non computable because computers literally can’t be in a state of paradox (have you ever tried to divide by zero?). Computers are foundational Boolean logic operators at massive scales. If something is required to be true and false, this breaks everything! (Quantum computers and transformers may not have this limitation, and we will discuss in a future post).

This fact alone is actually a huge issue in our universal tool, because paradoxes can be extremely useful as a creative tool, and elucidate unique facets about the universe.

This simultaneously implies that computers cannot suffer from what we might call cognitive dissonance, since dissonance is a sign of a paradoxical state, where a person deeply believes that A is the case and acts in a way that is directly counter to what would be the case if A were indeed true.

bramadams.dev is a reader-supported published Zettelkasten. Both free and paid subscriptions are available. If you want to support my work, the best way is by taking out a paid subscription.