• LATEST RESULTS IN A SEARCH FOR LARGE VALUES UNDER BB(3,3) and S(3,3)

• ## Ligockis Have Now Determined S(3,3) Greater Than 119 Quadrillion!

• Among a flurry of new Busy Beaver discoveries announced by Terry and Shawn Ligocki on 9 November 2007 was their new discovery that S(3,3) is now known to be greater than 119 quadrillion (119 x 10^15 or 119 times 10 to the 15th power). To be exact, their new 3x3 (3 states by 3 symbols) Turing machine, starting on an all blank tape, takes 119,112,334,170,342,540 steps ("shifts") before it finally comes to a halt, having recorded 374,676,383 non zeros ("marks") on its tape. Their other new discoveries range over the machine domains 2x5, 2x6, 6x2, 3x4 and 4x3, the latter two domains being relatively unexplored until their recent efforts. The results for the new 3x3 machine are shown here. All of the Ligockis' new results are posted on Heiner Marxen's web site. (See Other Web Sites on this page.) Marxen has also confirmed their new results. A description of the Ligockis' latest "champion" machine and its final output have been incorporated into the list of 3x3 machines shown here (below).

• -- AHB 15 November 2007

• ## Ligocki Team Discovers S(3,3) Greater Than Four Quadrillion!

• On 20 August 2006, the father-son team of Terry and Shawn Ligocki announced their latest discovery which is a 3x3 (three state by three symbol) machine that pushes the S(3,3) lower bound up by three orders of magnitude over the previous discovery (April 4, 2006) by Lafitte and Papazian. Whether you call it "impressive", "stunning" or "astounding", we have run out of appropriate descriptive adjectives. S(3,3) now exceeds four quadrillion (four times 10 to the 15th power)! Starting on a blank tape (zeros) the new machine takes 4,345,166,620,336,565 steps and leaves 95,924,079 non-zeros on its output tape. A description of their machine is shown in the list of 3x3 machines (below.)

• -- AHB 23 August 2006

• ## Lafitte-Papazian Announce S(3,3) Now Exceeds Four Trillion!

• On 4 April 2006, Gregory Lafitte and Christophe Papazian announced the discovery of a 3x3 (three state by three symbol) machine that demonstrates that S(3,3) now exceeds four trillion. The new machine takes 4,144,465,135,614 steps to halt, writing 2,950,149 non-zeros on its (initially blank) input tape. The result was confirmed on 5 April by Terry Ligocki requiring 21 hours for a step-by-step simulation! A description of the machine has been added to the 3x3 collection on this page below.

• -- AHB 10 April 2006

• ## Lafitte-Papazian Team Discovers S(3,3) Approaches a Trillion Steps!

• In a stunning addition to known results in the Busy Beaver Game, Gregory Lafitte and Christophe Papazian have just announced discovery of a 3x3 (three state by three symbol) machine which brings the lower bound of S(3,3) up to 987,522,842,126 steps. The machine description (shown in the 3x3 collection below) was received on 9 September 2005 and the results were confirmed by Heiner Marxen on 10 September. Since their earlier S(3,3) discovery in August, Laffite and Papazian have also produced a new 2x5 (two state by five symbol) machine showing that S(2,5)>=7,543,673,517 (with a "score" of= 97,104), showing a nearly three orders of magnitude jump over the Ligockis' value for S(2,4) discovered earlier this year. (See below.)

• -- AHB 11 September 2005

• ## Old Discovery Recently Revealed--Immediately Superseded by New Discovery in France!

