Today in Uncertainty Wednesday we are continuing to look at what limits exist on explanations. If you are just coming into this series now, you will definitely want to start all the way back with the framework which sets out the relationship between reality, observations and explanations.

I introduced explanations as abstracted relational stories about reality. These generally can be formalized (at least over time) as a set of mathematical equations or other logical expressions. This mathematical formalization of explanations has been one of the great breakthroughs of science as it allows us to make explanations more precise (e.g. the previously mentioned orbit of planets) and as it exposes contradictions more readily. If you are using informal language (as I am doing in this whole series so far), it is quite easy to make contradictory assertions and not notice it.

But thanks to the pioneering work of Turing and Gödel we know that there are hard limits on formal systems. They cannot explain everything. Turing showed that we cannot in general in advance decide whether some code will eventually halt, meaning stop executing (and we can think of code as another way of formalizing explanations). Gödel showed that any sufficiently powerful formal system will nonetheless be incomplete, meaning it will contain within it assertions that cannot be shown to be true or false.

Let me use a “simple” example called the Collatz conjecture.  You take an arbitrary positive integer. If it is even you divide it by 2. If it is odd, you multiply it by 3 and add 1. This will give you a new positive integer and you keep applying the same rules. So there are just two extremely simple equations here and this system is entirely deterministic. Now the conjecture is that no matter what number you start with, you eventually wind up getting into the following cycle: 1 -> 4 -> 2 -> 1 -> 4 -> 2 … (you should see how this cycle results from the two rules). So say you start with 11. You get 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 and you are in the cycle.

But do we *know* this to be true for any positive integer? We don’t. There is no proof. This problem is considered by many mathematicians to be extraordinarily hard. And it is important to keep in mind that since Turing and Gödel we know that *nothing* in mathematics or computer science says that a proof must exist. In fact, we already know since 1972 that for a generalization of the Collatz conjecture there is definitely no proof because such a proof would be the same as solving the halting problem.

So for now, and possibly forever, there is some uncertainty here. If I give you some arbitrary (large) positive integer, you cannot be sure that applying the rules will get you into the cycle. If the Collatz Conjecture is true then it will. But you cannot be certain.

The Collatz Conjecture may eventually be proven. In that case this uncertainty will go away. But we know forever forward due to the pioneering works of Turing and Gödel that there are hard limits on all formal explanatory systems. They cannot explain everything and this means there is irreducible uncertainty in the world.