Computability and Algorithmic CompressionBy: Bruce
In a previous post I showed how to calculate PI and made the point that purely mental concepts, like PI, actually do exist.
Also, donât miss this post on M* where I considered how to use math to measure the earth and the moon â a power once associated with Divinity.
Now I want you to think about PI again for a moment. Back in school I was taught to use 3.14 to approximate PI. If I needed more precision I used 3.1416. But actually PI is what we call an irrational number.
Do you remember doing repeating decimals? You know, where you divide a number out and a pattern forms. For example, you take 1 and divide it by 3. The end result is 0.3333âŠ where the 3 goes on forever repeating. The way they teach you in school to write it down is to write 0.3 and then put a bar over the 3 after the decimal to signify that it just keeps repeating forever.
One of the amazing things about PI is that it never repeats. Itâs actually possible to prove this because we can prove that no fraction in the form of X / Y can ever equal PI. (fractions in the form X/Y always repeat at some point.)
So PI is actually an infinitely long sequence of numbers that never repeats.
But here is something interesting. In my previous post I showed you how to calculate PI to any number of digits.
You Can Represent the Infinite Finitely
Now imagine that you are a computer programmer. If you canât imagine that, then imagine you are hiring one. You take my previous post and you decide to take the steps I explained and you are going to write a computer program that calculates out PI to any number of digits that you specify. Because you understand the steps required to calculate PI, you know that itâs possible to write a computer program that does this calculation for you.
Now letâs define a few terms. When you write that computer program, you have to come up with a finite set of steps of logic that the computer will follow that will calculate PI. Those finite steps are what is called an Algorithm. Algorithms are just the set of steps you follow to get some result â any result desired so long as itâs logically possible through a set of logical steps.
If you can (at least in principle) program a computer to take certain inputs and then give a desired answer using an algorithm, then we say that the problem to be solved is Computable. As mentioned in my previous post in the footnotes if itâs computable, but too slow to be useful, we call it Intractable.
Now notice something interesting here. PI is an infinite sequence of numbers, but we can (at least in principle) calculate it out using only a finite algorithm. Isnât that interesting? Seems a little counter intuitive to me. Yet itâs now obvious that itâs true. The infinite can arise out of the finite.
I actually didnât need something complex like PI to prove this point. Physicist and author John D. Barrow, in his book Theories of Everything: The Quest for Ultimate Explanation, uses a much simpler example. Barrow uses the string of numbers 2, 4, 6, 8, etc. Itâs easy for us to see that this infinite list of numbers can be fully represented as âthe list of positive even numbers.â Again, we see that the infinite can be finitely represented without losing any information. Barrow goes on to say, âIt is clearly non-random. A short computer program could instruct the machine to generate the entire infinite sequence.â
This ability to compress things by representing them through a set of steps he calls âAlgorithmic Compressibility.â (Theories of Everything: The Quest for Ultimate Explanation, p. 14-15)
Science (and Math) Is The Search for Algorithmic Compressibility
He goes on to make a startling conclusion about the nature of science that is probably different than what you were taught in school. When I was in high school, and even in college, I was always taught that science was primarily about observations in nature. While this is clearly an important part of science, Barrow challenges this interpretation of science:
The goal of science is to make sense of the diversity of Nature. It is not based upon observation alone. It employs observation to gather information about the world and to test predictions about how the world will react to new circumstances, but in between these two procedures lies the heart of the scientific process. This is nothing more than the transformation of lists of observational data into abbreviated form by the recognition of patterns. The recognition of such a pattern allows the information content of the observed sequence of events to be replaced by a shorthand formula which possesses the same, or almost the same, information content. âŠ On this view, we recognize science to be the search for algorithmic compressions. âŠ Without the development of algorithmic compressions of data all science would be replaced by mindless stamp collection â the indiscriminate accumulation of every available fact. (Theories of Everything: The Quest for Ultimate Explanation, p. 14-15)
The Non-Algorithmically Compressible
If some things can be algorithmically compressed, does that imply some things can not? If so, what would a non-algorithmically compressible thing look like?
The short answer is that if a thing canât be algorithmically compressed (that is to say, it is not computable) then the reason is probably because itâs random.  Imagine a random string of numbers. The shortest possible representation of that string of numbers is the string of numbers itself. 
So we now have a theory about reality, one that we need to consider further. Here is our theory: reality is split up into two fundamental kinds of things: those that are algorithmically compressible and those that are random. Later on, weâll look at other types of phenomenon that challenge this category scheme. But for now, try your best to think of an exception and see if you can without looking it up.
This process of how we discover the truth about reality using reason is what we call epistemology.
So we find that Barrowâs view of science is that it is the process of how we use reason to find patterns in reality and then to algorithmically compress them into finite steps and formula that allow us to represent reality via processes that are computable.
For the moment this is our working theory about reality. Iâll cover some challenges to this view later.
So what do you think of Barrowâs view of science?
What is science anyway?
Why does science progress? (Does it progress?)
How does it progress?
What do you think of the idea of the infinite arising out of the finite?
Other than randomness, can you think of things that canât be computed? (i.e. put into an algorithm?)
What about things like beauty, poetry, or consciousness? Can those be put into algorithms?
 In a future post weâll see that there are other things that are not computable not because they are random but because they are rational contradictions. This also means they do not exist in reality, so I am eliminating them for now. Of more interest is the existence of non-computable phenomenon that do seem to exist in reality. These will be considered in future posts.
 The shortest possible representation of that string of numbers is the string of numbers itself. One possible objection here is that it is possible to write a computer program to create a random string of numbers. The key point here is that you canât write a computer program to come up with a specific string of numbers. Not even in principle. If you could then by definition it would not be random and so it would be algorithmically compressible. (If a random string is finite, at least you could store them by rote. But, for the moment, that is cheating.)