• Myron Souris recently made known (email received 18 July 2005) that a lengthy study of the 3x3 (three states by three symbols) Busy Beaver problem he carried out ten years ago had led to the discovery of three machines scoring higher than the machines found in my search last autumn which ended in Dec. 2004. Thus, Souris had already determined that S(3,3)>=544,884,219, but unfortunately no one he contacted had expressed interest or even encouraged him to publish this information. In the meantime two French academics, Gregory Lafitte and Christophe Papazian, have just announced their new discovery that S(3,3)>=4,939,345,068 (confirmed by Heiner Marxen 9 August 2005). I have added the high scoring Souris machines and the Lafitte-Papazian machines to the list below. So, my illusory reign as BB(3,3) Champion came to an end in July, while, alas, the Myron Souris reign as BB(3,3) Champion lasted only three weeks as a result of his somewhat delayed communication.

• -- AHB 12 August 2005

Added note: As of 15 August 2005, the Lafitte-Papazian search is still underway. An additional high scoring machine of theirs has been added to the list here. They have so far found eight 3x3 machines that take in excess of 100,000,000 steps to completion.

• ## A New Discovery for S(2,4) and BB(2,4) Made by Father-Son Team

• Since wrapping up my crude "brute force" (3,3) search in December 2004, I have also been in communication with Terry Ligocki who, teamed with his son Shawn, uncovered the amazing fact that S(2,4)>=3,932,964. This is nearly three orders of magnitude greater than my S(2,4)>=7,195 result that has stood since 1986. The Ligockis were searching the 2x5 space using a technique involving "simulated annealing".

Interestingly, I had determined just before starting my (3,3) search in the fall that either S(2,4)=7,195 or else S(2,4)>500,000. Now, I can state unequivocally that there are no other (2,4) machines which halt between my 7,195 shifts (steps) value from nearly twenty years ago and the astounding new value found earlier this year by the Ligockis.

• -- AHB 12 August 2005

• ## Yet Another New Machine!

• 2004 December 5: A new 3x3 Turing machine which more than triples
• the previous high shifts has been found taking 92,649,163 steps to a
• halt (its "shift number") with a "score" of 13,949. Further details
• to be posted later. -- AHB 6 Dec. 04
• 2004 December 12: A final sweep of "all" 3x3 machines under a 100
• million step limit on a 30 thousand square tape was completed. Two
• more machines were found with shift numbers of 47,287,015 and
• 51,525,774 respectively. All three new machines have been added to
• the previous "top 50" machines below (now a list of the "top 53").
• -- AHB 14 Dec. 04

• The most recent search of the 3x3 Turing machines
• is now complete as of 20 November 2004.
• RESULTS WILL BE POSTED AS TIME ALLOWS.
• We are attempting to improve the format. A link to
• the html text of my announcement of November 14, 2004
• regarding the new lower limit of 29,403,894 for S(3,3)
• is given below. There are four machines with shift numbers
• in the 15 million step range. Those machines are shown
• along with some other high scoring machines that were found
• during the last week of computer runs. 100% of the machines
• in the 3x3 tree have now been tested under a 50,000,000 move
• limit on a 20,000 square tape. This was an impromptu effort,
• not a carefully thought out project, so the output is jumbled.
• There are lots of interesting things to include, but they will
• have to wait until I have combined and culled the data.
• -- Allen Brady 20 November 2004

Announcement (14 Nov 2004) of new result for S(3,3) related to Rado's Busy Beaver Game.

