Cellular Turing Machines(Introduction)

EDIT: I'm going to come back to this project soon and really finish it up, because I think it's worth doing. All my posts are bloated and badly formatted, and I've read up on a lot of relevant material, so I'm going over these with a fine tooth comb and clean them up, post clean code. Basically, I'm going to bring this up to speed, and hopefully release a nice clean application with some features that I really have wanted to see in other programs.

I have known for some time about Conway's game of life, but today I learned two things that surprised me.The first (and less surprising of the two for me) is that the game of life is a Universal Turing machine. In more common terms, it can act as a computer. I guess this doesn't surprise me so much because, in seventh or eighth grade, I remember making something very much like an AND gate in the game of life: Single cell inputs, and a single indicator cell. My gate destroyed itself in computation, but I saw no reason why a stable one could not be constructed (at the time, I was trying to do something other than make a gate, I cannot recall what).

The second, and somehow more surprising discovery (for me at least) was that Conway’s game is not alone. While reading though the book Professor Stewart’s cabinet of mathematical curiosities, I came across a short essay on a mathematical “creature” known as Langton’s Ant. The rules for the ant are simple, arguably simpler than those for the game of life and there is another amazing feature of the ant. Given long enough, the ant always seems to build a “highway” (see the link if you are confused). No one has ever proved this to be true, but no finite configuration of tiles is known that performs otherwise.

Another thing that struck me about the ant: If one imagines the ant to be flipping tiles on a glass plane, then looking at the plane from underneath yield the exact inverse of the view from above. Black tiles are now white, white now black, but the ant obeys the same set of rules. On further investigation of both games, I discovered that even more games exist. Some of these others have similarly interesting properties, like Day & Night, where the inverse of a pattern behaves in exactly the same manner as the original. So anyway, while reading about these various games I had an interesting idea. All the games I have encountered so far are played on a simple grid. As I considered various ways to implement such a grid in a program, one that stood out was a linked data structure, where a node indicated each square, and links showed which squares were adjacent. A second or so later I realized I could construct "loops" from the connections in such a system, and therefore assess the topology to the shape, at least in theory.

For example, most of the games with Langton's ant that I found allowed the ant to roam across the screen, wrapping in both directions as it came to the edge.This describes the topology to a torus: some loops (sets of connections between squares) cannot be "deformed" to a point, in fact, all loops that pass over the edge of the screen cannot be deformed in this manner. If you are confused, try this image, which comes from this page (WARNING: a LOT of math I don't understand EDIT: Oh. Now I do!). The picture shows a grid, which is what is displayed on the screen, and the topological interpretation, a torus. Note that straight lines on the square are circular "loops" on the surface of the torus, and that these loops cannot be moved (imagine rubber bands around a doughnut) in such a way as to squeeze and stretch them down to a point while they remain on the surface.

In any case, I got to thinking about different shapes I could deform the network into, including sphere like shapes, mobius strips (EDIT: I now know I was really thinking of a projective plane here- A kind of double mobius strip that can't be neatly embedded in three space. It's neat. Check it out.), and twisted versions of these shapes (while topology may not care about twists and deformations, the Game of life certainly would), when I had an idea. It will take a while to explain, even on its own, so I will end this post here and pick up the rest later on in another post.Watch for part 2 soon!