Is Reality Digital or Analog

After my collaboration with Tommaso Bolognesi last autumn, we noticed the following essay competition being run by FQXi. FQXi is a marvelous organization that supports frontier physics research in areas where other organizations wouldn’t dare. It’s an invaluable resource for people who’re trying hard to think outside the paradigm box, and a useful rallying point for those interested in foundational questions about how the universe actually works.

The subject of the competition: Is Reality Digital or Analog?

How could we not take part? Tommaso and I agreed that we should both submit an essay. I didn’t win, but I’m delighted to say that Tommaso received a prize. For those who’re interested, my submission can be found here, and Tommaso’s here.

Antropy Doubled

In my last post, I introduced an algorithm for turning order into chaos and back again using a turmite (otherwise known as a 2D Turing Machine). This time, I have to admit that I kept some of the truth from you. I didn’t just come up with one algorithm, I came up with two. And the second one is significantly more weird and beautiful than the first.

Where my first algorithm used a single machine head, my second one uses two. And instead of simply picking up and putting down bits, this new algorithm swaps them from one head to the other. Machine-head A passes its data to head B, and B passes its data to A. What this means is that the new algorithm is a lot faster at turning order into chaos while being no less reversible.

On top of this, the new algorithm produces some eerie physics-like results from time to time, the reasons for which still aren’t entirely clear to me. The new algorithm working on a block of bits also looks peculiarly like something rotting or rusting—something I’ve not seen before in a simple algorithm.

Once again, I’m struck by the peculiar corrosive beauty of these programs but am still not sure what they’re good for. You can find the simulations here.

Increasing Antropy

I have a new algorithm that I want to share with you. It’s interesting to watch, slightly mysterious, and I can’t help but wonder if it might turn out to be useful for cryptography or something. Before you take a look, though, I should first explain what it does, why I came up with it, and what it has to do with digital physics. (For the impatient, the cool stuff is here.)

During my collaboration with Tommaso Bolognesi at CNR-ISTI last autumn, we were looking for ways to create sparse, pseudo-random data structures. Specifically, we wanted sparsely-connected directed acyclic graphs (a requirement for building spacetime-like causal sets, a term I explained in my last post.) However we soon discovered that there weren’t any classes of data structures for which we could get the kind of results we were looking for.

For those of you with a math/computing background, this might sound like a slightly odd statement, because there have been algorithms to build sparse, pseudo-random matrices for ages. However, none of these algorithms were as simple as we wanted, or as adaptable as we wanted. For starters, most of these algorithms require that you explicitly represent numbers somewhere in your code. For our purposes, this pretty much ruled them out immediately. What we wanted was for the sparseness of the data to emerge naturally out of a process without us having to impose extra layers of interpretation on it.

To get a sense of what I mean, let’s take a look at turmites. Turmites are very simple programs of a sort that Tommaso and I have explored and are great at producing pseudo-random data. The way they work is very straightforward: you have a network of memory slots hooked up according to some geometrical rule. You also have a machine-head that can move across that network and change the contents of the memory slot it’s sitting on. You then create a simple rule for moving the machine-head based on the contents of the slot where it’s located. It’s basically like a 2D Turing Machine.

The simplest such program is probably Langton’s Ant—the first turmite ever discovered. It runs on a square grid of black and white cells, and has an operating rule says:

• If you’re on a white cell, make it black, turn right, and step forwards.
• If you’re on a black cell, make it white, turn left, and step forwards.

That’s it. It’s about as computationally simple as you can get and yet the output is so unexpected that computer scientists still don’t have much in the way of useful proofs about its behavior.

At face value, turmites look like a terrific fit for the sort of randomness we want to create. Furthermore, there are plenty of turmites that you can run for as long as you like, and never get repeating data. However, if you take a look at the kinds of patterns that turmites create, you may notice something about them. The patterns are all pretty dense. What I mean by this is that the balance of black and white squares that they generate is usually pretty much equal. Sure, some of them make denser patterns than others, but the density is never all that low. Furthermore, you definitely don’t get to choose in advance how dense the pattern is going to be. Your choice of ant algorithm decides that for you. You don’t have any say in the matter.

The reason for this is that in order for the ant to produce random-looking data, its behavior needs to be unpredictable. And its behavior can only be unpredictable if it has a nice rich mix of black and white cells to work with. Take away the mixture and the behavior stops being unpredictable.

One way to get very sparse data out of a turmite is to pick a rule that’s got a large number of different states. In other words, instead of only permitting you to put a one or a zero in each slot that the turmite visits, you can put one of a larger range of values, say, for instance, one of ten different values. Then, to get your sparseness, you throw away everything except one of the states when you examine the results. However, we didn’t like this solution either, as it required us to take the output of the algorithm and apply some kind of arbitrary filter to it. So we were stuck. We couldn’t even create turmites of the sort that we wanted, let alone causal sets.

Then, shortly after I got back to the US, a solution of sorts to the turmite version of the problem occurred to me. Whether the same kind of algorithm will turn out to be applicable to networks is unknown, but it seems like a an interesting starting point.

The idea here is that instead of having a rule for turning a slot in the grid on or off, instead you have a rule for picking up a bit or putting it down. This allows you to populate your environment with data as sparse as you like, and know that the density will never change as long as the program runs. There’s one other twist, so to speak. Rather than running the program on a grid of infinite size, you run it on a grid of finite size, but you hook up the edges of that grid such that leaving the top of the grid brings you back at the bottom of the grid shifted one row to the left. Likewise, leaving through the bottom brings you back a row to the right. The left and right edges of the grid are also hooked up the same way, so that the whole grid is slightly twisted.

