Cellular automata – Langton’s Ant
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.
Visualizations
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.
“Magic” square – bitmap processing
 
 
Figures – bitmap processing
 
 
 
Letter “E”
 
Labyrinths
 
 
Highways
 
 
Triangles
 
 
Blocks
 
 
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
Related posts
Comments
One response to “Cellular automata – Langton’s Ant”
Leave a Reply
Website for You!
CMS WordPress, custom design.
-
TOP 5
% 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))