IS THIS A NEW BUSY BEAVER LOWER LIMIT FOR S(3,3)?

Allen H. Brady

Dept. of Computer Science and Engineering
University of Nevada/171
Reno, NV 89557 USA


For those who are interested in the Busy Beaver Game (Busy Beaver problem) of Tibor Rado, I wish to report that, after recently finding five (5) Turing machines of three (3) states and three (3) symbols with "shift numbers" exceeding eight million (8,000,000), I have more than tripled that result. The Turing machine shown here, found early this morning, 14 November 2004, will halt in 29,403,894 steps after starting on a blank (all "0") tape. Its final output ranges over 5,599 squares.

As displayed by the search program the machine is described below as three groups for states 1, 2, and 3 (q1, q2, and q3) and within each group triplet entries for symbols 0, 1, and 2 in that order. Each numeric triplet (q,m,s) describes the next state, move, and printed symbol. The move value -1 stands for L or Left, and 1 stands for R or Right.

Sun Nov 14 01:23:02 PST 2004 u-20
"par3x3.c " running as "902.nice-ALatCS"
# 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=29403894 Excursion=5599 **NEW SHIFTS** **NEW RANGE**
Sun Nov 14 01:54:39 PST 2004


The line can be rearranged in tabular form as follows with the letter q appended to the states for clarity. I have refrained from any editing that might cause an error. [Table shown here was redesigned for web presentation.]

(symbols)

0 1 2
q1 q2 1 1 q1 1 2 q1-1 1
q2 q3-1 2 q3 1 0 q2 1 1
q3 (halt) q1-1 2 q2 1 1

3x3 Machine with "Shift Number" = 29,403,894
and "Score" = 5,600

The five 3x3 Turing machines with "shift numbers" greater than 8,000,000 may be seen on my web page at

http://www.cs.unr.edu/~al/BusyBeaver


I will also be posting other interesting finds as they may arise while I continue my final sweep through the entire(?) 3x3 tree using an upper limit of 50,000,000 steps on a tape restricted to 20,000 squares.

The program being used is a crude C language translation of a Pascal program which I wrote in 1986 to produce data for a chapter on the Busy Beaver Game contributed to Rolf Herken's book The Universal Turing Machine A Half-Century Survey (Oxford Univ. Press, 1988). It has been slightly modified to search separate branches of the tree with execution distributed over 12 to 18 laboratory PC's running simultaneously. The processors in the computers are supposedly equivalent to 1.5-2.0 ghz Pentiums and run under Linux on a local network with a central file server.

To put this nominal amount of computer power into perspective, consider the situation in 1964 when I discovered the "Champion" Busy Beaver Turing machine for four states (and two symbols) using a Scientific Data Systems SDS 920 computer at the Oregon Regional Primate Research Center in Beaverton(!). The first full run through the complete 4-state tree (approx. 600,000 nodes), limited to 90 steps per Turing machine, took nearly four (4) hours executing a machine language program. A single one of the laboratory machines above, executing my C program, will search that same tree for the 4-state case (with a 110 step limit) in one and one-half seconds! In 1964 after making the first run with the 90 move upper limit, I was chagrined a month later to discover the four-state champion among my several thousand "holdouts" as I ran quickly through them with a larger limit. (One four-state machine took 96 steps and the other took 107.) So, does anything lurk above 50,000,000 moves or outside a 20,000 square tape for BB(3,3)? If you find something out there, please let me know. The way the search has been progressing leads me to suspect there is at least one larger number further out. Good luck to anyone who might feel inspired to carry on. This searcher is worn out.


--Reno, Nevada
14 November 2004


Added Comment (15 November 2004):

It seems interesting to me that starting with Rado's Busy Beaver problem for three state Turing machines with two symbols if you add a single state then the problem (for four states and two symbols) does not quite get out of hand. However, if you instead add a single symbol, then the problem (for three states and three symbols) appears simply to explode! --AHB

.07.1