Hardworking beaver

Hardworking beaver (also English busy beaver ) are special Turing machine , the possible write many ones on the tape and after a finite number calculation steps to halt state taking (ie pause ). The Radó function (also hard-working beaver function ) indicates the maximum number of ones that a hard-working beaver can write with a given number of states. Both were first considered in 1962 by the Hungarian mathematician Tibor Radó .

Formal consideration

definition

According to Radó, a hard-working beaver is a Turing machine, which, as usual, can assume states and a halt state. In contrast to the general definition of a Turing machine, however, it is subject to special rules. A hardworking beaver always has to move either to the left or to the right on the belt. So there is no instruction here to remain in a field. A hardworking beaver does not expect empty fields either, only those that already contain a value from the two-element alphabet he is familiar with . The tape on which the hard-working beaver is placed is completely filled with zeros beforehand. A hard-working beaver has to assume the halt state after a finite number of steps, i.e. it must not get into an endless loop. After stopping , it must have written the maximum number of ones, compared to all other Turing machines that also have states that work according to the same rules. Only Turing machines that do not hold could write more ones, but then would not be hardworking beavers. ${\displaystyle n}$ ${\displaystyle \{0,1\}}$ ${\displaystyle k_{n}}$ ${\displaystyle n}$

Hardworking beaver function

The maximum number of ones which a diligent beaver with write conditions, the value of the Out hard Beaver function (also Radó function) at the location defined . ${\displaystyle k_{n}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \Sigma (n)=k_{n}}$

Unsolvable problem

The determination of the hardworking beavers is a problem that cannot generally (for everyone ) be solved algorithmically. It is not generally possible to decide whether a given Turing machine with states actually writes a maximum number of ones on the tape. However, this is possible for individual Turing machines of low complexity. So the set of values ​​of is neither decidable nor recursively enumerable , although it is well-defined . Since the complement of this set cannot be recursively enumerated either, this set is often chosen as an example for a language that is not in the first level of the arithmetic hierarchy . ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \Sigma (n)}$ ${\displaystyle \Sigma (n)}$

Because of these properties of the value set, the function cannot be calculated . It can also be shown that its asymptotic growth is stronger than that of any computable function. ${\displaystyle \Sigma }$

Practical consideration

In practice it has been shown that even realistically speaking, it no longer seems possible to know about the value . To do this, one would have to find out for each individual Turing machine with states after how many steps it holds, or else prove that it does not. For a given number of states (plus a hold state) there are different Turing machines for an alphabet with two characters , because for each of the input states it must be determined for each of the two possible read symbols which of the two symbols is to be written on the tape and in which direction the reading head should be moved and which of the possible states the Turing machine should then assume. Different Turing machines have to be considered even with possible input states. ${\displaystyle n>5}$ ${\displaystyle \Sigma (n)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle (2\cdot 2\cdot (n+1))^{2n}}$ ${\displaystyle n}$ ${\displaystyle n+1}$ ${\displaystyle n=5}$ ${\displaystyle 24^{10}}$

The Bulgarian Georgi Georgiev published a study in 2003 in which he analyzed diligent beavers to see whether they would stop or not. For only just over 40 hardworking beavers evaded a reliable result, because they could not be finally analyzed with the methods used by Georgiev due to special behavior. Of those determined to be terminating (sustained), none writes more than 4098 ones on the tape. ${\displaystyle n=5}$

conditions ${\displaystyle n}$	Turing machines	${\displaystyle \Sigma (n)}$	source
1	64	1	(1962; Rado)
2	20736	4th	(1962; Rado)
3	16777216	6th	(1965; Lin, Rado)
4th	2.56 x 10 10	13	(1972; Weimann, Casper, Fenzel)
5	≈ 6.34 × 10 13	≥ 240	(1983; Jochen Ludewig)
		≥ 501	(1983; Uwe Schult)
		≥ 1915	(1984; George Uhing)
		≥ 4098	(1989; Jürgen Buntrock and Heiner Marxen)
