Superluminal Computing

So today an interesting article on the wonderful Arxiv Blog that caught my eye.
http://www.technologyreview.com/blog/arxiv/24903/
It’s a report on a piece of theoretical physics which suggests something that I’ve long suspected that current theories implied. Namely, that if the universe is smooth, that you should be able to perform computational miracles.

The way I tend to describe this idea is as follows:
How do you tell if the universe is smooth or discrete? You can’t build an apparatus directly to test for smoothness, because whatever apparatus you build, there will always be some level of detail that it fails to examine. Thus, it might be that the universe is discrete, but simply made of granular events at some scale that you haven’t yet measured.

Thus the only way that you can determine whether you’re in a smooth universe or not is by doing something that would be computationally impossible in a universe that contained a finite amount of information. In other words, can you beat Turing’s Halting Problem, or Godel’s Incompleteness Theorem? If you can, then you can go to bed at night comfortably certain that the Calculus enthusiasts are right. The universe can do impossible things, and therefore physical theories that depend on continuous variable are just fine. On the other hand, of course, if you can’t beat Godel’s theorem, then you have to consider the ghastly possibility that the application of calculus to physics is only a handy approximation, as it is in every other field where it’s applied, rather than an absolute truth.

The Arxiv article is the first time I’ve seen people in the theoretical physics community come to these conclusions on their own. What’s wonderful about it is that it points the way toward a falsifiable experiment some time in the future that might actually settle the question. It hinges on the fact that a superluminal computer should be able to pack an infinite number of calculations into a finite period of time–something that digital physics forbids. Thus, if we can build an optical computer and an electron bath, neither of which seem impossible, then we can feed our computer a theorem-checking program and a nice list of Godel sentences. Then we go grab a bite of lunch and when we come back, the answer to one of the most contentious questions in physics has been answered for us. Hoorah!

It perhaps doesn’t come as a surprise that I’m skeptical of the idea of hyper-computers. Nevertheless, it’d wonderful to be wrong. A universe capable of miracles might be a fun place to live. Roll on optical computing technology. Your first grand application awaits!

Steeds & Riders

In my last post I outlined a paradigm that we can use to build ‘pseudo-particles’ with properties a lot more naturalistic than those we generally find in Cellular Automata. However, as I mentioned, this paradigm comes with a price: an apparent sparsity of the kinds of interesting, emergent patterns that systems like CAs give you.

This sparsity is only to be expected. Irregular graphs of the kind I use are inherently noisier than the tidy lattices employed by CAs. That noisiness gives us enough robustness to model curved space and approximate quantum uncertainty, but means that we can’t rely on exact patterns of cell activation to represent physical phenomena. However, this isn’t to say that we can’t build interesting and exciting patterns in this paradigm–far from it. And in this post, I’m going to explain how it can be done.

The first step is to point you at the slides I used in my talk at the JOUAL conference in Italy last year. You can find them here:
http://www.alexlamb.com/science.html

This talk covered some research I did on extending Jellyfish–most notably to create pseudo-particles on three dimensional graphs that polarize and retain their orientation as they move. Just as they can fly in any direction, they can polarize in any direction too, without requiring any change to the algorithm.

The core concept that I share in the slides to achieve this couldn’t be easier: you put one Jellyfish inside another. I call this a ‘steed-rider relationship’. You advance an ordinary pseudo-particle with simple iterative steps to move it forward, (that’s the steed), but you also adjust the position of pseudo-particle the same size that’s trapped inside it, (the rider). Half of the rider’s front nodes are located in the front node set of the steed, the other half are in the back. That’s it. Voila: polarization. The particle self-organizes to give you a nice naturalistic property that’s unexpectedly robust.

What’s also interesting about this kind of particle relationship is that the steed’s update algorithm isn’t affected by the rider it carries. This means that the rider manifests as an intrinsic property of the steed, rather than as a physical sub-particle. You can break the steed up so that it’s in multiple locations at once and the property will be retained. This gets useful if you extend the model a little further.

By creating a rider that’s much smaller than its steed, and changing its update rule a little, you can pretty easily create a rider that moves around inside its steed as it travels. And because in three dimensions the steed always tends toward having a circular profile, the rider ends up traveling around the edge of the steed along a helical path. Voila: intrinsic angular momentum, AKA spin.

Sadly, this kind of spin isn’t quite like that we see in physical particles, because for Jellyfish instances it can only be aligned with the steed particle’s direction of motion. Nevertheless, by increasing the number of riders that the steed carries, you can build particles for which angular momentum comes in tidy discrete quantities. Use one rider and the momentum is always clockwise or anti-clockwise (-1 or 1). Use two riders and the momentum can be in one of three states, both anti-clockwise, both clockwise, or in opposite directions (-2, 0, 2). Use three and you get the following pattern: (-3, -1, 1, 3). This is the same pattern that we see for spin number in subatomic particles.

I should re-iterate a point here that I made last week. Nice though these apparent similarities between these discrete systems and physics are, they’re not illustrative of anything except potential. This work is still a long way from being physical science. Furthermore, the simulations are costly and still somewhat unreliable. The best video I have of particle spin is here:
http://www.youtube.com/watch?v=gsCwILrSuBM

As you can see, at this scale, the rider has a tendency to flip direction from time to time, reversing the particle’s spin. Clearly much larger simulations are needed to test what this approach is truly capable of.

Nevertheless, the doors seem to be wide open to further experimentation. For instance, by creating riders that only travel in packs of a certain size, you can build particles with flavors that obey the properties of mathematical groups. That could be useful further down the line if we get as far as trying to emulate the Standard Model. In short, there seems to be plenty of fun work to do here and I’ve barely scratched the surface.

If you’d like to see a preprint of the paper I submitted to the JOUAL proceedings, just let me know. Or, if you’d like to see some open-source code for building this kind of simulation, that can be arranged. If you’re at all intrigued by these kind of simulations, I encourage you to try them out for yourself. There’s a world of fascinating science out there waiting to happen, and a lot of it can be discovered right there in your living-room.

Some Results

I’ve recently heard requests to put some concrete results on this blog, and they are splendidly welcome. When covering this topic, the temptation to cover one’s philosophical bases is almost overwhelming, but the foundations can wait. This blog entry is about some of what I’ve achieved.

It’s important to say upfront that the research I’ve been doing is not physics. At least not yet. I don’t have a grand theory for how the universe works, and I’m not trying to advertise one. What I’m trying to do instead is make a point about tools.

Physics is founded on Calculus and continuum mathematics because they are tools that deliver results. They have delivered more concrete progress than any other modeling system that the human race has ever developed. However, now they are failing. The standard model was presented in its current form in 1974. Relativity and Quantum Mechanics have resisted integration since around 1905. Thus, the most important frontier in physics has yielded only limited progress in the last hundred years, and virtually none in the last forty. String Theory, while terribly grand and clever, is so amorphous that it predicts ten to the five hundred different possible sets of physical laws and has no predictive power to speak of. In my opinion, this is because the tools in use are reaching the limits of their applicability.

Nevertheless, we cannot expect physicists to believe this, or to change the tools they use, because at this point, swapping to any other modeling system entails a massive step backwards. This step is one that only a few very brave souls are willing to take. (Frankly, they’re braver than me because I’m not a career physicist and I have nothing to lose.) Therefore, it’s very likely up to someone else–someone outside the physics community–to start producing tools that can do what continuum mathematics cannot.

The first, most important part of this task, IMO, is catching up with the last three hundred years of scientific progress. As is hopefully clear from this blog, the tools that I believe will help are those that have been developed in Computer Science. The goal then is the replication of the total set of observed symmetries of nature in a discrete, iterative system that is no more complex than strictly necessary. This includes rotational and Lorentz invariance, the wave properties of Quantum Mechanical systems that are customarily modeled through the use of Hilbert Spaces, and everything else. This includes all those symmetries employed by Gauge Theory such as SU3, if such things prove necessary under the new system. Physics hinges on symmetry. Once the symmetries can be painlessly reproduced, things will go more smoothly.

The easiest place to start seemed to me to be rotational invariance, and this is what my first paper was about. The aim was to produce a discrete medium and an iterative function that could be applied to the elements of that medium that would produce a pattern that moved equally well in all directions. For those of you familiar with Cellular Automata (CAs), the goal, if you like, was to produce a universal glider that could travel equally well in any direction, rather than just in diagonal lines. The difficulty here is that discrete systems have a limited number of degrees of freedom. That makes travel in more directions than you have degrees of freedom a challenge.