Examination of the more than 28 million 3-state by 3-symbol machines is now complete. A preliminary inspection of the results shows a total of 50 machines were discovered with shift numbers ranging from 947,146 to 29,403,894. The machine with the largest shift number also had the largest output string and the largest SCORE (per Rado) of 5,600 marks on its output tape (all 1's).

It does not appear to be the case that any new machines cropped up in the latest computer runs (50 million move limit on a 20,000 square tape) that were not seen by the previous run (10 million move limit on a 10,000 square tape) just because they happened to operate outside the limit of the smaller tape. Until a detailed comparison is made, however, this is not absolutely certain.

The New Higher Shift (3,3) Machines Found by Others.

The 53 Highest Shift Machines. (From my own search as of 12 December 2004)

The high scoring machines were distributed across most of the branches of the generated tree. As time allows, all of these machine descriptions will be posted. The 53 machines are grouped by the range of their shift numbers as follows:

Among the machines found in this search is one of the most amazing Turing machines I have ever run across. It absolutely stunned me. I have given it a special name:

It will both surprise you and confound you. Logicians, mathematicians, computability instructors, please take note. Students, check this out, and surprise your teacher (who won't believe it).

Added Note. Myron Souris tells us that he also found this machine during his search and was likewise very surprised by its uniqueness. I have yet to hear from anyone or read about a detailed analysis. The possibility of opposing counters came to my mind. That is also what Heiner Marxen suggested. (Marxen was actually completely fooled by the machine on first examination.) Souris thinks it might be a combination of a counter and the Collatz-like behavior discussed by Pascal Michel. An analysis of this BBSB machine still awaits. I would offer an award for the answer, but what more of an award or prize is needed than the self-satisfaction that comes with discovery?

Other Web Sites.

See the OTHER BB WEB SITES of potential interest.

Ligocki-Ligocki: 4,345,166,620,336,565 - 119,112,334,170,342,540 (two machines)

(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!

Ligocki-Ligocki #0''' (CHAMPION as of 9 November 2007!):

1 R q2, 2 L q1, 1 L q3;
0 L q1, 2 R q2, 1 L q2;
1 R q0, 1 R q1, 1 R q3;

The columns in the description shown above correspond to the three symbols 0, 1, 2, while the rows correspond to the states q1, q2, q3. Each triplet specifies "print symbol" (0, 1 , or 2), "move right" (R) or "move left" (L), change to (or remain in) the "specified state" (q1, q2, or q3) for the machine's current state (row) and the current character (column) being scanned on the machine's tape. "Halt" is indicated by branching into a final (uncounted) state q0.

Here are the edited results of a computer simulation where the Ligockis' new Turing machine was started in the center of an 8,000,000 square blank (all "0") tape:

Initial Configuration: (400000000*0)>q1>0(400000000*0)
Final Configuration: (25323651*0)(1*1))>q0>((1*1) (374676381*2) (399999966*0)

Thu Nov 15 15:21:15 2007
MACHINE HALTED AFTER (119,112,334,170,342,540) STEPS

The "score" for this machine is the total 1 + 1 + 374,676,381 = 374,676,383 of non blanks (non zeros) remaining on the final tape.

(NOTE. The number of "Shifts" = 119,112,334,170,342,540 steps to the final halt (q0) configuration from the initial configuration in the manner of Tibor Rado.)

The notation used in the machine description shown duplicates the notation used in my Emacs LISP simulation which required many hours on a very fast (circa 3 ghz) Linux-based computer. My crude computer code unfortunately does not attain anything like the speed and sophistication of the Ligockis' techniques which include their own improvements on the techniques originally pioneered by Marxen and Buntrock in the latters' search for complex small machines.

Ligocki-Ligocki #0'' (Former Champion announced 20 August 2006!):

q2 R 1, q3 R 2, q1 L 1;
q1 L 2, q2 R 1, -halt-;
q2 R 2, q1 R 2, 3 L 1;

Initial Configuration: (100000000*0)>q1>0(100000000*0)
Final Configuration: (99999980*0)(95524078*1)>q2>2(4475941*0)
(Shifts = 4,345,166,620,336,565 steps to the final configuration counting the initial configuartion.)

Note that allowing the machine (in the style of Tibor Rado) to print a "one" and move right in the transition to "halt" would make the last output symbol = "1", but not add another shift to the count stated. If an added final "shift" is counted, then, for consistency, we do not count the initial configuration, but instead start counting with the first transition.

Lafitte-Papazian: 1,808,669,046 - 4,144,465,135,614 (5 machines shown)

(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.

Lafitte-Papazian #0' (Former Champion from 4 April 2006!):

2 R 1 , 0 0 0 , 3 L 2;
3 L 1 , 2 R 2 , 2 L 1;
1 L 1 , 3 R 2 , 1 L 2;

Initial Configuration: (3000000*0)>q1>0(3000000*0)
Final Configuration: not available
(Shifts = 4,144,465,135,614 steps to final configuration.)

Lafitte-Papazian #0 (Former Champion!):

2 1 1 , 1-1 2 , 1 1 1;
3 1 1 , 2 1 2 , 3 1 0;
1-1 1 , 0 0 0 , 1-1 1;

Initial Configuration: (1550000*0)>q1>0(1549999*0)
Final Configuration: (1549977*0)1(762843*[12])0>q3>1(24334*0)
(Segments shown on either end are untraversed portions of tape.
Shifts = 987,522,842,126 steps to final configuration.)

Lafitte-Papazian #1:

2 1 1 , 0 0 0 , 2 1 2;
3-1 1 , 2-1 0 , 1 1 1;
1 1 1 , 3-1 2 , 3 1 1;

(Shifts=4,939,345,068 Output Length=107,900)

Lafitte-Papazian #2:

2 1 1 , 1-1 2 , 1 1 1,
3-1 1 , 1-1 1 , 3 1 2,
0 0 0 , 1-1 1 , 2 1 2;

(Shifts=1,808,669,046 Output Length=43,925)

Lafitte-Papazian (new) #3:

2 1 1 , 1-1 2 , 1 1 1,
2-1 1 , 1-1 1 , 3 1 2,
0 0 0 , 3-1 1 , 2 1 2;

(Shifts=1,808,669,066 Output Length>=43,925)

Souris: 310,341,163 - 544,884,219 (3 machines)

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.

Souris No. 1:

2 1 1 , 2-1 1 , 1-1 2;
1-1 1 , 3 1 1 , 0 0 0;
1-1 0 , 3 1 2 , 3-1 1;

(Shifts = 544,884,219 Output Length = 32,213)

Souris No. 2:

2 1 1, 1-1 0, 1-1 1,
3 1 2, 3 1 1, 0 0 0,
3-1 2, 1 1 1, 3 1 0;

(Shifts = 408,114,977 Output Length = 20,240)
Souris No. 3:

2 1 1, 1 1 2, 3 1 2,
3-1 1, 0 0 0, 1-1 1,
1 1 1, 2-1 2, 3-1 1;

(Shifts = 310,341,163 Output Length=36,089)

92,649,163 (1 machine)

This once surprising machine was the reigning "Champion" (both shifts and score) for 3x3 Turing machines from 6 December 2004 until we learned of the earlier unrevealed discoveries of Myron Souris (above). Note that both its shift number and score are about twice the present known lower bound values for 5x2 machines. ( For output details and score click here. ) Still there is no reason to assume that this the largest possible shift number for 3x3 machines. The previous 3x3 "Champion" (shift number = 29,403,894) which reigned for all of three weeks, had an "immediate superior" (47,287,015 shifts) which might have been found in the same earlier sweep, except that the limiting tape size being used was, unfortunately, too small to accommodate the final output of the higher scoring machine.

# 16812191 :

2 1 1 , 0 0 0 , 3-1 2;
3-1 1 , 2 1 2 , 2-1 1;
1-1 1 , 2 1 0 , 1-1 2;

(Shifts =92,649,163 Output Length = 13,949)

47,287,015 - 51,525,774 (2 machines)

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.

# 4290607 :

2 1 1 , 1-1 2 , 1-1 1;
1-1 2 , 3 1 1 , 2 1 2;
0 0 0 , 3-1 0 , 1 1 0;

(Shifts = 51,525,774 Output Length = 7,210)

# 4812308 :

2 1 1 , 1 1 2 , 1-1 1;
1-1 2 , 2-1 2 , 3 1 2;
0 0 0 , 2 1 2 , 2 1 1;

(Shifts = 47,287,015 Output Length = 12,289)

29,403,894 (1 machine)

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!

# 18886871:

2 1 1 , 1 1 2 , 1-1 1;
3-1 2 , 3 1 0 , 2 1 1;
0 0 0 , 1-1 2 , 2 1 1;

(Shifts=29,403,894 Output Length=5,599)

15,701,167- 15,725,661 (4 machines)

# 10948781 :

2 1 1 , 1-1 1 , 1-1 2;
2-1 1 , 3 1 1 , 0 0 0;
1-1 1 , 3 1 2 , 3-1 1;

(Shifts = 15,725,661 Output Length = 4,098)

# 14388496 :

2 1 1 , 1-1 1 , 0 0 0;
3-1 0 , 2 1 2 , 2-1 1;
1 1 1 , 3-1 1 , 3-1 2;

(Shifts = 15,725,629 Output Length = 4,096 )

# 14389397 :

2 1 1 , 1-1 2 , 0 0 0;
3-1 0 , 2 1 2 , 2-1 1;
1 1 1 , 3-1 1 , 3-1 2;

(Shifts = 15,701,167 Output Length = 4,094)

# 25523247 :

2 1 1 , 1-1 1 , 1-1 2;
3 1 2 , 3 1 1 , 0 0 0;
1-1 1 , 3 1 2 , 3-1 1;

(Shifts = 15,725659 Output Length = 4,098)

11,597632 - 12,931,782 (2 machines)

# 9254067 :

2 1 1 , 1-1 2 , 1 1 1;
2-1 1 , 1-1 1 , 3 1 1;
0 0 0 , 1-1 2 , 2 1 2;

(Shifts = 11,597,632 Output Length = 3,680)

# 23193917 :

2 1 1 , 1 1 2 , 1-1 1;
3 1 0 , 3 1 1 , 1-1 2;
3-1 2 , 2 1 1 , 0 0 0;

(Shifts = 12,931,782 Output Length = 5,209)

8,134,503 - 8,152,753 (5 machines)

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.

# 2162653 :

2 1 1 , 2 1 2 , 3-1 1 ;
1-1 1 , 2 1 2 , 2-1 1 ;
0 0 0 , 2-1 2 , 1-1 2;

(Shifts = 8,134,503 Output Length = 3,684)

# 2164214 :

2 1 1 , 2 1 2 , 3-1 1 ;
1-1 1 , 2 1 2 , 2-1 1 ;
0 0 0 , 2-1 2 , 3 1 0;

(Shifts = 8,152,753 Output Length = 3,684)

# 2165244 :

2 1 1 , 2 1 2 , 3-1 2 ;
1-1 1 , 2 1 2 , 2-1 1 ;
0 0 0 , 2-1 1 , 1-1 1;

(Shifts = 8,141,799 Output Length = 3,684

# 3380843 :

2 1 1 , 3 1 1 , 3-1 2 ;
1-1 1 , 2 1 2 , 2-1 1 ;
0 0 0 , 2-1 1 , 1-1 1;

(Shifts = 8,141,811 Output Length = 3,684)

# 22223935 :

2 1 1 , 2 1 2 , 3-1 1;
3-1 2 , 1 1 1 , 0 0 0 ;
2 1 2 , 3 1 2 , 3-1 1;

(Shifts = 8,137,941 Output Length = 3,684)

4,959,315 - 5,117,632 (4 machines)

# 16455916 :

2 1 1 , 0 0 0 , 3-1 2 ;
3-1 1 , 2 1 2 , 2-1 1;
1-1 1 , 2-1 2 , 1-1 2;

(Shifts = 5,117,632 Output Length = 3,279)

# 17658000 :

2 1 1 , 0 0 0 , 2 1 2 ;
3-1 1 , 1-1 2 , 1 1 1 ;
1 1 1 , 3-1 2 , 3 1 1;

(Shifts = 4,959,323 Output Length = 3,418)

# 17658467 :

2 1 1 , 0 0 0 , 2 1 2 ;
3-1 1 , 1 1 1 , 1-1 1 ;
1 1 1 , 3-1 2 , 3 1 1;

(Shifts = 4,967,241 Output Length = 3,418)

# 17658470 :

2 1 1 , 0 0 0 , 2 1 2 ;
3-1 1 , 1 1 1 , 1 1 1 ;
1 1 1 , 3-1 2 , 3 1 1;

(Shifts = 4,959,315 Output Length = 3,418)

3,914,655 - 3,963,836 (29 machines)
Only three representative machines are shown here.
The entire group will be added eventually

# 2678468 :

2 1 1 , 3-1 1 , 0 0 0;
1-1 1 , 3-1 1 , 2 1 2;
2 1 1 , 3-1 2 , 3 1 1;

(Shifts = 3,932,964 Output Length = 2,050)

# 15019325 :

2 1 1 , 1-1 2 , 1 1 1 ;
3-1 1 , 2 1 1 , 3 1 1 ;
0 0 0 , 1-1 1 , 3 1 2;

(Shifts = 3,932,994 Output Length = 2,050)

# 26229964 :

2 1 1 , 0 0 0 , 2-1 2 ;
3 1 2 , 2 1 2 , 2-1 1 ;
1-1 2 , 3 1 1 , 2-1 1;

(Shifts = 3,926,835 Output Length = 2,049)

2,315,619 - 2,382,044 (2 machines)

# 1732367 :

2 1 1 , 2-1 2 , 3-1 1 ;
1-1 1 , 2 1 2 , 2 1 1 ;
0 0 0 , 1-1 2 , 3-1 0;

(Shifts = 2,315,619 Output Length = 49)

# 9257347 :

2 1 1 , 1-1 2 , 1 1 1 ;
2-1 1 , 1-1 1 , 3 1 2 ;
0 0 0 , 1 1 2 , 2 1 2;

(Shifts = 2,382,044 Output Length = 1,596)

947,146 - 1,302,660 (3 machines)

# 1348214 :

2 1 1 , 1-1 2 , 1 1 1 ;
1-1 1 , 1 1 0 , 3 1 2 ;
0 0 0 , 1 1 2 , 2 1 1;

(Shifts = 947,146 Output Length = 1,258)

# 1374873 :

2 1 1 , 1-1 2 , 1-1 0 ;
1-1 1 , 0 0 0 , 3 1 2 ;
1 1 2 , 3 1 0 , 1 1 0;

(Shifts = 1,053,191 Output Length = 1,068)

# 1526279 :

2 1 1 , 2-1 1 , 1-1 2 ;
1-1 1 , 2 1 2 , 3 1 2 ;
0 0 0 , 1-1 0 , 3-1 1 ;

(Shifts = 1,302,660 Output Length = 2,334)

BUSY-BEAVER SCORE

Rado's "score" for a Busy-Beaver Game champion candidate was the number of "marks" on the output tape. The scoring routine in the program I used was slightly altered to count the number of squares from the leftmost non-blank symbol (1 or 2) to the rightmost non-blank, inclusive. This gave me a rough idea of the range of excursion over the tape, but that clearly is not a measure of the actual excursion extremes. E.g., the output (non-blank output string), could simply travel along the tape. To get the highest "score" then, one simply has to count the number of 1's and 2's marked on the output tapes of the machines with the highest "Excursion" or "Range" values that were detected. For most of the high shift machines I have observed there were very few 0's or "blanks" embedded in the final output string. The score for the
29,403,894 shift machine was 5,600. In this case the final output was all 1's, which makes the matter of counting 2's as well as 1's moot if anyone wishes to differ with me on this scoring convention.

Added Note (23 Nov 04): I have expunged the terms "excursion" and "range" which I temporarily used in my computer output. Henceforth I shall use the term "Output Length" to describe the length of the output string from the leftmost nonblank symbol to the rightmost, inclusive.

OTHER WEBSITES

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.