6th	≈ 2.32 × 10 17	> 3.514 × 10 18267	(2010; Pavel Kropitz)
7th	≈ 1.18 × 10 21	Estimation unrealistic

Examples

Hardworking beaver with a condition

${\displaystyle M=(\{q_{0},q_{f}\},\{\},\{0,1\},\delta ,q_{0},0,\{q_{f}\})}$

The partial transfer function is defined as follows: ${\displaystyle \delta }$

Hardworking beaver with a condition

current state	read. symbol		schr. symbol	new condition	Head direction
${\displaystyle q_{0}}$	0	→	1	${\displaystyle q_{f}}$	R.

${\displaystyle M}$ runs through the following states, whereby the current head position is printed in bold:

step	Condition	tape
1	${\displaystyle q_{0}}$	0 0
holds	${\displaystyle q_{f}}$	1 0

Hardworking beaver with 2 states

${\displaystyle M=(\{q_{0},q_{1},q_{f}\},\{\},\{0,1\},\delta ,q_{0},0,\{q_{f}\})}$

The transfer function is defined as follows: ${\displaystyle \delta }$

Hardworking beaver with 2 states

current state	read. symbol		schr. symbol	new condition	Head direction
${\displaystyle q_{0}}$	0	→	1	${\displaystyle q_{1}}$	R.
${\displaystyle q_{0}}$	1	→	1	${\displaystyle q_{1}}$	L.
${\displaystyle q_{1}}$	0	→	1	${\displaystyle q_{0}}$	L.
${\displaystyle q_{1}}$	1	→	1	${\displaystyle q_{f}}$	R.

${\displaystyle M}$ runs through the following states, whereby the current head position is printed in bold:

step	Condition	tape
1	${\displaystyle q_{0}}$	… 000 0 000…
2	${\displaystyle q_{1}}$	… 0001 0 00…
3	${\displaystyle q_{0}}$	... 000 1 100 ...
4th	${\displaystyle q_{1}}$	… 00 0 1100…
5	${\displaystyle q_{0}}$	… 0 0 11 100…
6th	${\displaystyle q_{1}}$	… 01 1 1100…
holds	${\displaystyle q_{f}}$	… 011 1 100…

Hardworking 3 condition beaver

${\displaystyle M=(\{q_{0},q_{1},q_{2},q_{f}\},\{\},\{0,1\},\delta ,q_{0},0,\{q_{f}\})}$

The transfer function is defined as follows: ${\displaystyle \delta }$

Hardworking 3 condition beaver

current state	read. symbol		schr. symbol	new condition	Head direction
${\displaystyle q_{0}}$	0	→	1	${\displaystyle q_{1}}$	R.
${\displaystyle q_{0}}$	1	→	1	${\displaystyle q_{f}}$	R.
${\displaystyle q_{1}}$	0	→	0	${\displaystyle q_{2}}$	R.
${\displaystyle q_{1}}$	1	→	1	${\displaystyle q_{1}}$	R.
${\displaystyle q_{2}}$	0	→	1	${\displaystyle q_{2}}$	L.
${\displaystyle q_{2}}$	1	→	1	${\displaystyle q_{0}}$	L.

${\displaystyle M}$ runs through the following states, whereby the current head position is printed in bold:

step	Condition	tape
1	${\displaystyle q_{0}}$	0 0 0000
2	${\displaystyle q_{1}}$	01 0 000
3	${\displaystyle q_{2}}$	010 0 00
4th	${\displaystyle q_{2}}$	01 0 100
5	${\displaystyle q_{2}}$	0 1 1100
6th	${\displaystyle q_{0}}$	0 11100
7th	${\displaystyle q_{1}}$	1 1 1100
8th	${\displaystyle q_{1}}$	11 1 100