Various systems have been tried to produce such a universal glider. One such system is to use a grid as the discrete medium and to define a glider with motion described by some number of steps along each axis with each turn. For instance, to go North North East, the glider might take three steps North for every step East. One problem with this approach is that to change direction just a small amount can require enormous changes in the ratios of motion along each axis. Thus, in order to produce motion in all directions, the glider needs an effectively infinite memory in which to store what part of its movement cycle it’s in at any time, along with a mechanism for converting between axis ratios when a change in direction is required.

Another problem is that this model has trouble compensating for the kind of spatial distortion witnessed in Relativistic systems. Specifically: there’s no room in the model for spatial expansion or contraction. That means no Big Bang, at least, not one that’s compatible with cosmological observations. Ideally, we’d like to choose a model that rules out none of the kinds of behavior we’d like to later produce.

Another approach that’s been explored is to once again use a grid, but to have the glider change axis of motion with each step based on some probability function. Thus when headed NNE, this glider has a 75% likelihood of going North, and a 25% likelihood of going East, but we don’t know which way it’ll turn for each step. While this approach gets around the problem of the awkward issue of ratios on different axes, it replaces it with dependency on a continuously varying probability value. Such variables are exactly the kind of tools we’d like to avoid using. Furthermore, the use of a grid once again rules out large chunks of Relativity.

What I do instead is use a densely-connected, irregular graph as my discrete medium, and define my glider as a function operating over sets of nodes on that graph. I define two sets, front nodes and back nodes, if you like, and then employ a simple algorithm I call ‘Jellyfish’ to find a new set of front nodes with each iteration.

The formula for Jellyifish is outlined in my NKS Midwest 2008 presentation slides, which you can find here:
http://www.cs.indiana.edu/%7Edgerman/2008midwestNKSconference/Lamb_Slides.pdf
The slides outline the formula, so I won’t duplicate it here.

If you want a more in depth explanation, my paper on this system will be published in the journal Complex Systems shortly, but if you don’t want to wait, send me your email address and I’ll send you a preprint. Alternatively, if you’d just like to see the results, you can alway go to YouTube and watch the glider, or ‘pseudo-particle’ moving for yourself.
You can find it here:
http://www.youtube.com/user/alexlamb#p/u/8/Y_yCxcjYPmo

Using an irregular graph means that the bulk properties of the medium are the same in every direction. There are no preferred directions of motion, so most of the anisotropy problems associated with Cellular Automata disappear immediately. Furthermore, the medium can be distorted in any way we like. Its geometry is not fixed. This means that nothing is stopping us from exploring the implications of Relativity later. Defining a pseudo-particle in terms of operations over sets of nodes also allows us to define orientation of motion as a group effect, and thus to describe motion over an arbitrarily large number of directions with ease.

To some, the Irregular Graph/Jellyfish approach feels rather more random than Cellular Automata, more fundamentally complex, and certainly less likely to produce pretty patterns. However, though we lose a little in terms of algorithmic succinctness, we seem to gain at least as much in terms of descriptive power, and, as you’ll hopefully see in later posts, what we gain often looks eerily like physics.

The Jellyfish algorithm works equally well in 2, 3 or any dimensionality, as well as on curved surfaces. It shows potential compatibility with Lorentz invariance, as I illustrate in the slides, and even some properties similar to those of Quantum Mechanical systems. What Jellyfish doesn’t have is wavelength, polarization, or the habit of following all paths at once. It’s a long way from being a physical particle, and that’s okay because it’s not supposed to be one. However, what it does demonstrate is that getting something like basic particle behavior out of a discrete system is extremely easy. Natural, even.

I believe that this work work leaves us with a new class of automata to explore, and an important question to answer: What is the simplest algorithmic model that fulfills the constraints that physical law imposes on a system, without resorting to the classical formalism of that system. In other words, if we tie one hand behind our back, and forgo the use of differential equations, axes, and smooth numbers, can we still wield the rapier of science? I bet we can. In solving this and similar puzzles, we may be opening the doors to a new era of science. The answers are just a few simple experiments away and anyone with a computer and a little curiosity can start looking.