This is part of live presentation series called Mathematical Games in which we explore a variety of games and puzzles using Wolfram Language. In this episode, we explore the mathematical games and puzzles involving Turing machines and turmites.

Can Machines Think? (Martin Gardner, 8th Book)

demonstrations.wolfram.com

Many Demonstrations involve Turing machines.

Paterson Worms

Worms eat sediment, delineating some sort of path. The 21 November 1969 issue of Science had computer simulations of worms, side by side with images of actual worm trail fossils. The ancient slimetrails enthralled John Conway and Mike Paterson. Mike started drawing algorithmic doodles for worms eating from an isometric grid (sometimes during lectures). His simple rules led to simple patterns for some worms, but many other doodles wound up being decidedly non-simple.
Mike Beeler, who worked in the MIT Artificial Intelligence Laboratory, became interested in “Paterson’s Worms”, and came up with a method of rendering their patterns on the cutting-edge green CRTs of the era. In 1973, Martin Gardner wrote a column: “Fantastic patterns traced by programmed worms.” Inspired by this, Sven Kahrkling developed a web page about isometric worms.
Worm {1,0,4,0,1,5}, pictured below, starts life on a triangular grid, with food on every gridline. It munches the lines, and chooses where to go based on the lines of food remaining. On the 57th step, it wanders into a node where no food lines are left, and dies of starvation. Note the bold numbers and blue lines -- 1 0 4 0 1 5.
As a different approach, consider the 28 step life of Worm {1,0,5,1}. Black is the first “new” configuration. The configuration with five foodpaths happens many times, and direction {1} is always chosen. The next new configuration is Red, where direction {0} is chosen. In the Green configuration, which will be encountered a few more times, direction {5} is always chosen. In the Magenta configuration, which only occurs once, direction {1} is taken. In the Blue configuration, there is no choice. The worm rule {1,0,5,1} represents the direction chosen for a given configuration, in the order in which those configurations appear.
In[]:=
Row[{DrawWormPath[{1,0,4,0,1,5}],DrawWormPath[{1,0,4,0,1,0,1}],DrawWormPath[{1,0,4,0,1,0,2}],DrawWormPath[{1,0,4,0,1,0,5}]}]
Out[]=
Some worms become predictable:
For Martin Gardner, the fates of 11 worms remained unknown: {1,0,4,2,0,1,5}, {1,0,4,2,0,2}, {1,2,5,2,1,2,1}, {1,4,2,0,2,2,1}, {1,4,2,0,2,2,4}, {1,4,5,0,2,2,4}, {1,4,5,0,2,2,1}, {1,5,2,5,1,1,5}, {2,0,1,4,1,4,2}, {2,1,4,5,1,4,2}, {2,4,5,4,1,4,2}.

More Worms

In October 2003, Benjamin Chaffin solved most of them.
Worms {2,1,4,5,1,4,2}, {2,0,1,4,1,4,2}, and {1,4,2,0,2,2,4}.
In 2004, Tomas Rokicki solved things further.
Pattern 1042020 terminates at step 57,493,855,205,939.
Pattern 1042022 terminates at step 57,493,855,205,905.
Pattern 1042015 doesn’t terminate after 1.3E18 steps.

The Busy Beaver Problem (Stephen Wolfram, NKS)

Different Representations of a Turing Machine

Import a standard Turing machine format specified as a string:
Return a Turing machine number:
Return the raw table of string:
Return a formatted raw table of states and symbols:
Show the Turing Machine, the state of the head and the ongoing tape.

Turing Machine L R, Color, State

A 2-state, 2-color machine:
The states are A/B or up/down. The colors are 0/1 or white/orange:
A 3-state, 3-color machine:
A table of the three colors and three states:

A Turing Machine and the Compressed Form

A Turing Machine
Compressed form showing only when a new section of the tape is reached.

2,2 Turing Machines

by: Stephen Wolfram
Explore the behavior of the simplest nontrivial class of Turing machines—the 4096 possible machines with 2 states and 2 colors.