step	Condition	tape
9	${\displaystyle q_{1}}$	111 1 00
10	${\displaystyle q_{1}}$	1111 0 0
11	${\displaystyle q_{2}}$	11110 0
12	${\displaystyle q_{2}}$	1111 0 1
13	${\displaystyle q_{2}}$	111 1 11
14th	${\displaystyle q_{0}}$	11 1 111
holds	${\displaystyle q_{f}}$	111 1 11

The function S

Radó also defined a function whose value is the maximum number of steps of a holding Turing machine with a two-element alphabet and states. This function cannot be calculated either; if it were, the stopping problem with an empty input tape could be resolved , because a Turing machine with states that does more than steps never stops. ${\displaystyle S(n)}$ ${\displaystyle n}$ ${\displaystyle S}$ ${\displaystyle n}$ ${\displaystyle S(n)}$

Since a maximum of one can be written in each step, the following applies

${\displaystyle S(n)\geq \Sigma (n)}$.

The following relationship still exists between the functions and . ${\displaystyle \Sigma }$ ${\displaystyle S}$

${\displaystyle S(n)<\Sigma (3n+6)}$.

Also not calculable function

Another non-calculable function results if the additional restriction is introduced that all ones must form a coherent chain.

The name for it has become common. ${\displaystyle \sigma (n)}$

In 1965, C. Dunham specified another variant of the function of the hardworking beaver. is defined as the maximum number of ones that a Turing machine with a two-element alphabet and states can write if it is put on a tape with a block of ones and holds it. If this function were calculable, there would also be a Turing machine M with a two-element alphabet that calculates. This Turing machine has states. Then , where the equal sign is precisely the definition of M, and the sign stems from the fact that M is a machine with states and is attached to (i.e. a block of ones) and therefore, according to the definition of D , must satisfy the inequality . This contradiction shows the unpredictability of D. ${\displaystyle D(n)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n\mapsto D(n)+1}$ ${\displaystyle m}$ ${\displaystyle D(m)+1=M(m)\leq D(m)}$ ${\displaystyle \leq }$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle M(m)\leq D(m)}$

literature

• AK Dewdney : The (new) Turing Omnibus. 66 Excursions in Computer Science. Computer Science Press, New York NY 1993, revised 1996, ISBN 0-7167-8271-5 .
• Jochen Ludewig, Uwe Schult, Frank Wankmüller: Chasing the Busy Beaver. Notes and Observations on a competition to find the 5-state Busy Beaver. University of Dortmund - Department of Computer Science, Dortmund 1983 ( Department of Computer Science, University of Dortmund. Report 159).
• Heiner Marxen, Jürgen Buntrock: Attacking the Busy Beaver 5 . In: Bulletin of the EATCS. 40, February 1990, ISSN  0252-9742 , pp. 247-251.

Web links

• W. rooms: Busy Beaver (PDF, 97 KiB ), exact introduction to literature examples, at 10 pages for basic course Theoretical computer science at the Cusanus-Gymnasium Wittlich shown
• Reinhard Völler: Turing computability from theoretical computer science , brief description of Rado's busy beaver problem with some examples from literature, Hamburg University of Applied Sciences
• Heiner Marxen: Busy Beaver (English) - known results, many links (to research) up to 2010, including:
• In search of hard-working beavers - Turing machine simulators, University of Stuttgart 1996

Individual evidence

1. ↑ ^{a b} T. Radó: On non-computable functions ( Memento of March 27, 2014 in the Internet Archive ) (PDF; 3.6 MB; WebArchive of March 27, 2014), In The Bell System Technical Journal , Volume 41, No. 3, pp. 877-884, May 1962
2. ↑ Busy Beaver non-regular machines for class TM (5)
3. ↑ AM Ben-Amram, BA Julstrom, U. Zwick: A Note on Busy Beavers and Other Creatures , In Mathematical Systems Theory , 29 (4), pp. 375-386, July / August 1996, doi: 10.1007 / BF01192693
4. ^ C. Dunham: A Candidate for the simplest uncomputable function In: Communications of the Association for Computing Machinery (Letter to the Editor) 8, 4, 1965, ISSN  0001-0782 , p. 201