Nature and Computation

Physicists look for the simple rules of our world; computer scientists look for the possible worlds that come out of simple rules.

The world around us is complicated. Political experts are no better than monkeys throwing darts when it comes to predicting important political matters. Physicists need the help of powerful computers to predict how a universe with only three bodies behaves. Yet, physicists have discovered again and again that the apparent complexity boils down to simple rules, applied again and again. Predicting how a solar system with two planets moves is difficult not because we don't know what are the simple rules governing the movement, but because there is no other way to predict than repeated application of these simple rules. Repeated a lot.

But before discovering the simple rules, the laws of gravity, people thought that the movement of planets is really complicated. When you look up at the sky you see an intricate pattern of lights that slowly rotates. On that background, there are a few lights that wander around — these are the planets. (‘Planet’ comes from the Ancient Greek expression meaning ‘wandering star’.) To predict how planets move, ancients have developed all kinds of complicated models. Here is a picture from Ptolemy's Almagest, via Wikipedia:

Nowadays we have a much simpler model: All planets move on elliptical (but nearly circular) orbits around the Sun. Incidentally, the simplicity of this model is what motivates scientists to advertise that ‘the Sun is at the center of the solar system’ as opposed to ‘the Earth is the center of the Universe’. If the Sun and the Earth would be the only two bodies in the Universe, then both sentences would have equal merit. The only reason the Sun ‘is at the center of the solar system’ is that a model with the Sun in the center is much simpler than models with the Earth at the center.

It is rather surprising that whenever we observe a complicated phenomenon in nature, it almost always turns out that we end up explaining it from very simple principles. Often, all we need is a change in perspective, but a change in perspective is really difficult for most humans.

Conversely, it is rather amazing what complicated patterns emerge from very simple rules. Perhaps the most vivid demonstration is Conway's Game of Life. See here an example, again via Wikipedia:

That intricate pattern is generated from very simple rules. Imagine that a black dot is a (live) organism. The rules are: (1) underpopulation and overpopulation: a live organism with less than two neighbors or more than three neighbors dies; (2) reproduction: if an empty space has three neighbours (not too much, not too little), then an organism is born. Now read these two rules again. Would you believe the picture is just one example of the fascinating consequences of those two rules? Now look at the picture again. Do you think it's easy to figure out that it is based on only two simple rules? Well, that's what physicists do: They look at a complicated picture and they find simple rules that explain it.

I should stress that finding the simple rules (or principles) is by not means the end of the story. For example, now that you know the rules of Conway's Game of Life, can you immediately figure out how a world would evolve if given its state at only the present time? You could, of course, apply the rules over and over again and see what happens. But that is tedious and requires much computation power (and time). Is it possible to do better? It turns out that in many situations it is possible to find approximations that work well enough if you don't look too far into the future. This is the sort of thing that physicists are into. And, surprisingly enough, also computer scientists that work in the field of program verification. How so? Well, the rules of a programming language (say, Java bytecode) are fairly simple. Yet, if somebody gives me a program and asks what it will do, it is rather tedious to just apply the rules of the programming language (aka ‘operational semantics’). Plus, it will tell me what the program does for one particular input, which means I should repeat the process for other inputs, making this even more painful. (That would be the problem with what programmers call testing.) So, the question posed in program verification is how can we approximate quickly what the program will do, for a range of inputs. See? Really similar with what physicists do.

What else could we want to know once we know the simple rules? Well, you could get curious about what would happen if the rules change a little. How would that affect the consequences? Also, if somebody gives you an arbitrary set of rules, is it possible to decide whether efficient approximation schemes exist? Are there worlds that cannot be explained by simple rules? And so on. These kind of questions keep computer scientists busy, because they want to understand computation: how simple rules lead to complicated worlds.

Both physics and computer science deal with simple rules and complicated worlds. There are differences. Physics is mostly interested in one particular world, our Universe, and in discovering its simple rules. Computer science is mostly interested in sets of simple rules as an object of study in itself, with less regard for our Universe. Physics cares more about the world outside us; computer science cares more about the worlds inside us, because the rules are of our own making. Of course, the distinction inside–outside isn't strict. What appears first inside your brain could ultimately change the world outside. Also, your inside is my outside: So I could look at your brain the same way I look at any other object around me, and wonder how it works. Still, the distinction inside–outside is meaningful, just as the distinction between the rules of our Universe and other sets of rules is meaningful.

Almost done. In this post I tried to identify a commonality between physics and computer science: They try to understand the relation between simple rules and complicated worlds. If you want to hear more about how this relationship works in physics, I strongly recommend you watch this beautiful lecture by Feynman. (I remember even now where I was when I bumped into the book where this lecture ended up. I was in the National Library of Romania, browsing random books.)