Cellular Turing Machines(Creature Genetics and Development)

Rewritten on 1/12/11
Genetic code for these creatures is going to be an 11 character language based off brainfuck. The commands for the creatures is as follows:
  • '<' and '>' increment/decrement the pointer to the primary node.
  • 'v' and '^' increment/decrement the pointer to the secondary node.
  • '.' link the secondary node and the primary node. If the two already linked, do nothing.
  • ',' unlink the primary and secondary nodes if they are linked, else do nothing.
  • '+' and '-' increment/decrement the value of the primary node (note that this value is cyclic!).
  • '[' and ']' will preform looping functions, as in brainfuck. The loop terminates when the value a the primary node is zero when a check is made.
  • '*' is a special character--it does nothing in the developmental code. Instead, it's used to mate creatures, maybe even to speciate them in a later version: '*'s are point of possible crossover. Actually, this command is where I can't wait to see what the program does. How will these characters, which have nothing directly to do with fitness, position themselves in the genome? Will it be random, haphazardly strewn around in the middle of loops and such? Could these start to partition off genes somehow, segments of the program which are independent from each other? I hope it's the latter. It would be really neat to see the evolution of alleles and such--some kind of more complex genetic code.


Cellular Turing Machines(Overview)

One of my other fascinations is evolutionary processes. In the past, I have written simple, computer programs in which short strings compete to become simple words, but I want to try something more complex. One of the big holdups? I've never developed a sufficiently complex and interesting way to representing these creatures before now.
One way I'd like to represent a creature would be as a complex set of nodes and links. Treating nodes as points, and links as springs or pistons between the nodes, creatures could be made to move. This is all really nice on paper, but I've always run into an implementation problem: How to give the creature a simple to implement but functionally meaningful way to manipulate its own movement.
This is where a cellular automata come in. These simple games can work as a method to control movement. If each node is given a state, and alters that state based on a simple set of rules, as in the game of life, the links can change their length based on the states of the nodes they are connected to. Of course, the game played on the creature needs some basic properties that some games just don't have. Conway's game of life assumes that each node has exactly four neighbors, while Langton's ant needs to have an order defined on the nodes. Any game that's to work needs to have coherent and interesting behavior regardless of the number of nodes, and it needs to have consistent behavior regardless of ordering. While not required, I'd love it if it were capable of sending signals down a single strand of nodes, and it'd be nice if it were possible to make some kind of resetting muscle.
I have at least one game that fits this bill: the Cyclic Cellular Automaton. This is what I hope to use in my program. Next post, I'll explain how I plan to build creatures from a linear genetic code.


Professor Stewart's Cabinet of Mathematical Curiosities

This book, written by Professor Ian Stewart, is possibly one of the best books I have ever read. Despite this, it has a format quite unlike an ordinary book; it has no coherent theme, and is full of tricky, and sometimes unsolved, math problems. When I first picked it up, I read the first few problems, and was about to set it down when I decided to flip just a few more pages ahead, and fell upon an essay about Fermat's last theorem.

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!


A note on my editing policy...

As this blog is a bit like a notebook for me, I will not hesitate to edit old posts, and may not leave evidence of my doing so. Most of these changes will be minor (i.e. adding tags, fixing grammer, etc.). However, should I change a post in some major way, I will try to write a note explaining why I did so. No promises though.

A sketch

Just a quick image. This is something I sketched a while back. I am not completely certain what exactly it is supposed to be. Your call.