When I studied computer science, I traveled to the heart of computing. There I found insights into God. This is my attempt to explain these insights: an article on computable numbers, with an application to theology.
Computing numbers and weighing stones
In my field, the highest honor that a person can obtain is the Turing award. Similar to the Nobel prize, it is awarded once a year to a distinguished computer scientist. The award is named after Alan Turing, an English mathematician and crypto code breaker. You might know him from the movie The Imitation Game. In 1937, a few years before the events in the movie, Alan Turing published a brilliant finding: there exist numbers that a computer cannot compute.1 These numbers are uncomputable in a very fundamental way: it’s not just that the computation would take a long time – it is actually impossible. There are questions for which, if you want to know the answer, a computer won’t help you.
I will explain Turing’s argument with an analogy. In a discussion about my faith, I was once asked: can an all-powerful God create a stone that is so heavy that even God himself can’t lift it? This is the omnipotence paradox. Of course, God can create such a stone; God is omnipotent, right? But at the same time, shouldn’t God be able to lift every stone in existence by virtue of being omnipotent? So then, how can there be a stone that God isn’t capable of lifting?
Alan Turing’s argument is similar. Instead of discussing stones and their weight, Turing wrote about computer programs and the time they take to execute. A stone that can be lifted would correspond to a program that eventually finishes. Instead of discussing God, Turing discusses a kind of meta-program that decides whether another given program ever finishes. Turing concludes that such a meta-program cannot exist since one could always construct a program for which the meta-program produces the wrong result.2 The constructed program is like the hypothetical stone that is so heavy that God can’t lift it.
Searching for numbers…
Despite the mathematical nature of Turing’s argument, his paper has proven to be of great practical value. Indeed, the paper not only talks about what can be computed but also presents the design of a machine that can compute all the computable answers. This machine, called a Turing machine, is extremely simple. A pocket calculator of sorts. Turing showed in his paper that to compute an answer, you’re just as well off with a pocket calculator as with a supercomputer (except that the pocket calculator might take a bit longer to perform its steps).
It turns out that Turing machines appear in unexpected places, such as biological systems. In 1985, Stephen Wolfram researched cellular automata3. These are mathematical models of cells living in a tissue. Cells would live if they had the right number of neighbor cells, but they would die if they were too lonely or lived in an overcrowded area.
In the simplest possible model, the tissue is just a row of cells, like this:
One can then construct various rules to model under what conditions a cell lives. For example, consider the rule “a cell will survive if it has at least one living neighbor.” This leads to a steady state, or equilibrium, like in this figure:
Another rule could be: a new cell will grow if there is at least one neighbor. This leads to quick growth:
It turns out that there are only few possible rules. In fact, Wolfram found that there are exactly 256 of them. This is fantastic because we can look at each rule and simply see how the model behaves. In other words, we can easily find out all there is to know about these automata, can’t we? No…turns out our intuition is fundamentally wrong! And the reason for that is linked to Alan Turing.
The two examples we’ve seen so far are indeed simple. Cells from example 1 will reach a steady state after one generation. In Turing’s terms, this is a program that finishes. Cells from example 2 will grow forever: a program that never terminates. The behavior of these programs is predictable. If they were stones from our previous analogy, we could decide whether they can or cannot be lifted.
But Wolfram found, among the 256 possible rules, one that was surprising. He called it “Rule 110,” and after some generations it looks like this:
The cells show a surprising mix of structure and randomness. Parts of the pattern look regular, but these parts are occasionally interrupted by groups of cells that “travel to the right,” or white triangles where cells have died. These events seem to occur in a completely unpredictable way.
In Wolfram’s beautiful book4, you can see hundreds of generations of these cells printed on the cover. The cool thing is that no steady state emerges. A colleague of Wolfram, Matthew Cook, later proved that Rule 110 is “Turing complete.” This means that in all its simplicity, it is equivalent to the most powerful supercomputer out there. Which is awesome. And awful because we’ll never understand how it will look after infinitely many generations.
…and finding God
To me, thinking about these machines is profoundly humbling. If computers are just pocket calculators and yet are so hard to understand, then I like to believe that some questions cannot be answered by logic and mathematical reasoning. I think of God as all the more fascinating because of his infinity. If infinite execution time turns even the simplest automata into life-like, complex things creating intractable variations of patterns, how much more can God’s infinite power, time, and presence do? My hope is that one day, I’ll see God, get a glimpse of infinity, and participate in it…it is a glorious hope.
I wish us all a passion to look for God, the humbleness to admit that we will never fully understand, and a lasting fascination for the infinite!
————
Notes:
Cover image generated using code by Jos Dirksen.
1Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. January 1937. Online Version.
2Assume that P is the hypothetical meta-program that can decide if any given program finishes.
And let Q be a program with the following source code: “if P(Q) then sleep.” Q is only 18 characters of source code. Yet P, when given those 18 characters as input, produces the wrong result. This contradicts our assumption that P would give the correct result for all programs out there.
3Wow, these cellular automata were discovered in the year that I was born. Cool, huh?
4Stephen Wolfram: A New Kind of Science. 2002. Read online.
