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
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.)
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.
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.)
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.
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.
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.
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 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?
See the OTHER BB WEB SITES of potential interest.
(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!(Back to top)
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:
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.
(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.(Back to top)
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.(Back to top)
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.(Back to top)
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.(Back to top)
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!(Back to top)
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.
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.
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.
Back to my home page.
Latest update 1115 hrs PST 16 November 2007 (Newest 3x3 champion (Ligocki & Ligocki): 119 quadrillion steps)