Small Busy Beavers

Show evolutions of small Busy Beaver Turing machines up-to their record halting time:

Busy Beaver (2011)

by: Hector Zenil

Busy Beaver 2-state, 4 color

According to https://wiki.bbchallenge.org/wiki/Main_Page BB(2,4) = 3932964

Busy Beaver 2-state, 5-color

As of June 15th 2024, there are 273 unresolved 2-state, 5-color Turing machines.

Busy Beaver 5-state, 2-color “Inverted Counter”

Busy Beaver 5 “Helix”

Busy Beaver 5 “Pointy Wide”

Busy Beaver 5 “Chaotic”

Busy Beaver 5 “Complex Counter”

Busy Beaver 5 “#7,410,754”

Busy Beaver 5 “#36,909,813”

Busy Beaver 5 “#68,329,601”

As of 2021, there were 21 undecided machines, including this one. These were pruned down from a longer list, the 43 Skelet undecided machines.

https://bbchallenge.org/story

Launched by Tristan Stérin.
Maintained by Justin Blanchard (UncombedCoconut), Pavel Kropitz (uni), Shawn Ligocki, mei.
Major contributors: atticuscull, Konrad Deka, Frans Faase, Nathan Fenner, Tony Guilfoyle, Matthew House, Nick Howell, Iijil, Alexandre Jouandin, Dawid Loranc, Heiner Marxen, modderme123, mxdys, Mateusz Naściszewski (Mateon1), Sébastien Ohleyer, savask, star, tomtom2357, Valentin, racheline, Chris Xu, Daniel Yuan, Jason Yuen

Busy Beaver 5

The 5-state busy beaver produces 4098 1s, using 47,176,870 steps. It was discovered by Heiner Marxen and Jürgen Buntrock in 1989.
Proven maximal in 2024.
May 10, 2024. mxdys: “The Coq proof of BB(5) is finished.”

BB(3,3) record: 119112334170342541 steps Terry and Shawn Ligocki in 2007

BB(3,3) Holdouts

There are currently 22 unresolved (3,3)-Turing machines.
1RB---0LC_2LC2RC1LB_0RA2RB0LB
1RB---1RB_2LC2RC1LB_0RA2RB0LB
1RB0LB0RC_2LC2LA1RA_1RA1LC---
1RB0RC---_2RC0LB1LB_2LC2RA2RB
1RB1LB2LC_1LA2RB1RB_---0LA2LA
1RB1LC---_0LC2RB1LB_2LA0RC1RC
1RB1LC1LC_1LA2RB0RB_2LB---0LA
1RB2LA0LA_2LC---2RA_0RA2RC1LC
1RB2LA1LA_2LA0RA2RC_---0LC2RA
1RB2LA1LA_2LA0RA2RC_---1RB2RA
1RB2LA1LC_1LA2RB1RB_---2LB0LC
1RB2LA2RA_1LC1LB0RA_2RA0LB---
1RB2LB---_1RC2RB1LC_0LA0RB1LB
1RB2LB0LC_2LA2RA1RB_---2LA1LC
1RB2LC---_0LA0RC1LC_1RB2RC1LB
1RB2LC1RC_2LC---2RB_2LA0LB0RA
1RB2RA1LB_0LC0RA1LA_---2LA---
1RB2RA1LB_0LC0RA1LA_---2RB2LA
1RB2RA1LB_0LC0RA1LA_2LA0RB---
1RB2RA1LC_2LC1RB2RB_---2LA1LA
1RB2RB---_1LC2LB1RC_0RA0LB1RB
1RB2RB1LC_1LA2RB0RB_2LB---0LA
Some pictures of these cases.

BB(6) Kropitz 10↑↑15-halter

This machine halts in 10↑↑15 steps, a very large number.

BB(6) Antihydra [mxdys, Racheline, 2024]

It simulates the Collatz-like iteration
It may not be currently solvable whether this halts.

Turmites (2D Turing Machines)

A turmite is a set of rules for moving a cell on a grid. Turmites are also called turning machines or 2D Turing machines. The simplest turmite, known as Langton’s ant, starts on an infinite grid of white squares. Each time the ant moves off a square, the color changes (white to black or vice versa). Whenever the ant lands on a black square, it turns right. Whenever the ant lands on a white square, it turns left. This simple rule and its generalizations lead to amazing patterns.
The Binary Counter
Langton’s Ant

Turmite Predictability

Some turmites make highways:
There are many types of highway:
Many make spiral patterns
Others have more chaotic behavior:

Ed Pegg Jr’s Busy Beaver Turmite Challenge

https://github.com/GollyGang/ruletablerepository/wiki/EdPeggsBusyBeaverTurmiteChallenge

Resolved 1-state 3-color turmites

{{{1,2,0}, {2,1,0}, {0,4,0}}} Highway at 67,620,060 +10 by Hutton/Pegg

Unresolved 1-state 3-color turmites

There are currently 9 unresolved 1-state 3-color turmites. The image below shows the state of the first eight rules after 20 million steps.
All are chaotic after 10 billion steps.
The last turmite can make a binary highway.
Binary counting highways at 2,717,308,080 +10 and at ~10 trillion steps but expected to be unpredictable again after that -- Tim Hutton
It’s expected that this one will eventually become predictable.

Resolved 1-state 4-color turmites

{{{1,4,0}, {2,2,0}, {3,8,0}, {0,8,0}}} Highway at 6,650,200,000 by Georgi Gochev
{{{1,2,0}, {2,4,0}, {3,2,0}, {3,1,0}}} Dual Highway at 4,391,220,000 +10000 by Dean Hickerson

Unresolved 1-state 4-color turmites

There are 91 unresolved 1-state 4-color turmites
Submarine Turmite {{{1,2,0}, {2,1,0}, {3,4,0}, {1,1,0}}}

Unresolved 1-state 4-color turmites

{{{1,2,0}, {2,8,0}, {3,8,0}, {0,2,0}}}

Unresolved 1-state 4-color turmites

{{{1,4,0}, {2,1,0}, {3,1,0}, {2,2,0}}} Binary counting, makes width-4 extrusions out of the main hull;
see bottom at gens 41633 to 42084. -- Dean Hickerson
First big counter: ? - 803.43 billion.
Second big counter: 1.3~1.4 trillion - 1.600 trillion.
Third big counter: ~1.75 trillion - ~1.763 trillion.
Fourth big counter: ~1.78 trillion - (expected) 7*1033.

Unresolved 1-state 4-color turmites

{{{1,4,0}, {2,1,0}, {3,2,0}, {1,2,0}}} This rule loves ternary counters inside it’s hull.
First counter: from ~2,871,000 to ~1,868,000,000.
Second counter: from 1,870,924,000 to (projected) 14.6 trillion.

Resolved 2-state 2-color Turmites

{{{0,1,1}, {0,4,0}}, {{1,4,0}, {1,2,1}}} Highway at 9,533,133,147,000 +2,000 by Mark Jeronimus

Unresolved 2-state 2-color Turmites

{{{0,4,1}, {0,4,1}}, {{1,2,1}, {0,2,0}}} Still chaotic at 41,759,302,342.
Maze-like and fractal-like structures.
The maze corridors are actually highways allowing the turmite to travel vast distances surprisingly fast for a turmite with no “straight forward/no turn” rule.

Turmites: Binary Counter Chaos

With a different initial condition, the binary counter goes into chaos. Does this ever resolve?
For the current unresolved turmites, are there initial conditions that become predictable quickly?
Robust turmites behave in similar ways for any initial condition.
Fragile turmites can be broken to show different behaviors.

Unsolved Questions

CITE THIS NOTEBOOK

Mathematical Games: Turing machines​
by Ed Pegg​
Wolfram Community, STAFF PICKS, July 19, 2024
​https://community.wolfram.com/groups/-/m/t/3227158