(9 November 2007) As part of an announcement involving several machines over a wide range of Busy Beaver Turing machine domains, Terry and Shawn Ligocki announced their discovery of the newest champion for 3x3 (three state and three symbol) machines which takes more than 119 quadrillion (119 x 10 to the 15th power) steps before halting. Coming only 15 months later this increases the known results for the "shift number" (number of steps) by almost two orders of magnitude over their previous champion.

(20 August 2006) The father son team of Terry Ligocki and Shawn Ligocki has now produced an astounding machine which demonstrates the "shift number" function value for S(3,3) is over four quadrillion steps! It took my crude computer attack using Emacs Lisp an hour and twenty minutes on a Linux-based 2.5 ghz Pentium machine to produce the output shown here. (A step-by-step simulation completed on any existing computer before the end of the year would would not be achievable.) The Ligockis have honed their acceleration techniques, and right on the heels of discovering some new 2x5 (two state by five symbol) champions, they turned their attention to the 3x3 problem. In addition to this 3x3 champion they hold the championship for both 2x4 and 2x5 machines!

(4 April 2006) Lafitte and Papazian have now found yet another machine which pushes the "shift number" function value S(3,3) to over four trillion steps. While I do show the machine description below, I am presently without the practical capability to simulate it in order to display its final output. I cannot thus guarantee that the description shown using my internal notation is free from transcription error. Terry Ligocki's confirming simulation required 21 hours of computer time. (On my home computer --a 733 mhz G4 Mac-- I estimate nearly six days of running time for a step-by-step simulation. What can you do?)

(9 September 2005) The Lafitte-Papazian search has found another machine yielding a two order of magnitude jump in the known maximum number of steps to completion for 3x3 machines starting on an all blank tape. A description of their stunning discovery has been added to the list below.

(PREVIOUSLY) Gregory Lafitte of the University of Aix-Marseille I (Provence) and Christophe Papazian of the University of Nice-Sophia Antipolis, Nice, France have carried out a (3,3) search which has uncovered two machines that exceed a billion (1,000,000,000) steps before halting. These two machines were confirmed by Heiner Marxen on 9 August 2005. No other details are available for inclusion here at this time.

15 August 2005. The ongoing Lafitte-Papazian search has uncovered a better "runner up" shown as #3 below. In all they "have found at this time 8 machines ending after a number of steps higher than 100,000,000." How this jibes with the Souris discoveries (below) is not yet clear. Their search, which is using as many as 16 computers, is not yet complete.

Myron Souris, a computer science graduate of Washington University of St. Louis and an avid computer recreation enthusiast (who also works as a professional programmer), carried out an intensive search of the 3x3 space circa 1995 and discovered that S(3,3)>=544,884,219. The programs used his own technique (not a tree) for eliminating isomorphisms, mathematically eliminated many machines as not halting, and used "meta-machines" for speeding up the simulation of the individual Turing machines by a factor of 8 to 20 or more. The search ran for many months in the background on an HP 9000 computer. His programs ran all of the machines not already eliminated for one billion (1,000,000,000) steps. Souris also chose 100 or so machines deemed especially interesting which were then run for 100 billion steps. Sadly, for those of us who might have been interested in his results, the only people Souris contacted disdained any interest, and apparently no one he contacted even suggested that he announce his discoveries to an appropriate special interest group for the benefit of anyone else. Thus, we learned about his impressive finds only recently when he communicated his results simultaneously to me, Heiner Marxen, and Pascal Michel on 18 July 2005. So, my own seven month reign as "Champion" of the 3x3 search was illusory even though it was a much longer reign than I ever expected under the circumstances. Alas, however, for all of his considerable work ten years ago Myron Souris' reign as the 3x3 Champion has lasted since his July 18th announcement for only three weeks!

The first of the three machines is, of course, the machine with the largest shift number (steps until halting). The third machine has the largest "score", while the second machine has a more complex output than the others. These three machines are the only ones Souris found that operate beyond 100 million steps. The other machines he found below these three apparently coincide with mine.

These two machines may have little in common. The 47+ million step machine was missed in the 50 million step limit sweep because its output ranges beyond the tape limit of 20 thousand that was imposed for the earlier sweep. The 100 million limit sweep was carried out with a tape limit of 30 thousand.

This is the alleged "Champion" machine in the original announcement of 14 November 2004. Its reign (within my search) was a brief three weeks, and as fate would have it, the reign was only accidental. A larger tape size (30 thousand squares instead of 20 thousand squares) accompanying the 50 million step limit which was used to discover it would have revealed a different champion with a much more impressive 47,287,015 shift number and a score of 12,290!

FIVE MACHINES WITH SHIFT NUMBERS ABOVE 8,000,000--
Three of these machines were clustered together, the fourth was nearby, while the fifth appeared in a branch of the tree far away. They have been extracted from the saved 70 pages of raw program output that was later combined manually and visually scanned. They were found on or before 7 November 2004 in a previously completed run of all 3x3 machines under a 10 million step limit on a 10,000 square tape.

Following are some other Busy Beaver websites that might be of interest. The website of Heiner Marxen has some of these (3,3) machines set up to be simulated on-line. The website of Michiel Wijers has an extensive bibliography (PDF format) and links to a number of other interesting "Busy Beaver" websites. The website of Pascal Michel is one of the nicest websites I have seen about Turing machines with some very well-written tutorials. He has recently completed a paper about the Busy Beaver problem which relates the behavior of some of these (3,3) machines in particular to what he describes as "Collatz-like behavior" (paper in PDF format). It should be of interest to people who like to analyze the operation of "long-running" machines.