From: heiner@DrB.Insel.DE (Heiner Marxen)
Subject: 6-state busy beaver news
Date: Sun, 20 Aug 2000 17:19:34 GMT
Newsgroups: comp.theory,sci.math
Summary: [missing]

Hello busy beaver fans,

In early August 2000 I posted a new busy beaver champion with 6 states
(5-tupel TM).  It produces more than 10^21 ones in more than 10^42 steps.

Transition table of this new machine:

    on  0   1
    A: B1R C0R
    B: A0L D0R
    C: D1R H1R
    D: E1L D0L
    E: F1R B1L
    F: A1R E1R

Final Ones:		2,537,699,363,594,175,843,063
Final tape position:	839 (to the right of the start position)
Final configuration:	1^2537699363594175843062 0 1 H>
(A large compact block of ones, a zero, a one and the head scanning
the empty right part of the tape)

The news are...

At 14-Aug-2000 I received e-mail from Chris Thompson, who independently
does confirm the above number of ones, and the final configuration.
Moreover, he also computed the total number of steps to be:
Steps:	5,366,598,383,321,904,238,506,234,609,927,865,294,538,105
i.e. 5.3*10^42 (which fits into the bounds I posted last time).

We would appreciate an independent confirmation of this number of steps.

I have also just today updated my busy beaver simulation web pages,
which now includes true macro machine simulations:
    http://www.drb.insel.de/~heiner/BB/bbsimtab.html
The awk program to perform these simulations is also available, there.

Finally, the above "monster" is (by far) not the best 6-state BB candidate.
We are currently busy searching/listing/analysing even bigger ones.
We will follow-up on that within the next weeks.

Cheers,
-- 
Heiner Marxen	heiner@drb.insel.de	http://www.drb.insel.de/~heiner/
==============================================================================

From: heiner@DrB.Insel.DE (Heiner Marxen)
Subject: A new 6-state busy beaver champion (> 10^21 ones)
Date: Sat, 5 Aug 2000 14:35:53 GMT
Newsgroups: comp.theory,sci.math

In early July 2000 we (Juergen Buntrock and Heiner Marxen) have discovered
a new busy beaver champion with 6 states (5-tupel TM).
It produces more than 10^21 ones in more than 10^42 steps.

Transition table of this new machine:

    on  0   1
    A: B1R C0R
    B: A0L D0R
    C: D1R H1R
    D: E1L D0L
    E: F1R B1L
    F: A1R E1R

Final Ones:		2,537,699,363,594,175,843,063
Final tape position:	839 (to the right of the start position)
Final configuration:	1^2537699363594175843062 0 1 H>
(A large compact block of ones, a zero, a one and the head scanning
the empty right part of the tape)

We do not yet know the exact number of steps.  A macro machine using 2-bit
symbols (and a 2-bit context coded into its state) uses so many steps:
macro-steps:	1,788,866,127,773,968,079,497,172,864,450,133,057,703,778
The real number of steps is at most 11 times the above number.

We have used two different programs to compute the (same) number
of ones.  We would appreciate independant verification of the
number of ones and the number of steps of this remarkable machine.

Some remarks:
- In its main loop this machine multiplies by 5/4, and uses the mod-4 remainder
  and some more (right) context to iterate many times before halting.
- After 3 steps this machine produces an empty tape and is in state C.
  Therefore there is an equivalent machine with renamed states, that
  yields the same final configuration with 3 steps less.
- An initial simulation fragment can be seen at:
  http://www.drb.insel.de/~heiner/BB/simmbL6_3.html

-- 
Heiner Marxen	heiner@drb.insel.de	http://www.drb.insel.de/~heiner/