Why does Ed Pegg Jr.'s turmite (Turing machine) creates a Fibonacci Spiral—Or does it?

Last modified: 
7/3/2017

Introduction

One can find Ed Pegg Jr.'s article on turmites at the MAA. Among the many turmites created by Ed Pegg Jr., he has discovered a certain 2-state 2-color which creates a Fibonacci spiral:



Algorithm

In the software Golly, one can simulate that turmite. Its instructions read as follows: Specification string: {1, 8, 1}, {1, 8, 1}, {1, 2, 1}, {0, 1, 0}

This string is a curly-bracketed table of n_states rows and n_colors columns, where each entry is a triple of integers. The elements of each triple are:
  • new color of the square;
  • direction(s) for the turmite to turn;
    • 1 = no turn;
    • 2 = right;
    • 4 = u-turn;
    • 8 = left.
  • new internal state of the turmite
For example, the triple {1, 8, 1} says:
  • set the color of the square to 1;
  • turn left (8);
  • adopt state 1 and move forward one square.1
This description might seem a bit arbitrary. This is since it doesn't explicitly specify that the specification string should be interpreted as a matrix (or as Tim Hutton2 had explained to me: as a "look-up table of how to behave in each situation"), and how to actually use that look-up table.

Specification string table/matrix

The specification string can be read as the following matrix:

$\begin{bmatrix}{\{1, 8, 1\}} & {\{1, 8, 1\}}\\{\{1, 2, 1\}} & {\{0, 1, 0\}}\end{bmatrix}$

The first number in each of these four triplets specifies how to change the colour of the square the termite is on. The second number refers to the movement to make. Their third number refers to what state (colour of the termite) should be changed.

When using Golly, it might also be helpful to understand that the color "1" should be read as green, and the color "0" should be read as black, by default. The state "1" is represented by a blue termite, and state "0" by a gray one.

To understand what triplet to execute under which circumstances, the following table might be of help:
Specification string table/matrix
State/color of cell
0 (black)1 (green)
State/color of termite1 (blue)$\{1, 8, 1\}$$\{1, 8, 1\}$
2 (gray)$\{1, 2, 1\}$$\{0, 1, 0\}$
For clarity, I will explain the instructions as per some screenshots of the first few steps, when executing this pattern in a standard Golly set-up. Also: after executing any triplet, the termite moves forward one square in whatever direction it is facing.

First few steps as an example

Generation 0



As visible above: the "state" of the termite is "1" (since it is depicted blue), and it is located on a cell of color "0" (namely a black cell). This means one needs the following triplet (as per the "Specification string table/matrix"): $\{1, 8, 1\}$

As per above: ... [...] the triple {1, 8, 1} says:
  • set the color of the square to 1;
  • turn left (8);
  • adopt state 1 and move forward one square.
This brings us to the subsequent generation.

Generation 1



Now the termite is again on a black cell (thus one will again need a triplet from the second column of the specification string matrix). However, now, the state of the termite is "2" (gray) ... thus, one will need the triplet $\{1, 2, 1\}$. Thus, analogue to the above:
  • set the color of the square to 1;
  • turn right (2);
  • adopt state 1 and move forward one square.

Generation 2



The circumstances are exactly the same as during generation 1, thus the same algorithm will be executed.

Generation 3



Idem dito.

Generation 4



Now, the termite is still in state "2" (gray), but the cell it is located on is in state "1" (green). Looking to the "Specification string table/matrix", this means we need to execute the triplet ${0,1,0}$. Thus:
  • set the color of the square to 0 (black);
  • do not turn (1);
  • adopt state 0 (blue) and move forward one square.

Generation 5



And so on and so forth ...

I suspect that the use of the specification string is clear now. For further execution of the algorithm, I propose to use Golly. If one does not desire to install the software, one can equally well use the test drive function of "Golly Online" @ rollApp. Subsequently, navigate to Patterns > Turmites > FibonacciSpiral.rle; and e.g. hit play (or use your spacebar) to start the algorithm.

How to understand the resulting formation of a Fibonacci spiral?

The main question arising from the appearance of a Fibonacci spiral out of these simple algorithm is of course: why does this occur?

Tim Hutton

I asked questions about this to Tim Hutton, and I will take the liberty of quoting a small passage from one of his replies: As to why it makes a Fibonacci spiral, that's a different question! By watching it you can see it grows squares and draws their diagonal, and then starts a new one. But there is no way of designing such a small turmite to do such a thing, this was a discovery. In general there is no way of predicting the long-term behavior of a turmite other than by running the simulation. Wolfram calls this the Principal of Computational Equivalence.3

Ed Pegg Jr.

I would like to thank Ed Pegg Jr. | | , who has confirmed that his discovery was unexpected: It was a coincidental discovery. All of these turmites are too small for intentional programming.4

... how to think further?

If anybody would yet be able to crack the nut and grasp as to why the Fibonacci spiral must result from this Turing machine, it would be a great honour if you could inform us of your thoughts.

Or does it?

As Professor Keith Devlin has pointed out in his lecture "The Golden Ratio & Fibonacci Numbers: Fact versus Fiction" of 8 October 2012,5 quite a number of people believe to notice Fibonacci/golden spirals or Fibonacci/golden ratios more often than that they are actually present.

A quick glance6 at Wikipedia's page on the "Golden spiral" shows us a picture of a very close approximation of a golden spiral (in red), and another spiral which is not a golden spiral but constructed quite differently (in green). The two spirals indeed look quite similar (at this scale) when one doesn't take enough time to examine the formulas from which they were constructed.

This begs the following question: is the pattern created by the turmite really creating a Fibonacci Spiral, as its name purports; or is it merely wishful thinking? And what method to use in a quest to verify either hypothesis? Asking these questions to both Ed Pegg Jr. (and CC'ed to Tim Hutton)7, I have received no further reply.

Footnotes

  • 1. In Golly, it is located under "Patterns" > "Turmites" > "FibonacciSpiral.rle". The file can also be consulted e.g. as cloned by Brenton Bostick (one of the contributors to Golly), or downloaded elsewhere on Sourceforge.
  • 2. Tim Hutton | is one of the contributors to Golly, and holds a PhD in biomedical informatics awarded at the University College London.
  • 3. From private mail correspondence, 18 August 2016.
  • 4. From private mail correspondence, 10 October 2016.
  • 5. This lecture was also recommended by Pawel Sobocinski in the 31th episode of his Graphical Linear Algebra, entitled "Fibonacci and sustainable rabbit farming".
  • 6. As of 14 October 2016.
  • 7. Correspondance as of of 14 October 2016.

Add new comment