Turing the Universe

Brian Koberlein

My research area is computational astrophysics. This means I use computers to analyze astronomical data or model astrophysical systems. Most of my work is done through an application known as Mathematica, which is a powerful computational program. Like any application, Mathematica has advantages and disadvantages, but it has one property that is absolutely essential: it is Turing complete.

A program that is Turing complete is capable (at least in principle) of computing anything that can be computed. So the only real limitation to an astrophysical model is computing power and memory. As a result, I can run a model in Mathematica on my laptop. If it takes too long, or needs too much memory, I can run the same model on a cluster of computers. With enough grant money I could run it on a large supercomputing cluster. My only limitation is that of the current hardware.

Turing completeness is central to computational astrophysics, though it is not a particularly rare property for applications. For example, Excel and Minecraft are Turing complete. One consequence of this is that any Turing complete application can model any other Turing complete application, so in principle you could program Excel to run Minecraft, and then program Minecraft to run Mathematica. It would be horribly impractical to do that, but it’s possible in principle.

The idea of computational completeness was developed by Alan Turing. He was a mathematician and computer scientist who lived in the mid-1900s, and was central to the cracking of the German enigma code in WWII. It was his work on computability that lead to his understanding of enigma.

Knowing an application is Turing complete, you can then choose your application based on other needs, such as ease of coding, or scalability. These are two of the reasons I use Mathematica. It is geared toward scientific computing, and the same program can be run on a laptop or computer cluster without recoding.

Completeness gives us the confidence that computational models can provide an accurate description of astrophysical processes. We are not simply limited to models that can be done by hand. We can use computers to extend our understanding of the universe.