An odd set-up, admittedly, but what it gives you is a turmite that takes whatever input you provide and mangles it for you without losing track of any of your bits. Because no bits are ever gained or lost, it also means that the ant should be reversible. We can write a program that can unmangle any mangled data we’re handed. It’s like a magic wand for turning order into chaos and back again—a kind of do-it-yourself entropy kit. In fact, it’s a little bit like a tiny universe with a finite supply of matter. Over time, everything becomes disordered, but it does so according to a rule that works as well backwards as it does forwards.

About fifty years ago, this would probably have been an awesome way of encoding messages. However, these days we have public key cryptography, so the utility of my algorithm is a little less obvious. However, there’s something about it that gives me a tingly feeling. It has practical uses, I’m sure of it. I’m just not sure what they are yet. Any ideas?

How to fold this approach back into a class of algorithms that will help build causal sets is something I’m still working on. I can use this method to approximate percolation dynamics by using the turmite to construct an adjacency matrix. However, that doesn’t help us build realistic spacetimes. Clearly, more work is required.

And now, for those of you who’ve been patient enough to read to the end, here’s another link to the simulation. Happy watching, and if you think of a use for this thing, let me know!

Causal Sets and Leaning Towers

Last year I had the incredible good fortune to spend a couple of months collaborating with Tommaso Bolognesi at CNR-ISTI, in Pisa, Italy. Tommaso runs his own research program into the interface between computation and physics and is a champion of the Digital Physics cause. He hired me to see if together we could answer a very specific question:

Is it possible to build networks that have the same properties as spacetime using simple algorithms, and if so, how?

I’ve had plenty to say on the subject of modeling space before this. However, what Tommaso was looking for was very specific. He wanted us to find ways to build causal sets. Causal set theory is probably the point of closest approach between digital physics and more mainstream quantum gravity research and it’s a fascinating subject. In a nutshell, causal set theorists believe that spacetime is most usefully thought of as a discrete structure and that the way to model it is to try to mimic the kinds of relationships between events that we see in relativity. To achieve this, they connect nodes using something called a partial order—a set of relationships that define which nodes must come before others, but which falls short of providing an exact numbering for all nodes.

Broadly speaking, the Causal Set Program uses two methods to build their sets. The first, called sprinkling, is to deposit nodes at random onto a surface, and hook them together based on the geometry of that surface. The other way, called percolation dynamics, is to add nodes one by one to a set, and randomly add links from existing members of that set to each new node.

Sprinkling is useful for exploring how causal sets behave but it has a huge problem: in order to construct the discrete structure of spacetime, you have to deposit your points onto a smooth spacetime first! Clearly, if we want to come up with a background-independent theory of physics, we need to build the sets some other way. On the other hand, percolation dynamics has all the nice statistical properties that physicists would like to see and doesn’t need a background, but sadly doesn’t actually produce graphs that look like spacetime (though people are working on that).

The right solution would seem to be to come up with a third way: a process that produces the right structures without needing a background surface. However, this comes with problems. The key features that differentiate spacetime-like causal sets from others are dimensionality and Lorentz invariance.

Dimensionality essentially says that we should expect the graph that we build to have some consistent number of dimensions, rather than just being a tangled mess. Lorentz invariance is a little trickier. What it implies is that if you build your network first and then lay the nodes onto a flat surface afterward, the positions of the nodes should appear random. There should be no way you can stretch or squish the network to make it look otherwise. This is vitally important because in order to treat every relativistic reference frame the same way, as special relativity says we must, we need about the same number of links between nodes in each frame.

Another way to say this is that, thanks to Einstein, we know that no matter how fast we’re moving, space will always feel the same to us. The way a causal set works is that each link corresponds to a step through time and space taken at a certain speed. So, if for some speed of travel, our network doesn’t have enough links, it’s definitely not going to feel the same to someone traveling through it. If this happens, our model has failed. The only way that people have ever found to make Lorentz-invariant causal sets is to have the network be random.

My collaboration with Tommaso was founded on a neat way around this problem that works like this:

• Because any causal set we can build is finite, it can only ever approximate perfect randomness.
• Furthermore, for a finite network of given size, we can always find some algorithm that can approximate that level of randomness through a deterministic process.
• Thus, no matter how big our network needs to be, we should still always be able to find an algorithm that could give rise to it.
• This will always be true so long as we believe that spacetime is discrete, that the universe has finite size, and that it has existed for finite time.

In essence, what this tells us is that just because the network we want to build needs to look random, that doesn’t mean that we can’t use a completely non-random method for building it. This is all great as far as it goes, but it leaves us with an enormous problem: how to find an algorithm that can build spacetime.

In the two months we had, Tommaso and I didn’t manage to crack this problem (otherwise you would have heard about it on the news by now) but we learned some fascinating things along the way. I hope to share some of them with you in my later posts.

However, in the mean time, there are plenty of really excellent introductory papers on causal sets that are very approachable for those who’re interested. While my favorite approach to discrete physics is a little different from the causal set methodology, I can recommend this field very highly to anyone interested in learning more about quantum gravity without taking on a full-time career as a string theorist.