Visualization of a simple algorithms of two-dimensional Turing machine can create impressive images. The “movement” of the head of Turing machine can be irregular in the early stage, but it start making characteristic patterns after millions of iterations. In this post I will show how to define a table of rules the Turing machine for a simple cellular automaton that isô Langton’s antô and sample visualizations of the work of other machines.

## Turing machine model and image processing

The Turing machine modelô is used to perform algorithms. We can define the following attributes of this model:

• Set of states – possible states that can adopted by the head
• Set of input symbols
• Set of outputs symbols
• Initial state

In the process of image processing by a Turing machine, the tapeô will be a bitmap. The machine based on the state of the head and a value of the pixel at the current position, set the output value of the pixel accordance with a defined rule, update state of the head and move it to the desired location in space. To reduce the size of the input alphabet, you can use a modulo operation on the RGB value of a pixel.

### Lanton’s ant

Lanton’s ant is a simple cellular automaton. It moves in an infinite grid divided into square fields. I will show how you can define the rules table of the two-dimensional model of a Turing machine for this.

#### Rules

• if ant is located at a black field:
• change color of field to white
• turn right and move forward one unit
• if ant is located at a white field:
• change color of field to black
• turn left and move forward one unit

As you can see, the ant flips the current color to the opposite and moves only orthogonally. This rule is very easy to transform to the model of the Turing machine.

#### Langton’s ant – table of rules

State öý öÇ ü
0 1 0 1 0 1
0 3 1 1 0 3 4
1 0 2 1 0 2 5
2 1 3 1 0 4 3
3 2 0 1 0 5 2
• State: current state of the head
• öý: output state of the head
• öÇ: output value of the field
• ü: output position of the head

The value of each attribute model, depends on the value of field at the current position of the head. We have to define rules for each symbol from the input alphabet. The value of attributeô üô is related to the index of fields defined in the neighborhood model.

#### Neighborhood

The ant can move only two possible positions, which are located next to it. Excluding the angle of the ant, it can move in four different directions. The following figure presents a two-dimensional model of the neighborhood used in the Langton’s ant rule and in the other visualizations in the gallery.

## Gallery of Turing machines

In this section I will present gallery of the work of Turing machines with different rules. Images come from my own program to visualize the work of Turing machines.

## Summary

Very simple rule after hundreds of thousands or millions of iterations of chaotic movements can create amazing patterns and shapes. Presented visualizations are part of the possible combinations. If you know other an interesting rule –ô send me a message.

### Website

Do you need a nice Website? See demo at: this wepage ### One response to “Cellular automata – Langton’s Ant”

1. Graham Medland says:

% Octave / Matlab code for langtons ant
E=256;
A=0.5*(E+1);
B=0.5*(E-1);
K=pi/4;
N=12288;
t=1:1:65536;
Psi_d(t)=1;
k(t)=0;
k(1)=32896;
for t=1:1:N;
Theta = trace(diag(Psi_d));
Psi_t = exp(i*K*Theta);
X=(Psi_t + B*Psi_d(k(t+1)+1))*(conj(Psi_t) + A*Psi_d(k(t+1)+1))-(A*B);
k(t+1)=mod(k(t)+round(real( X-1 ) + imag( X-1 )),E^2);
Psi_d(k(t+1)+1)=real(exp(2*i*K.*(1+Psi_d(k(t+1)+1))));
endfor;

imagesc(reshape(Psi_d,E,E))