Busy beaver

Busy Beavers (also Engl. Busy Beaver ) are Turing machines that write as many ones on the tape, without getting into an infinite loop (ie the hold after a finite number of computational steps ). The Radó function ( also Hardworking Beaver function) specifies the maximum number of ones that can write an industrious beaver with a given number of states. Both were first considered in 1962 by Hungarian mathematician Tibor Radó.

Formal consideration

Definition

An industrious beaver is a Turing machine with a two-element alphabet and states that holds and above the maximum number of ones writing on a blank ( consisting of zeros) band, compared with all other holding Turing machines also states. Only Turing machines that do not hold, can write more ones.

Hardworking Beaver Function

About the number of ones that writes an industrious beaver with states, the value of Hardworking Beaver function (also Radó function) defined on the site: .

Non- solvable problem

The determination of the industrious beaver is a problem that is not generally algorithmically solvable. So is not generally decidable whether a given Turing machine with states actually writes a string of ones maximum length. For individual Turing machines low complexity which is, however, possible. So the set of values ​​of is neither decidable nor recursively enumerable, although it is well-defined. Since the complement of this set is not recursively enumerable, this amount is often chosen as an example of a language that is not in the first level of the arithmetical hierarchy.

Because of these properties, the set of values ​​the function can not be calculated. One can show that their asymptotic growth is stronger than any computable function well.

Useful viewing

In practice it has been shown that, realistically, even for a recognition of the value does not seem to be possible. One would have for each Turing machine with states each to find out how many steps it considers, or otherwise prove that it does not. By examining certain properties could now at least for the 40 machines that show no regular behavior, a subdivision in holding machines, write the maximum 4098 ones, and not just machines to be made.

≥ 501 (1983, Uwe Schult ) ≥ 1915 (1984, George Uhing ) ≥ 4098 (1989, Jürgen Buntrock and Marxen Heiner )

The number of Turing machines here calculated according to.

Note on the calculation: A Hardworking beaver makes after writing one step to the right or left before he takes up the new state. So he keeps never held on the same field as long as he has not taken the "Halt ".

The S function

Radó additionally defined a function whose value is the maximum number of steps a Turing machine with holding zweielementigem alphabet and states. This function can not be calculated; they would be there, so the halting problem with empty input tape would be decidable, since a Turing machine with states, which makes up more than steps, never stops.

Since, in each step, a maximum of one can be written is valid

Between the functions and persists the following relationship.

Also not computable function

One also not computable function is obtained if the additional restriction is introduced, all ones that have to form a contiguous string.

As a term for it has become common.

1965 C. Dunham has given a further variant of the function of the industrious beaver. is defined as the maximum number of ones that can write a Turing machine with zweielementigem alphabet and states when it is set on a tape with a block of ones and keeps it. If this function is computable, so there would be a Turing machine M with alphabet zweielementigem that calculates. This Turing machine have states. Then would be, where the equal sign is just the definition of M, and therefore stirs the characters that M indeed is a machine with states and recognized (ie a block of ones ) holds, and therefore satisfy the inequality by definition of D must. This contradiction shows the non- predictability of D.