Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

When looking at 2D Turing machines, many of them eventually become predictable. For example, Langton's Ant, the champion 2-color 1-state turmite, develops a highway after 10,000 steps. Predictable behavior includes Traps (as in Worm Trails), Highways, Spirals, Wedges and Sequences (like the binary counter). Examples at 2D Turing Machines, within Golly, and at wikipedia's Turmite entry.

For 2-color, 2-state Turmites, {{{1,1,1},{0,8,1}},{{1,8,1},{0,1,0}}} found by Georgi Gochev runs for 240 million steps before becoming predictable.

{{{1,1,1},{0,8,1}},{{1,8,1},{0,1,0}}} found by Georgi Gochev

EDIT: Beating that is {{{1,8,1},{0,2,0}},{{1,8,0},{0,1,0}}}, with 7.735 billion timesteps before making a wedge: (Georgi Gochev)

EDIT: Beating that is {{{0,1,1},{0,4,0}},{{1,4,0},{1,2,1}}}, with 9.533 trillion timesteps before making a highway (found by Mark Jeronimus).

Is that the longest unpredictable run for a 2-color, 2-state termite?

Non-halting Busy Beaver is a repository for known results.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.