On 1936, Alan Turing publshied an article with the title “On Computable Numbers, with an Application to the Entscheidungsproblem” in which he formally defined what an Algorithm is. There were another attempts before Turing. Kurt Gödel propposed a definition for algorithm some years before Turing, and on 1935, the american mathematician Alonso Church, generalizing Gödel’s idea, propposed his deffinition of algorithm. Turing made his deffinition independetly of the other two, although Gödel’s work in other areas was highly influential on Turing during his research. If these other scientists formalized the concept of algorithm before Turing, why we use his deffinition? Because his deffinition is most intuitive one of computation and algorithm, associating the task with the execution of a machine, Turing’s Machines (TM) as we called them today. The other deffinitions propposed for Algorithms and computers were highly abstract in a mathematical sense and were difficult to grasp for non-mathematicians.

In his book, “The Bit and the Pendulum“, Tom Siegfried gives another good reason besides the simplicity. He wrote that the scientifical paradigms of our society have been based on machines since the Renaissance. First, it was the Clock and the Mechanical description of the universe. Then came the Thermal Engine and the Thermodinamics description of systems. After that, science used Eletromagnetism and the Electrical Engine. Now, the dominant paradigm in most of sciences is Information and Computers are used as an abstraction to explain many different aspects of the universe.

Ok, but, what’s a Turing Machine? A TM is a device that can manipulates symbols on a strip of tables according to a table of rules. The Church-Turing thesis (nobody has proved this to be true, but nobody either has found a counter-example, that’s why we call it a thesis) states that a TM can represent any algorithm. There’s also another kind of TM, The Universal Turing Machine (UTM), that if provided the description of another TM and its set of inputs, the UTM can simmulate any other TM. This concept, of a machine that can simmulate other machines given a description was the fundamental concept that lead other scientists create the first eletronic computer.

And finally, what’s a Turmite? A Turmite is a Turing Machine that has an infinite sheet of paper to read symbols from and write symbols to instead of just a strip, like a conventional TM, and also has a state. It was developet independently by many researches from later seventies throughout the eighties. One of the first scientists that propposed this concept, using a infinite sheet of paper instead of a strip, was Christopher Langton with his Langton’s Ant. Allen Brady and Greg Turk developed the same ideas independetly from Langton. A turmite is basically an infinite two dimensional grid of cells, which can be retangular, triangular or hexagonal with an agent, called ant or vent. The ant has a set of rules that lets it chooses the next cell it will visit based on the its current state, basically its direction, and the state of the cell it is in. The ant also changes the state of its current cell before leaving, and with this simple schema, any computation, algorithm, can be simulated. The ant’s direction can be based on a local coordinate system, also called relative, or in a global coordinate system, absolute. The patterns formed by these ants are basically chaotic or spiral growth and highways, but sometimes a turmite can give a periodic pattern.

The Rule Table Repository has many sets of rules for not only turmites, but for many kinds of cellular automata and other algorithms for Artificial Life.  The pattern drawn by the turmite of this post is based on these rules, and the code in Processing to achieve this is bellow. Although is very similar to Langton’s Ant, it’s a different patter. If you don’t have patients or time to see the pattern (it takes 5 minutes to reach the state showed in this page), here’s a short video I’ve recorded and editted to show only some parts.

If you have any questions or comments, send me an email through Contact Menu. My next, and final, post about these simple aglorithms of Artificial Life will be about Cellular Automata. See you there.

[java]
int WIDTH = 800, HEIGHT = 600;
int squareHeight, squareWidth;
int numCol, numLine;
int antX, antY;
color[][] gridColor;
color Black, White, Ant;
int antDirection, North, South, East, West;
int antState, Dead, Alive;

void setup()
{
// Grid Information
numCol = 60;
numLine = 60;
squareWidth = WIDTH / numCol + 1;
squareHeight = HEIGHT / numLine + 2;

// Start position of the Ant
antX = numCol / 2;
antY = numLine / 2;

// Colors of the Grid
Black = color(0);
White = color(255);
Ant = color(255, 0, 0);

// Ant Direction. Too bad Processing doesn’t have enums
North = 1;
South = 2;
East = 3;
West = 4;

antDirection = North;

// Ant State
Alive = 1;
Dead = 0;
antState = Alive;

gridColor = new color[numCol][numLine];
for (int row = 0; row < numLine; row++)
{
for (int col = 0; col < numCol; col++)
{
gridColor[col][r] = Black;
}
}

size(WIDTH, HEIGHT);
background(0);

// Green (Matrix) Line
stroke(80, 80, 80);
}

void draw()
{
background(0);

// Draw the Grid
for (int row = 0; row < numLine; row++)
{
for (int col = 0; col < numCol; col++)
{
fill(gridColor[col][row]);
rect(col * squareWidth, row * squareHeight, squareWidth, squareHeight);
}
}

// Draw Ant position in this frame
fill(Ant);
rect(antX * squareWidth, antY * squareHeight, squareWidth, squareHeight);

// Compute the new position of the Ant
iterate();

// Reset if Ant has reached a border
if (antX < 0 || antX >= numCol || antY < 0 || antY >= numLine)
reset();
}

void iterate()
{
if (antState == Alive)
{
if (gridColor[antX][antY] == Black)
{
// Don’t change the color of the square in this case

// Set ant’s new state
antState = Dead;
}
else if (gridColor[antX][antY] == White)
{
// Change the color of current square to Black
gridColor[antX][antY] = Black;

// Set ant’s new state
antState = Alive;
}

// Move Ant to relative North
switch (antDirection)
{
// Relative North
case 1:
antY–;
antDirection = North;
break;

// Relative South
case 2:
antY++;
antDirection = South;
break;

// Relative East
case 3:
antX++;
antDirection = East;
break;

// Relative West
case 4:
antX–;
antDirection = West;
break;
}
}
else if (antState == Dead)
{
if (gridColor[antX][antY] == Black)
{
// Change the color of current square to White
gridColor[antX][antY] = White;

// Set ant’s new state
antState = Dead;
}
else if (gridColor[antX][antY] == White)
{
// Don’t change the color of the square in this case

// Set ant’s new state
antState = Alive;
}

// Move Ant to relative East
switch (antDirection)
{
// Relative North
case 1:
antX++;
antDirection = East;
break;

// Relative South
case 2:
antX–;
antDirection = West;
break;

// Relative East
case 3:
antY++;
antDirection = South;
break;

// Relative West
case 4:
antY–;
antDirection = North;
break;
}

} // else if (antState == Dead)
}

void reset()
{
antX = numCol / 2;
antY = numLine / 2;
antDirection = North;
antState = Alive;

for (int row = 0; row < numLine; row++)
{
for (int col = 0; col < numCol; col++)
{
gridColor[col][row] = Black;
}
}
}
[/java]