This website will be obsolete by 2018-03-26. Please refer to http://web.archive.org/web/*/http://VincentVerheyen.com/

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

Post date:

9/10/2016

Last modified:

7/3/2017

Contents

# 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:

**Caption:**The turmite specified as {{{1, 8, 1}, {1, 8, 1}}, {{1, 2, 1}, {0, 1, 0}}} shown at 10211 timesteps [showing a Fibonacci spiral].**Source:**Uploaded by user "Ferkel" at Wikimedia Commons on 15 October 2009.

# 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 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 "

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:For example, the triple {1, 8, 1} says:

- 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

- set the color of the square to 1;
- turn left (8);
- adopt state 1 and move forward one square.1

*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:

State/color of cell | |||
---|---|---|---|

0 (black) | 1 (green) | ||

State/color of termite | 1 (blue) | $\{1, 8, 1\}$ | $\{1, 8, 1\}$ |

2 (gray) | $\{1, 2, 1\}$ | $\{0, 1, 0\}$ |

## 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:This brings us to the subsequent generation.

- set the color of the square to 1;
- turn left (8);
- adopt state 1 and move forward one square.

### 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 31
^{th}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