TwoDimensionalTuringMachines
- 12th March 2018: Rosalie Fay reports new records for hex-grid 2-state 3-color relative movement busy beavers: one with 59 million steps and another with 227,345 non-zero cells written. Also a new record for triangular-grid 2-state 3-color relative movement busy beavers: 21 million steps and 44,594 non-zero cells written.
- 6th March 2018: Catsarefluffy discovers two new record-breaking extinction turmites for 1-state 2-colors and 2-state 2-colors.
- 20th Feb 2018: Rosalie Fay reports a new record for hex-grid 2-state 3-color relative movement busy beavers: 2 million steps and 55,753 non-zero cells written.
- 19th Feb 2018: Rosalie Fay reports a new record for 2-state 3-color relative movement busy beavers: 59.35 million steps and 888,629 non-zero cells written.
- 10th Feb 2013: Georgi Gochev reports a new 2-state 2-color relative-movement non-halting busy beaver: 7.735 billion steps.
- 8th Feb 2013: Georgi Gochev reports a new 2-state 2-color relative-movement non-halting busy beaver: 240 million steps.
- 6th Feb 2013: New 2-state 2-color relative-movement non-halting busy beaver: 18.22 million steps.
- 1st Feb 2013: Ed Pegg, Jr. asks: "What is the longest a machine can run before it becomes predictable? For Langton's Ant, it's around 10000 steps. For Worm Trails, it's 4 million. What 2-color, 2-state turmites are unresolved? Is there a list somewhere?" I've made a new section: Non-halting Busy Beavers
- 26th Aug 2011: Georgi Gochev reports a new record Busy Beaver for 5-state 2-color absolute-movement on a square grid, now up to 25 billion steps.
- 12th Jan 2011: Georgi Gochev reports a new record Busy Beaver for 5-state 2-color absolute-movement on a square grid, now up to 7.1 billion steps.
- 6th July 2010: Georgi Gochev reports a new record Busy Beaver for 5-state 2-color absolute-movement on a square grid, now up to 1.8 billion steps.
- 4th June 2010: Georgi Gochev reports a new record Busy Beaver for 5-state 2-color absolute-movement on a square grid.
Turing machines operate on an infinite tape, extending out to infinity in each direction. The tape is divided into cells, each of which can contain a symbol from a finite alphabet. The Turing machine consists of a finite state machine that moves along the tape, reading and writing symbols.
One way to generalise this simple definition is to alter the tape on which the Turing machine inhabits. Since there is only one possible one-dimensional tape, this involves moving into two dimensions. Natural choices for the grid are the square and hexagonal lattices; triangular and Penrose tilings are more exotic.
Another way to generalise the definition is to give the read-write head an orientation, so it moves either forwards or does a U-turn first. We're calling these machines relative, since their movement choices are relative to their current orientation. By contrast therefore the standard definition Turing machines are absolute.
The majority of this article is concerned with Turing machines on a square grid, both absolute and relative. Relative-movement 2D Turing machines are popularly known as Turmites.
Relative-movement Turing machines and 2D Turing machines have been investigated by many people over the years (both extensions are very obvious) but there are only a few papers:
- Hartmanis, J. and Stearns, R. E. (1965) "On the Computational Complexity of Algorithms" Transactions of the American Mathematical Society, 117: 285-306. Pascal Michel tells us that this paper discusses 2D Turing machines. I haven't seen a copy myself.
- Brady, Allen H. (1995) "The Busy Beaver Game and the Meaning of Life". In: Herken, R. "The Universal Turing Machine: a half-century survey". He considered "TurNing" machines (an independent invention of Turmites) and found 2-state 2-color machines that ran for 121 steps and printed 37 non-zero cells before halting. He did the same test on a triangular grid and found machines that took 171 steps and printed 39 non-zero cells before halting. He found a 3-state 2-color triangular grid machine that took 1721 steps and printed 351 non-zero cells before halting but the search was limited to 2,000 iterations.
- Wolfram, S. (2002) "A New Kind of Science" He has a section on 2D Turing machines.
Absolute movement
- Run Scripts/Python/Rule-Generators/AbsoluteTurmite-gen.py in Golly. Copy-paste one of the absolute-movement specification strings, e.g.:
{{{1,'E',1},{1,'W',1}},{{1,'W',0},{1,'',0}}} - Each machine is specified as a table of n_states rows by n_colors columns, written in (Western) reading order: the first row first, then then other rows.
- Each triple is {A,B,C} where A is the new color to write:
[0,1,2,...,(n_colors-1)], B is the direction to move in (North, South, East, West) or empty to halt, C is the new state to adopt:[0,1,2,...,(n_states-1)]. - For example, the triple
{1,'S',3}means: print a '1', move South, and adopt state 3.
Relative movement
- Run Scripts/Python/Rule-Generators/Turmite-gen.py in Golly and copy-paste one of the relative-movement specification strings below into the text box. E.g.
{{{1,2,0},{0,8,0}}} - It uses a similar notation as the other script. The difference is in how the direction is specified: 1=forward, 2=right, 4=u-turn, 8=left, 0=halt. (This notation allows turmites to split, e.g. 10=turn left and right.)
- For example, the triple
{1,2,3}means: print a '1', turn right (and move forward), and adopt state 3.
This is a list of the best known busy beavers. If you find improvements then overwrite the below.
- Going from absolute movement to relative movement improves the score. The only exception found is Sigma_relative(2,2)=4 which is the same as Sigma_absolute(2,2).
- Going from 1D to 2D seems to improve the score other than for low numbers of state or colors.
- No examples are known where going from 2D to 3D improves the score but this is likely to be true for higher numbers of states and colors for the same reason that the 2D case outperforms the 1D case.
Absolute movement
| 2-state | 3-state | 4-state | 5-state | |
|---|---|---|---|---|
| 2-color | 1D: 6 (4) 2D: 6 (4) 3D: 6 (4) 4D+?: 6 (4) |
1D: 21 (6) 2D: 32 (11) 3D: 32 (11) 4D+: ? |
1D: 107 (13) 2D: 4,632 (244) 3D+: ? |
1D: 47,176,870 (4,098) 2D: 25,772,988,638 (935,508,401) 3D+: ? |
| 3-color | 1D: 38 (9) 2D: 38 (10) 3D: 38 (10) 4D+: ? |
|||
| 4-color | 1D: 3,932,964 (2,050) 2D+: ? |
Relative movement
| 2-state | 3-state | 4-state | |
|---|---|---|---|
| 2-color | 1D: 13 (4) 2D: 121 (37) 3D: ? |
1D: 82 (9) 2D: 21,790 (2,793) 3D+: ? |
1D: 48,186 (96) 2D: 287,251 (19,875) 3D+: ? |
| 3-color | 1D: 233 (19) 2D: 59,348,218 (888,629) 3D+: ? |
||
| 4-color | 1D+: ? |
Detailed results and credits are listed below.
To find busy beavers you'll need a search program. Here's the one I was using to find some the results listed below: https://github.com/gollygang/terminatingturmites
For other programs, the wikipedia page on busy beavers will guide you.
- What acceleration techniques can we find in 2D and higher? Heiner Marxen's macro machines can't obviously be used but can maybe be adapted?
http://www.drb.insel.de/~heiner/BB/mabu90.html
http://www.drb.insel.de/~heiner/BB/macro.html
- So far no 3D or higher TM has been found that outperforms a 2D one with the same parameters. Do they exist or is 2D somehow special?
- Can we understand anything about how BBs work or are they 'black boxes'? Some 1D machines (Surprise in a box) appear to have counting components - is there a similar mechanism in 2D?
Absolute movement
| S (steps) | Sigma (non-zero cells left) | ||
|---|---|---|---|
| 1D | 6{{{1,'E',1},{1,'W',1}},{{1,'W',0},{1,'',1}}} |
4 (same one) |
|
| 2D+ | (no improvement) | (no improvement) | In 3D there's no improvement either. And thinking about it, it will be true in all higher dimensions too - there are only 3 moves to be specified so if the 2D case is no improvement over the 1D case then adding further dimensions won't help either. Busy Beavers need to go over their own tracks to really be effective - and from this perspective it's really a surprise that some of the 2D cases outperform the 1D cases. TJH March 2010 |
Relative movement
| S (steps) | Sigma (non-zero cells left) | ||
|---|---|---|---|
| 1D | 13{{{1,4,1},{1,0,0}},{{1,1,0},{0,1,1}}} |
4 (same one) |
Allen H. Brady (in unpublished work) called these systems "Flippers" and discovered this Busy Beaver. |
| 2D | 121{{{1,8,0},{0,8,1}},{{1,0,0},{1,2,0}}} |
37{{{1,2,1},{1,1,0}},{{1,4,0},{1,0,0}}} |
Allen H. Brady's results from the paper. |
| 3D+ | ? | ? |
Absolute movement
| S (steps) | Sigma (non-zero cells left) | ||
|---|---|---|---|
| 1D | 21{{{1,'E',1},{1,'',0}},{{1,'W',1},{0,'E',2}},{{1,'W',2},{1,'W',0}}}
|
6{{{1,'E',1},{1,'W',2}},{{1,'W',0},{1,'E',1}},{{1,'W',1},{1,'',0}}} |
|
| 2D | 32{{{1,'S',1},{1,'W',2}},{{0,'W',2},{0,'E',1}},{{1,'N',0},{1,'',1}}} |
11{{{1,'W',2},{1,'E',1}},{{1,'S',0},{1,'N',1}},{{1,'N',1},{1,'',1}}} |
If better machines exist then they take more than 10,000 steps or move more than 100 squares from the starting position. TJH March 2010. |
| 3D | (no improvement) | (no improvement) | If better machines exist then they take more than 1000 steps or move more than 50 squares from the starting position. TJH April 2010. |
| 4D+ | ? | ? | Unlikely to be any further improvement. |
Relative movement
| S (steps) | Sigma (non-zero cells left) | ||
|---|---|---|---|
| 1D | 82{{{1,1,1},{0,1,0}},{{1,4,0},{0,1,2}},{{1,1,0},{1,0,0}}} |
9 (same one) |
If better machines exist then they take more than 1,000 steps or move more than 50 squares from the starting position. Steps: TJH March 2010. Sigma: Allen H. Brady, unpublished. |
| 2D | 21,790{{{1,2,1},{1,1,0}},{{1,2,1},{1,2,2}},{{1,0,0},{1,1,0}}} |
2,793 (same one) |
If it is not the best, the best will take more than 100,000,000 steps or move more than 5,000 squares from the starting position. TJH March 2010. [bounds raised RF Feb 2018] |
| 3D | ? | ? |
Universal computation becomes possible for 1D Turing machines, as demonstrated by Alex Smith and Stephen Wolfram for {{{1,'E',1},{2,'W',0},{1,'W',0}},{{2,'W',0},{2,'E',1},{0,'E',0}}}
Absolute movement
| S (steps) | Sigma (non-zero cells left) | ||
|---|---|---|---|
| 1D | 38{{{1,'E',1},{2,'W',1},{1,'',0}},{{2,'W',0},{2,'E',1},{1,'W',1}}} |
9 (same one) |
|
| 2D | (no improvement) | 10{{{1,'N',1},{2,'W',1},{0,'E',0}},{{1,'S',0},{2,'N',1},{1,'',1}}} |
If better machines exist then they take more than 10,000 steps or move more than 100 squares from the starting position. TJH March 2010. |
| 3D | (no improvement) | (no improvement) | If better machines exist then they take more than 500 steps or move more than 20 squares from the starting position. TJH April 2010. |
| 4D+ | ? | ? | Further improvement thought unlikely. |
Relative movement
| S (steps) | Sigma (non-zero cells left) | ||
|---|---|---|---|
| 1D | 233{{{1,4,1},{0,1,0},{2,1,0}},{{2,1,0},{1,0,0},{1,1,0}}} |
19 (same one) |
If better machines exist then they take more than 10,000 steps or move more than 100 squares from the starting position. TJH March 2010. |
| 2D | 59348218{{{1,2,1},{2,4,1},{2,0,0}},{{1,2,0},{1,1,1},{1,4,1}}}
|
888629 (same one) |
If started facing 1,0, this one's range is x=-2510~3320 y=-305~201. If better machines exist then they take more than 100,000,000 steps or move more than 5000 squares from the starting position. RF Feb 2018. |
| 3D+ | ? | ? |
Absolute movement
| S (steps) | Sigma (non-zero cells left) | ||
|---|---|---|---|
| 1D | 107{{{1,'E',1},{1,'W',1}},{{1,'W',0},{0,'W',2}},{{1,'',0},{1,'W',3}},{{1,'E',3},{0,'E',0}}} |
13 (same one) |
|
| 2D | 4,632{{{1,'E',1},{0,'S',1}},{{1,'N',3},{1,'E',2}},{{0,'W',0},{1,'N',2}},{{1,'W',0},{0,'',0}}} |
244{{{1,'E',1},{0,'W',0}},{{1,'W',3},{1,'S',0}},{{1,'S',0},{1,'',0}},{{1,'W',2},{1,'N',3}}} |
If better machines exist then they take more than 100,000 steps or move more than 200 squares from the starting position. TJH March 2010. |
| 3D+ | ? | ? |
Relative movement
| S (steps) | Sigma (non-zero cells left) | ||
|---|---|---|---|
| 1D | 48,186{{{1,4,1},{1,1,0}},{{1,1,2},{0,1,0}},{{1,4,3},{0,1,3}},{{0,0,0},{1,4,0}}} |
96{{{1,4,1},{1,1,0}},{{1,1,2},{0,1,0}},{{1,1,0},{1,1,3}},{{1,0,0},{0,1,0}}} |
Allen H. Brady, unpublished. That's a pretty amazing leap from 107 steps, 13 cells! |
| 2D | 287,251{{{1,1,1},{0,4,3}},{{0,2,0},{0,1,2}},{{1,0,0},{0,4,1}},{{1,1,0},{0,1,0}}} |
19,875{{{1,1,1},{1,0,0}},{{0,8,2},{0,8,2}},{{0,2,3},{1,4,0}},{{0,4,0},{0,1,0}}} |
These are not expected to be the final results. |
| 3D+ | ? | ? |
Absolute movement
| S (steps) | Sigma (non-zero cells left) | |
|---|---|---|
| 1D | 3,932,964 | 2,050 |
| 2D+ | ? | ? |
Relative movement
| S (steps) | Sigma (non-zero cells left) | |
|---|---|---|
| 1D+ | ? | ? |
Absolute movement
| S (steps) | Sigma (non-zero cells left) | ||
|---|---|---|---|
| 1D | 47,176,870 | 4,098 | Marxen and Buntrock. |
| 2D | 25,772,988,638{{{1,'N',1},{1,'',0}},{{1,'S',2},{0,'W',3}},{{0,'E',4},{0,'E',3}},{{1,'W',0},{0,'W',1}},{{0,'N',0},{0,'N',1}}} |
935,508,401{{{1,'N',1},{1,'',0}},{{0,'E',2},{1,'W',3}},{{1,'S',4},{0,'W',3}},{{1,'N',2},{1,'S',3}},{{1,'W',3},{0,'E',0}}} |
Georgi Gochev , Aug 2011. |
For more states and colors, the Busy Beavers are enormous.
For example, here are two example 3,3 Turing machines, neither of which are record holders:
{{{1,'N',1},{2,'S',2},{2,'S',1}},{{1,'W',2},{1,'N',1},{1,'',0}},{{1,'E',0},{0,'N',0},{0,'N',0}}}
9304 steps.
{{{2,'W',1},{1,'',0},{2,'E',1}},{{2,'W',2},{0,'E',1},{2,'S',1}},{{1,'E',0},{0,'N',0},{0,'N',0}}}
697 non-zero cells written.
These are just examples - the actual record holders will have to be at least as large as the 1D case for which the record is large:
{{{1,'E',1},{2,'W',0},{1,'W',2}},{{0,'W',0},{2,'E',1},{1,'W',1}},{{1,'',0},{1,'E',0},{1,'E',2}}}
(119,112,334,170,342,540 steps, 374,676,383 non-zero cells written)
Here's the 3,3 1D machine described as Surprise-In-A-Box:
{{{1,'E',1},{2,'W',1},{1,'W',2}},{{1,'W',0},{2,'E',1},{1,'E',1}},{{0,'',0},{2,'W',0},{0,'W',2}}}
On a square grid we could also consider turmites that move to a cell within its Moore neighborhood rather than its von Neumann neighborhood. Relative-movement Moore turmites would turn through multiples of 45 degrees.
Note that hexagonal turmites (below) can be viewed as intermediate between von Neumann turmites and Moore turmites, the three cases having 4, 6 and 8 turns/moves to make, respectively.
We haven't investigated Moore turmites yet.
On a 2D grid of triangular cells, it doesn't make sense to talk about absolute-movement turmites because the triangles aren't all the same way up. Relative-movement turmites on a triangular grid were first studied by Allen H. Brady (ref at the top), and we've added some results of our own.
Each triple is {A,B,C} where A is the new color to write: [0,n_colors), B is the direction to turn: {0=halt, 1=left, 2=right, 4=u-turn}, C is the new state to adopt: [0,n_states). For example, the triple {1,2,3} means: print a '1', turn right, and adopt state 3.
| S (steps) | Sigma (non-zero cells left) | ||
|---|---|---|---|
| 2-state 2-color | 171{{{1,2,1},{1,0,0}},{{0,1,1},{1,4,0}}} |
39{{{1,2,0},{0,2,1}},{{1,0,0},{1,1,0}}} |
Allen H. Brady's results from the paper, confirmed. If better machines exist then they take more than 100,000 steps or move more than 1,000 squares from the starting position. |
| 3-state 2-color | 4,499{{{1,2,1},{0,1,1}},{{1,1,2},{1,2,0}},{{0,4,1},{1,0,0}}} |
1,611{{{1,2,1},{1,2,0}},{{1,1,1},{1,1,2}},{{1,0,0},{0,1,0}}} |
If better machines exist then they take more than 100,000 steps or move more than 200 squares from the starting position. TJH May 2010. |
| 2-state 3-color | 21,500,468{{{1,2,0},{2,2,1},{1,4,1}},{{0,2,0},{0,4,0},{2,0,1}}} |
44,594same one |
If better machines exist then they take more than 1,000,000,000 steps or move more than 18,000 squares from the starting position. RF Mar 2018. |
| + | ? | ? |
Golly 2.2 has a script TriTurmite-gen.py for generating CA for these turmites.
Absolute movement
Here there are 6 directions for the turmites to move in: 'A', 'B', 'C', 'D', 'E', 'F'. Golly 2.2 has a script AbsoluteHexTurmite-gen.py for generating CA for these turmites.
| S (steps) | Sigma (non-zero cells left) | ||
|---|---|---|---|
| 2-state 2-color | 6{{{1,'A',1},{1,'B',1}},{{1,'D',0},{1,'',0}}} |
4 (same one) |
If better machines exist then they take more than 100,000 steps or move more than 100 squares from the starting position. TJH May 2010. |
| 3-state 2-color | 33{{{1,'A',1},{1,'',0}},{{1,'E',2},{0,'A',2}},{{1,'C',1},{1,'D',0}}} |
13{{{1,'A',1},{1,'C',2}},{{1,'E',2},{1,'B',0}},{{1,'D',0},{1,'',0}}} |
If better machines exist then they take more than 100,000 steps or move more than 20 squares from the starting position. TJH May 2010. |
| 2-state 3-color | 38{{{1,'A',1},{2,'D',1},{1,'',0}},{{2,'D',0},{2,'A',1},{1,'D',1}}} |
14{{{1,'A',1},{2,'C',1},{1,'',0}},{{2,'D',0},{2,'B',0},{1,'E',0}}} |
If better machines exist then they take more than 100,000 steps or move more than 20 squares from the starting position. TJH May 2010. |
| 4-state 2-color | 1351(spec string lost) |
165{{{1,'A',1},{1,'',0}},{{1,'B',2},{0,'E',3}},{{1,'A',3},{1,'C',1}},{{1,'D',1},{1,'B',0}}} |
Preliminary results (9% explored) - not yet beating the square-grid case. TJH June 2010. |
| + | ? | ? |
Note that absolute-movement hexagonal-celled Turing machines can simulate any square grid machine, so their scores can never be lower. But their improvements (where there are any) are surprisingly small in the cases examined.
Relative movement
Extending our convention: 0=halt, 1=no turn, 2=left, 4=right, 8=back-left, 16=back-right, 32=u-turn. Golly 2.2 has a script HexTurmite-gen.py for generating CA for these turmites.
| S (steps) | Sigma (non-zero cells left) | ||
|---|---|---|---|
| 2-state 2-color | 54{{{1,16,1},{1,0,0}},{{1,16,0},{1,1,1}}} |
24 (same one) |
If better machines exist then they take more than 100,000 steps or move more than 50 squares from the starting position. TJH May 2010. |
| 3-state 2-color | 57,867{{{1,16,0},{1,8,1}},{{1,8,2},{1,16,0}},{{1,0,0},{0,1,0}}} |
1,654 (same one) |
If better machines exist then they take more than 500,000 steps or move more than 50 squares from the starting position. TJH May 2010. |
| 2-state 3-color | 59,823,304{{{1,1,1},{2,16,0},{2,0,0}},{{0,4,0},{0,4,0},{0,2,1}}} |
227,345{{{1,4,1},{1,0,0},{0,1,1}},{{2,4,1},{1,32,0},{0,8,1}}} |
If better machines exist then they take more than 1,000,000,000 steps or move more than 18,000 squares from the starting position. RF Mar 2018. |
| + | ? | ? |
The 2-state 2-color results (54, 24) are significantly smaller than the square-grid (121, 37) and triangular-grid (171, 39) results, which is perhaps surprising since there are more ways for the turmites to turn (6 as opposed to 4 or 3). But then again they can only make 3 turns so maybe it's like the 3D case (above) - they don't have enough moves to take advantage of the grid. But the 3-state 2-color steps result (S=57,867) is far ahead of the square-grid (S=21,790) and triangular-grid result (S=4,499).
Turmites on Penrose tilings are especially interesting. Due to the aperiodicity of the tiling, an infinite amount of information can be stored in the initial location of the Turmite. This means that it is possible to engineer a Universal Turmite, where the program is encoded entirely in its initial position, and not in the initial contents of the tape.
However, since the time to halt depends on the position of the Turmite, there is no analogue of the Busy Beaver problem; with a sufficient number of states, a Turmite could take arbitrarily long to halt.
Ed Pegg, Jr. extended the turmite idea by allowing turmites to turn both left and right, for example. When turmites collide they annihilate each other. Another form of the busy beaver game is therefore to find turmites that go extinct after writing the most non-zero cells or taking the most steps.
Relative movement, square grid
These turmites take advantage of the notation 1=forward, 4=u-turn, 2=right, 8=left, 0=halt. To turn in two or more directions, simply add the values together. E.g. 10=turn left and right.
| S (steps) | Sigma (non-zero cells left) | ||
|---|---|---|---|
| 1-state 2-color | 29{{{1, 4, 0}, {1, 5, 0}}} |
15 (same one) |
Discovered by Catsarefluffy One dimensional |
| 1-state 3-color | 307{{{1, 2, 0},{2, 4, 0},{1, 13, 0}}} |
432 (same one) |
Discovered by Catsarefluffy |
| 2-state 2-color | 122{{{1, 2 ,0}, {1, 10, 1}}, {{1, 6, 1}, {0, 12, 1}}} |
74 (same one) |
Discovered by Catsarefluffy |
| + | ? | ? |
Absolute movement, 1D, 3D+, triangular grid, hexagonal grid...
No-one has investigated extinction turmites on these cases, so there's lots left to be discovered.
(Asked by Ed Pegg, Jr.)
If we consider turmites without a halting state then there is still an interesting question:
- What turmite runs the longest before becoming predictable?
Results collected at EdPeggsBusyBeaverTurmiteChallenge. Let us know what you find.
As far as we know these are the current record holders:
1-state 2-color relative movement:
{{{1,2,0},{0,8,0}}}
Langton's Ant: 9,977 steps before making a highway.
2-state 2-color relative movement:
{{{1,2,1},{0,8,1}},{{1,8,1},{0,1,0}}}
8,362,028,000 (+1000) steps before making a highway. (Mark Jeronimus) This rule is a slightly modified version of a rule by Georgi Gochev.
3-state 2-color absolute movement:
{{{0,'S',1},{1,'W',1}},{{1,'E',2},{1,'S',2}},{{1,'W',0},{0,'N',0}}}
("Perfectionist": 15.5 million timesteps before making a highway)
Wolfram says this of 2D Turing machines:
"For Turing machines with two or three possible states, only repetitive and nested behavior normally seem to occur. With four states, more complex behavior is possible, but it is still rather rare." (NKS, p.184)
However there are examples of complex 3-state 2-color 2D Turing machines. These below were located by a program searching for patterns with high entropy:
This pattern is seemingly random for 15.5 million timesteps, before making a repetitive highway:
{{{0,'S',1},{1,'W',1}},{{1,'E',2},{1,'S',2}},{{1,'W',0},{0,'N',0}}}
(Patterns/Turmites/Perfectionist.rle in Golly)
This pattern expands at a logarithmic rate, and behaves quite unusually:
{{{0,'N',2},{1,'S',1}},{{0,'E',0},{0,'S',0}},{{1,'W',1},{1,'N',2}}}
This pattern grows extremely slowly, so is perhaps doing some form of counting, but appears random. Here's an animation of the states progressing from 1E9 timesteps up to 100E9 timesteps (100 frames, each 1 billion timesteps):
This resembles a form of binary counter. However, it is not performing traditional binary counting, as long strings of '1' symbols are replaced with alternating '1's and '0's, instead of solid '0's. If the counter didn't produce extra lines, and just worked in one dimension, it would count like so:
1
01
11
101
011
111
0101
1101
1011
0111
1111
10101
01101
11101
01011
11011
10111
01111
11111
010101
Notice that there is 1 one-digit number, 2 two-digit numbers, 3 three-digit numbers, 5 four-digit numbers and 8 five-digit numbers. These correspond to the Fibonacci numbers, which means that it effectively counts in base-phi, where phi is the golden number. This is quite unexpected, as phi is an irrational number, so doesn't usually occur as the base for discrete counting.
However, occasionally a parallel side-branch is created. This makes the counting process less regular, as the branches interfere with each other.
3-state 2-color 2D Turing machine from NKOS p184:
states: 0=north, 1=SE, 2=SW
colors: 0=white, 1=grey
{{{1,'E',2},{0,'E',1}},{{1,'W',0},{1,'N',1}},{{0,'S',1},{1,'N',0}}}
Five 4-state 2-color 2D Turing machines from NKOS p185:
states: 0=north, 1=east, 2=south, 3=west
colors: 0=white, 1=grey
(a): {{{1,'S',1},{0,'W',2}},{{1,'S',2},{1,'E',1}},{{1,'N',3},{0,'S',0}},{{0,'E',1},{0,'N',0}}}
(b): {{{1,'E',3},{0,'N',0}},{{1,'W',2},{1,'S',1}},{{0,'N',0},{1,'S',1}},{{1,'E',1},{0,'S',0}}}
(c): {{{1,'W',1},{0,'E',2}},{{0,'E',3},{1,'W',0}},{{0,'N',0},{0,'S',3}},{{1,'S',0},{1,'N',1}}}
(d): {{{0,'E',3},{0,'W',1}},{{1,'N',0},{1,'N',3}},{{0,'W',1},{1,'S',2}},{{1,'S',2},{0,'E',1}}}
(e): {{{1,'N',1},{0,'S',1}},{{1,'S',3},{0,'N',2}},{{1,'W',0},{1,'N',1}},{{1,'S',2},{0,'E',1}}}
Wolfram devotes a page to example (e)
and describes it as: "one example where the behavior seems in many respects completely random." In fact, as I reported here the pattern is periodic, with period 2,074,575 and dx=3953, dy=1912.
3-state 2-color 2D Turing machine from NKOS Notes, p931:
states: 0=north, 1=SE, 2=SW
colors: 0=white, 1=grey
{{{1,'N',2},{1,'W',0}},{{0,'W',0},{1,'S',0}},{{1,'S',1},{0,'E',1}}}
| Machine | S (steps) | Sigma (non-zero cells left) |
|---|---|---|
{{{1,'N',1},{1,'',0}},{{1,'E',2},{1,'E',3}},{{1,'W',3},{0,'S',4}},{{0,'W',4},{1,'S',3}},{{1,'E',0},{0,'W',4}}} |
12,135,580,977 | 319,966 |
{{{1,'N',1},{1,'',1}},{{0,'E',2},{1,'W',3}},{{1,'S',4},{0,'W',3}},{{1,'N',2},{1,'S',3}},{{1,'W',3},{0,'E',0}}} |
7,131,195,542 | 935,508,401 |
{{{1,'N',1},{1,'',1}},{{1,'E',2},{1,'N',1}},{{1,'W',3},{0,'E',1}},{{1,'S',0},{1,'S',4}},{{1,'W',2},{0,'E',1}}} |
1,894,226,289 | 581,857,738 |
{{{1,'N',1},{1,'N',4}},{{1,'S',2},{1,'',1}},{{1,'S',4},{1,'S',3}},{{0,'E',2},{0,'W',0}},{{1,'N',0},{0,'S',2}}} |
1,635,991,442 | 166,125,459 |
{{{1,'N',1},{1,'',1}},{{1,'S',2},{0,'W',3}},{{1,'W',4},{0,'E',3}},{{1,'S',2},{1,'N',3}},{{1,'N',0},{0,'S',3}}} |
1,547,228,624 | 341,883,343 |
{{{1,'N',1},{1,'E',3}},{{1,'E',2},{1,'',1}},{{1,'W',3},{1,'N',3}},{{0,'S',0},{0,'W',4}},{{0,'S',3},{0,'N',1}}} |
1,366,930,758 | 855,482 |
{{{1,'N',1},{1,'',1}},{{1,'E',2},{1,'W',1}},{{0,'N',3},{1,'W',4}},{{1,'W',1},{0,'N',4}},{{1,'N',0},{0,'S',1}}} |
1,187,246,809 | 668,652 |
{{{1,'N',1},{1,'',1}},{{1,'S',2},{1,'W',1}},{{1,'N',3},{0,'S',1}},{{0,'N',0},{1,'E',4}},{{1,'N',2},{0,'S',1}}} |
1,047,936,297 | 314,986,440 |
{{{1,'N',1},{1,'',0}},{{0,'S',2},{0,'E',4}},{{0,'W',3},{1,'E',1}},{{1,'W',0},{1,'W',3}},{{0,'W',0},{0,'E',2}}} |
1,918,870 | 66 |