**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.]

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 |

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