tbd
The Problems That CPUs Can’t Solve
the types of things that can't be solved by things that solve types of things
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.
Bridging the Distance in Problem Space
How CPUs actually move through the problem and solution space
The capacity to read, write, decode, and execute one clock cycle at a time allows a CPU to effectively bridge the gap between state transitions in the problem space (202306222324). The CPU's ability to jump enables it to move to different states conditionally, without having to pass through each one individually. This results in a tree-like leap from one section of the potential solution space to another (this is all within the set of repeatable problems, R). By looping, CPUs are able to pass data back and forth between two states until we accumulate enough information for a transition.
Reading, Decoding, Writing, Executing
Challenges in the set of reading, decoding, writing, and executing include: substituting old data with new, comprehending a massive amount of data, responding upon encountering a specific type of data, and modifying data to your heart's content.
Coffee Shop Example
Consider a situation at a coffee shop. You read the menu and decode the prices in your head. You mentally calculate the balance in your bank account (or, if it's on credit, you skip this step), and then you execute your decision by selecting the coffee you want and asking the barista to place your order. The barista decodes your order, enters it into the point of sale machine, and begins preparing the order once the credit card company reads the request, checks your account balance, compares the two numbers (decode + execute), and finally returns a positive or negative response. All these steps occur almost instantly and are partially carried out in the human brain and databases at the store and at the bank.
Jumping And Looping
Challenges in the set of jumping and looping include: making significant decisions that drastically alter the resultant execution based on decoded input, and repeating the same action multiple times to achieve an accumulation result.
Consider the example of exercising to get in shape. You go to the gym. You don't want to overwork your muscle groups, so you perform enough repetitions on one machine to gain strength, and then you jump to the cardio section to exercise there while resting your recently worked muscle group.
Breathing provides an even simpler example of looping. If you stop breathing, that's a critical problem. Recall that a problem represents a desire and a state. Not breathing is an undesirable state to be in. If you're still alive, your body will do everything in its power to restart the breathing loop and restore homeostasis, up to and including: gasping, wheezing, seizing the lungs, etc.
These universal tools are not only shared among specific use cases; they are universal because they can be applied to any conceivable problem <> solution situation.
Our brains and bodies also engage in reading raw input, decoding it, then conditionally jumping or looping, executing the resulting thought process, and finally recording the outcome in memory for future feedback loops.
Just like us, CPUs also perform these tasks, one clock cycle at a time!
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.
The Simplest CPU
what do we need to make the simplest computer?
Let’s imagine the simplest version of something that has the ability to calculate. If we break down a calculation into its simplest components, we will need: inputs, operations, and outputs.
We want input data to compute against, some raw material to convert into something else, some kind of operation or operations to do said converting, and finally some way to decipher and store the outputs, and convert those into inputs to continue the process.
The simplest tool-less version of this is to use our own dextrous human hands. Feel free to try this experiment, or skip it!
Put both of your hands into a fists, showing zero fingers. Lay your right hand down on a table or your lap. Next, stick out your index finger on your right hand, and place your thumb finger of your left hand over it. Your thumb will serve as the “counter”. Next, count the finger (1) and raise one finger one your left hand. The four fingers on your left hand will serve as storage. Now close your right hand again and raise any number of fingers from 1-3. Remember, as you count one with your left thumb, raise a finger on your left hand. Now, use your right thumb to “read” from storage and count how many fingers you have up on your left hand. Amazing! We’ve created a simple adder without talking about adding, just counting one at a time and storing what we’ve counted. We can do the same with subtraction, if we want, the only change will be to put a finger away on our left hand for every finger we count on our right.
Now there are some clearly obvious limitations to this method. Despite obviously being very physically uncomfortable, we have some serious mathematical barriers that cannot be overcome. For one, if we reserve our thumbs as counters, we can only store four numbers total, since our right hand is busy introducing new numbers to be stored on the left. Secondly, the only operations we can conduct are based around simple counting, we cannot even access the other elementary math operations of multiplication and division (well technically, we could do division on our fingers, but trust me, we do not want to do that).
Even as we introduce more complex technologies to the table the general principle of what we did on our fingers: reading the fingers up on our right hand, executing a count using our thumb counter, and writing them to the left hand every time we counted one is the basis for all computation. Modern day computers do this loop we just did in our heads really, really, really fast.
Let’s imagine one more simple technology (this one will only be a thought experiment, no need to worry about contorting your hands). In addition to the operations of reading, writing and executing above, what other simple operations might prove helpful?
Perhaps we realize that we can repeat certain parts of the counting process over and over while in the “write” step instead of stopping to read every time. To multiply is to add something over and over (2 x 3 = 2 + 2 + 2) so a looping operation would help us unlock multiplication from addition. Division is the same as repeated subtraction into groups, so we can use the looping function here as well.
What happens when we decide to stop the adding operation count the number of fingers on our left hand? Or what happens when our four left fingers “overflow” from counting on the right hand? We need some way of being able to stop the count, or more accurately modify our decision making based on what we see on our fingers. We can call this a conditional operation. With our conditional operation, we open up an infinite list of sub operations. Let’s say that if two fingers are up on your left hand are up, you do ten jumping jacks or five burpees, or if three fingers are up you do ten pushups and dance in place for 30 seconds. The options are limitless! We see our trigger, validate it, and then do something else.
So loops and conditionals have been added to our list of operations. We can now read and write to storage, execute on what we read, loop to repeat some helpful block of logic, and jump conditionally to some other process if some condition is met.
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.