[Busy Beaver S(3,3)>=29,403,894] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


Busy Beaver S(3,3)>=29,403,894

(Click here to view the original thread with full colors/images)


Posted by: edpegg

From: Allen Brady <al@unr.edu>

Please note that as of today (15 November 2004) the result announced here has been confirmed by Heiner Marxen whom I wish to thank for taking the time to do it. He has also forwarded the note to J.Buntrock.--ahb
======================================================
======================================================
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. The table is designed for Courier plain text.

\Symbol: 0 1 2
State:\
-------------|--------|--------
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
|----------|--------|--------

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)


Posted by: Allen Brady

Since my announcement of 15 Nov. 2004, I completed a further search of the Busy Beaver 3x3 space to determine (as of 5 Dec. 2004) that S(3,3)>=92,649,163 and Sigma(3,3)>=13,949. Likewise, two more machines have cropped up with numbers exceding those of the previous discovery of 14 November 2004. The description of this latest three state, three symbol Turing machine can be seen at

http://www.cs.unr.edu/~al/NewShifts5December2004.html

which also includes a link to my new Busy Beaver Problem web page that summarizes results to date learned from this 3x3 search. For those who may be interested, Pascal Michel characterizes these machines as exhibiting "Collatz-like" behavior.
-- Allen Brady


Posted by: Jason Cawley

These are very nice results, congratulations on finding them, and thanks. I've tried to clean up the first post above to make it a little more readable (the forum software can be unkind to copied text). Please keep us informed about your TM investigations.


Posted by: Jason Cawley

We've received email announcement (forwarded to a list of those interested) of some further results with 2 head-state busy beaver TMs, using 4, 5 and 6 symbols. I've copied the annoucement below to let those who found them explain (email addresses removed for privacy) -

"Date: Thu, 17 Feb 2005 01:57:46 -0800
From: "Terry J. Ligocki"
To: Shawn Ligocki, Terry Ligocki
Subject: New Busy Beaver (5-tuple) Turing machine results...

My son, Shawn, and I have come up with some new results for the Busy Beaver problem using 5-tuple Turing machines. After communicating our results with Pascal Michel, Heiner Marxen, and Allen Brady and having them verified, Allen Brady suggested we communicate with a wider list of people.

We used simulated annealing to try and maximize the values of S(M) for a machine M, (n,m), with a given number of states, n, and symbols, m. We succeeded in improving the largest known value for S(2,4), Sigma(2,4) and finding lower bounds for S(2,5), Sigma(2,5), S(2,6), Sigma(2,6).

Here are our results:

2 states, 4 symbols:

A0 A1 A2 A3 B0 B1 B2 B3...................Sigma(M) S(M)
3RB 3RA 3RA 1LA 3LB 2RB 2LH 3LA ............... 2,050 3,932,964

2 states, 5 symbols:

A0 A1 A2 A3 A4 B0 B1 B2 B3 B4...................Sigma(M) S(M)
4LB 1RH 2RA 0LB 3LB 2RA 3LB 3RB 2LB 1LB ....... 4,099 15,754,273
4RB 2LA 4LA 4RA 3LA 1LA 4LA 4RA 3RB 3LH ....... 3,685 16,268,767

2 states, 6 symbols:

A0 A1 A2 A3 A4 A5 B0 B1 B2 B3 B4 B5.......... Sigma(M) S(M)
5RB 5RA 3RH 1RB 3LA 1LA 4LB 1RB 4LH 2RA 5LB 5LA 10,574 94,842,383
4RB 4RA 4RA 1LA 1LA 1LB 4LB 2RB 5LB 3RA 3LA 0RH 10,248 98,364,599

Some comments:

* Previous best (2,4) result was Sigma(2,4) = 90, S(2,4) = 7,195! Also, our (2,4) result seems to be related a (3,3) machine that has the same values for Sigma() and S() and a very similar tape evolution.

* We suspect that the (2,5) and (2,6) results are not the best
possible but they are a starting point. In fact, the first (2,6) machine has an unused transition (B2) which is an unused halting transition - Heiner Marxen found which halting transition was unused when he verified the result.

Please let us know if you have any questions or comments.


Sincerely,


Terry J. Ligocki
Shawn Ligocki

P.S. I am a staff scientist at the Lawrence Berkeley National Laboratory and Shawn is a freshman at Caltech..."


Posted by: Kovas Boguta

Hi,

I've made a notebook that shows these machines in action. Just by looking at their evolution, it is clear that these machines can be abstracted into some other kind of system that performs these sorts of computations more directly.


Posted by: edpegg

It's hard to tell whether these results will be imcomprehensibly mangled within the tiny, tiny margins of this entry screen. However, I'll try to post them through anyways:
-----------------------------------------------

Here are new (better) results for the Busy Beaver problems (2,5), (2,6),
(3,4), and (4,3) (states,symbols):

Turing machines with 2 states and 5 symbols:

+------ +------ +------ +------ +-------+
| 0 | 1 | 2 | 3 | 4 |
+-----+-------+-------+-------+-------+-------+
M = | A | 1RB | 4LA | 1LA | 2LA | 1RA | s(M) =
148,304,214
+-----+-------+-------+-------+-------+-------+
| B | 3LA | 1RH | 1RA | 2RA | 4RB | sigma(M)
= 11,120
+-----+-------+-------+-------+-------+-------+

Turing machines with 2 states and 6 symbols:

+------ +------ +------ +------ +------ +-------+
| 0 | 1 | 2 | 3 | 4 | 5 |
+-----+-------+-------+-------+-------+-------+-------+
M = | A | 1RB | 4LA | 1RA | 5LB | 1RA | 3LB
| s(M) = 493,600,387
+-----+-------+-------+-------+-------+-------+-------+
| B | 1LB | 1LA | 5LA | 2LA | 2RB | 1RH |
sigma(M) = 15,828
+-----+-------+-------+-------+-------+-------+-------+

Turing machines with 3 states and 4 symbols:

+------ +------ +------ +-------+
| 0 | 1 | 2 | 3 |
+-----+-------+-------+-------+-------+
M = | A | 1RB | 2LC | 0LC | 0RA | s(M) = 262,759,288
+-----+-------+-------+-------+-------+
| B | 3LC | 2RC | 1LB | 0RC | sigma(M) = 17,323
+-----+-------+-------+-------+-------+
| C | 1RA | 0LB | 1RH | 0RB |
+-----+-------+-------+-------+-------+

Turing machines with 4 states and 3 symbols:

+------ +------ +-------+
| 0 | 1 | 2 |
+-----+-------+-------+-------+
M = | A | 0RB | 1RH | 2LD | s(M) = 250,096,776
+-----+-------+-------+-------+
| B | 2LA | 2RD | 2RC | sigma(M) = 15,008
+-----+-------+-------+-------+
| C | 2RB | 2RC | 1LC |
+-----+-------+-------+-------+
| D | 2LA | 1RB | 2LC |
+-----+-------+-------+-------+

These were all found using simulated annealing to maximize either the
number of steps or the number of non-zero symbols. These new results
were generated maximizing the number of steps.

Note: M(4,3) is not in common canonical form - it starts with by
writing a 0. This can be "corrected" by swapping states A and B but the
resulting machine writes the same number of non-zero symbols and takes
one less step. As a result, we left M(4,3) in this form.

Please let us know if you have any questions, comments, or corrections.

Sincerely,

Terry J. (Ligocki, tjligocki@lbl.gov)
Shawn Ligocki (sligocki at sign caltech period edu)




Forum Sponsored by Wolfram Research

© 2004-2009 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings