User:LunaticFringe/Busy beaver

This tiny 6-state busy beaver runs for over 3×10¹⁷³⁰ steps before coming to a halt.

In computability theory, the busy beaver functions relate to the amount of work that an n-state Turing machine can do before halting. The functions were introduced by Tibor Radó in his paper "On Non-Computable Functions", published in the Bell System Technical Journal in May of 1952. The term "busy beaver" refers to Radó's idea of a Turing machine's tape head busily moving back and forth on the tape for a long, but finite, amount of time.

Record busy beavers

1. Σ(n): the largest number of 1's printable by an n-state machine before halting, and
2. S(n): the largest number of steps taken by an n-state machine before halting.

All machines are started on initially blank tapes, uses only two tape values (0 and 1) and those that do not halt are not candidates.

Both of these functions are uncomputable in general. Their properties are related to halting problem and they grow faster than any computable function.

Even with only a few states, a Busy Beaver can do very much.

Current 5-state Busy Beaver champion machine produces 4098 ones, using 47176870 steps.

At the moment the record 6-state Busy Beaver produces over 10⁸⁶⁵ ones, using over 10¹⁷³⁰ steps.

The function values for Σ(n) and S(n) are known only for n<5.

In case n=5 there remain about 40 machines with nonregular behavior.

Generalizations

For any model of computations there exist simple analogs for Busy Beaver.

Allen Brady has determined Busy Beaver for machines with 3 states and 3-letter alphabet S(3,3)≥92649163.

The Busy Beaver for 6 state, 2-letter machines always reversing the tape value produces 6147 ones, using 47339970 steps. So S_RTM(6)≥47339970 and Σ_RTM(6)≥6147.

There is an analog to the Σ function for Minsky machines, namely the largest number which can be present in any register on halting, for a given number of instructions. This is a consequence of the Church-Turing thesis.

Trivial proof for uncomputability of S(n) and Σ(n)

Suppose that S(n) is a computable function and let EvalS denote a TM, evaluating S(n). Given a tape with n 1s it will produce S(n) 1's on the tape and then halt. Let Clean denotes a TM, cleaning the sequence of 1s initially written on the tape. Let Double denote a TM, evaluating function n + n. Given a tape with n 1s it will produce 2n 1s on the tape and then halt.

Let us create the composition Double|EvalS|Clean and let n₀ is the number of states of this machine. Let Create_n₀ denote a TM, creating n₀ 1s on an initially blank tape. This machine may be constructed in a trivial manner to have n₀ states (the state i writes 1, moves the head right and switches to state i + 1, except the state n₀, which halts). Let N denotes the summ n₀ + n₀.

Let BadS denote the composition Create_n₀|Double|EvalS|Clean. Notice that this machine has N states. Starting with an initially blank tape it first creates a sequence of n₀ 1s and then doubles it, producing a sequence of N 1s. Then BadS will produce S(N) 1s on tape, and at last it will clear all 1's and then halt. But the phase of cleaning will continue at least S(N) steps, so the time of working of BadS is strictly greater than S(N), which contradicts to the definition of the function S(n).

The uncomputability of Σ(n) may be proved in a similar way. We must exchange in upper proof the machine EvalS with EvalΣ and Clean with Increment - simple TM, searching for a first 0 on the tape and replacing it with 1.

Examples of lower-stage busy beavers

These are the first two sets of rules that generate the biggest Σ(n)... Result Key: (starts here, goes to here):

1-state:

	A
1	N/A
0	1-Halt

Result: 0 0 1 0 0 (one "1" total)

2-state:

	A	B
1	1B-Left	1-Halt
0	1B-Right	1A-Left

Result: 0 0 1 1 1 1 0 0 (four "1"s total)

External links

• The page of Heiner Marxen, who, with Jürgen Buntrock, found the above-mentioned records for a 5 and 6-state Turing machine.
• The page of Penousal Machado's Genetic Beaver Project uses Evolutionary Computation to find new candidates to the Busy Beaver Problem
• Definition of the class RTM - Reversal Turing Machines, simple and strong subclass of the TMs.
• Aaronson, Scott (1999), Who can name the biggest number?

Category:Computability