Busy Beaver Turmite Challenge

[Tim Hutton]

Ed Pegg, Jr., who runs http://www.mathpuzzle.com, has a challenge for us.

Turmites are little creatures that run around the grid. Langton's Ant is a simple turmite.
http://en.wikipedia.org/wiki/Turmite
http://en.wikipedia.org/wiki/Langtons_ant

Golly can run turmites. Use Scripts/Python/Rule-Generators/Turmite-gen.py. By default the script makes a random 2-state 2-color turmite, so just re-run it to see a new turmite.
http://golly.sourceforge.net/

Some turmites include a halting state. If they reach it then they will stop forever. The "Busy Beaver" game asks what machine runs the longest before halting.
http://en.wikipedia.org/wiki/Busy_beaver
Some Busy Beaver results for turmites can be found here:
http://code.google.com/p/ruletablerepos ... ngMachines

Other turmites don't include a halting state and so run forever. But often they end up in repeating predictable behaviour. This is another kind of Busy Beaver game. For example, Langton's Ant makes a highway after 10000 steps. The turmite called "Worm Trails" (shown below) ends up getting trapped in a loop after 4.3 million steps:
http://code.google.com/p/ruletablerepos ... sy_Beavers
Others seem to run forever, always random.

Ed asks us: What 2-state 2-color turmite runs the longest before becoming predictable? The current champion is Worm Trails, we think.

He defines 'predictable' to be: Traps, Highways, Spirals, Wedges and Sequences (like the counter), as shown here:
http://www.maa.org/editorial/mathgames/ ... 07_04.html
The turmite should start from an empty grid.

Send results to tim.hutton@gmail.com. I'll keep track of the current winner here:
http://code.google.com/p/ruletablerepos ... sy_Beavers

Prize: If you find a new champion, you might get a mention on http://www.mathpuzzle.com.

Good luck!

Tim

[Tim Hutton]

Update:

We've found a new record holder. The turmite {{{1,4,1},{1,1,0}},{{1,1,0},{0,2,1}}} runs for 18.22 million steps before making a highway:

[Tim Hutton]

Georgi Gochev is the current champion, with this amazing turmite that lasts 240 million steps:



{{{1,1,1},{0,8,1}},{{1,8,1},{0,1,0}}}

[Tim Hutton]

Georgi Gochev does it again! He has found a turmite that lasts 7.735 billion time steps before becoming predictable:

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

[Johnicholas]

Are there probability distributions over turmites (or functions from sizes to probability distributions over turmites of that size) which generally have large mean / median halting times?

Given a nice probability distribution, you can generate a lot of examples, test them, and the quality of the best one will have something to do with the number of examples you generated. But the thing that would be helpful to share would be the nice distribution, not the best example found.

[knightlife]

I randomly found Turmite_121080010111 that lasts at least 2 billion tics.
That is,

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

[Tim Hutton]

Mark Jeronimus and Ed Pegg, Jr. and Georgi Gochev are doing a great job of keeping the wiki updated with the latest results:

http://code.google.com/p/ruletablerepos ... eChallenge
http://code.google.com/p/ruletablerepos ... tes2Colors
http://code.google.com/p/ruletablerepos ... tes5Colors

The current champion for a 2-state 2-color turmite is over 3.5 trillion time steps.

Johnicholas: I could be wrong but I don't think there will ever be any useful way to model the behavior of turmites with a probability distribution - their behavior at each moment is contingent on the past behavior in a very random way. Changing a single value in the turmite specification usually gives a completely different behavior.

[MarkJ]

You're right about not being able to predict the behavior.

As an example, take a random turmite that is fairly chaotic in the first few million steps. You should be able to 'construct' a seed pattern that, when entered by the turmite at a certain cell, causes it to grow a highway. Now it's just sit and wait for the turmite to simulate trillions of steps until it creates this seed pattern on its own and enters it on its own.

Edit: Analogy; It's like taking any random transcendental number, like Pi, and looking at which decimal position a certain string, eg. "159267890" occurs. This could be (on average) around decimal 100,000,000, or it could actually be around decimal 7,500,000,000,000,000 or at decimal 3. You won't know unless you search them all. It's the same with iterations in turmites.

This means a few things:

• The same can be said about seed patterns for getting stuck.
• Turmites that grow highways encounter such a seed pattern they created in their own past. This doesn't exclude the possibility that multiple seed patterns exist, which would actually be very likely. (probably more likely for turmites that become predictable early on)
• By changing the initial state of the turmite (instead starting in an empty universe) a busy beaver can be (trivially) made to grow a highway or be otherwise predictable at the start.
• Turmites that are predictable from the very start (like a runaway turmite that only writes black and goes forward when it encounters black) could do other things when it encounters other colors. They could be very well a very busy beaver.

The current 2 state 2 color winner, found 10 days ago, is a turmite of at least 9,533,133,147,000 iterations, found by me after trying about 85 of the remaining unresolved turmites. There are hundreds of more candidates which I haven't run past 10 billion yet. Those can be found on the respective wiki page (just updated).

Sorry for the late response. in fact I just found this thread at random, after not coming here for two years.

[Tropylium]

Turmites that are predictable from the very start (like a runaway turmite that only writes black and goes forward when it encounters black) could do other things when it encounters other colors. They could be very well a very busy beaver.

This is a particularly intersting thought, and makes me wonder why we're only concerned with turmites starting from an empty universe?

I also wonder how many (if any) of even "trivially stabilizing" turmites could be able to still carve out a regular path, if dropped in the middle of an extended chaotic starting pattern? BRB, running a quick test.

[Tropylium]

OK, a small sampling of 36 stabilizing turmites and dropping them in chaos turns out the following results:

Oscillators
— 4 immediately stabilize with the same end result, one of them allowing for a small variation though.
— 9 erase some room until they stabilize. At least 3 could end up in stabilizations of an alternate period (eg. p16 rather than p4, or p4 rather than p12).
— 1 builds cells until stabilizing.
— 4 run chaotically for a while, then stabilize. All turmites with periods > 16 fell here. One could stabilize with an alternate period (p20 from vacuum, occasionaly p36 in chaos)
— 3 stabilize as oscillators of some arbitrary period, two creating loops, one creating "2×N chaos". The latter stabilizes almost instantly, one of the former can wanders for a while before stabilizing, the other erases space until it can "comfortably" orbit the edges of this hole.
— 2 wander chaotically without stabilizing

Highways and spaceships
— 1 (double highway) quickly stabilizes as loop oscillators of some arbitrary period
— 1 (spaceship) either stabilizes a p4, or makes a "chaotic spaceship", proceeding linearly at a variable speed
— 1 (spaceship) erases a double highway
— 1 chaotically erases cells
— 5 (w/ 1 double highway) wander chaotically

Other
— 2 linear spiral spacefillers: build cells until stabilizing as oscillators
— 1 return-to-origin 4× double-headed wedge builder: wanders chaotically
— 1 double binary counter: wanders chaotically

The chaotic double highway and the double binary counter, given only small perturbations, could both additionally stabilize as a 4-way highway/bincounter.

[MarkJ]

Funny that you did this, because I too am experimenting with dropping them in chaos as opposed to changing the initial state manually. This is however part of my search for a high quality random number generators, which would qualify for it's own thread. Of the 15 unique remaining rules, ironically about half are early highway builders (at most 1e3). Of course it may have something to do with that I use a toroidal space, so in the one in a million odds that it were ever to 'accidentally' make a highway (causing a run of non-random), it would soon run into debris, becoming chaotic again. (the world is 16x16 cells)