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.

 

neighborhood.png
2D Neighborhood model

 

Visualizations

 

ants.pngants_black.png
Four active Lantont’s ants

 

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

 

magic_square_1.png magic_square_2.png magic_square_3.png
Magic square

Figures – bitmap processing

circle.png icicle.png surface.png apple.png
Circle, icicle, landscape, apple

Letter “E”

letter_e_1.png letter_e_2.png
Letter “E”

Labyrinths

labyrinth_2.png labyrinth_3.png snake.png
Labyrinths

Highways

highway_1.png highway_3d_2.png highway_4.pnghighway_2.pnghighway_3.pnghighway_3d_1.png
2D and 3D highways

Triangles

kite.png highway_3d_3.png triangles_1.png
Kite, highway, triangle set

Blocks

block_1.png block_2.png triangles_2.png
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.


Related posts

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *