Fleißiger Biber

Definition

Nach Radó ist ein fleißiger Biber eine Turingmaschine, die ${\displaystyle n}$ Zustände und einen Halt-Zustand einnehmen kann. Im Gegensatz zur allgemeinen Definition einer Turingmaschine unterliegt er jedoch speziellen Regeln.^[1] So muss ein fleißiger Biber als Bewegungsschritt immer entweder nach links oder rechts auf dem Band gehen. Es gibt hier also keine Anweisung zum Verharren auf einem Feld. Ein fleißiger Biber erwartet auch keine leeren Felder, sondern nur welche, die bereits einen Wert aus dem ihm bekannten zweielementigen Alphabet ${\displaystyle \{0,1\}}$ enthalten. Das Band, auf das der fleißige Biber aufgesetzt wird, ist zuvor vollständig mit Nullen gefüllt. Ein fleißiger Biber muss nach einer endlichen Anzahl Schritte den Halt-Zustand einnehmen, darf also nicht in eine Endlosschleife geraten. Er muss nach dem Anhalten die maximale Anzahl ${\displaystyle k_{n}}$ von Einsen geschrieben haben, verglichen mit allen anderen Turingmaschinen mit ebenfalls ${\displaystyle n}$ Zuständen, die nach den gleichen Regeln arbeiten. Nur Turingmaschinen, die nicht halten, könnten mehr Einsen schreiben, wären dann aber keine fleißigen Biber.

Fleißiger-Biber-Funktion

Über die maximale Anzahl ${\displaystyle k_{n}}$ von Einsen, die ein fleißiger Biber mit ${\displaystyle n}$ Zuständen schreibt, ist der Wert der Fleißiger-Biber-Funktion (auch Radó-Funktion) an der Stelle ${\displaystyle n}$ definiert:

${\displaystyle \Sigma (n)=k_{n}}$.

Verwandte Funktionen

σ(n): Zusammenhängende Kette von Einsen

Eine ebenfalls nicht berechenbare Funktion ergibt sich, wenn die zusätzliche Beschränkung eingeführt wird, dass alle Einsen eine zusammenhängende Kette bilden müssen.

Als Bezeichnung dafür hat sich ${\displaystyle \sigma (n)}$ eingebürgert.

Nicht lösbares Problem

Die Bestimmung der fleißigen Biber ist ein Problem, das nicht allgemein (für alle ${\displaystyle n}$) algorithmisch lösbar ist. So ist nicht generell entscheidbar, ob eine gegebene Turingmaschine mit ${\displaystyle n}$ Zuständen tatsächlich eine maximale Anzahl von Einsen auf das Band schreibt. Für einzelne Turingmaschinen geringer Komplexität ist das allerdings möglich. Also ist die Menge der Werte von ${\displaystyle \Sigma (n)}$ weder entscheidbar noch rekursiv aufzählbar, obwohl ${\displaystyle \Sigma (n)}$ wohldefiniert ist. Da auch das Komplement dieser Menge nicht rekursiv aufzählbar ist, wird diese Menge gerne als Beispiel für eine Sprache gewählt, die nicht in der ersten Stufe der arithmetischen Hierarchie liegt.

Wegen dieser Eigenschaften der Wertemenge ist die Funktion ${\displaystyle \Sigma }$ nicht berechenbar. Man kann außerdem zeigen, dass ihr asymptotisches Wachstum stärker ist als das jeder berechenbaren Funktion.

Fleißiger Biber mit 1 Zustand

Der Automat ist definiert durch ${\displaystyle M}$:

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

wobei

${\displaystyle \{q_{0},q_{f}\}}$	die möglichen Zustände beschreibt,
${\displaystyle \{\}}$	die Menge der Eingabesymbole auf dem Band ist (hier leer),
${\displaystyle \{0,1\}}$	die möglichen Symbole auf dem Band beschreibt (hier binär),
${\displaystyle \delta }$	die partielle Überführungsfunktion darstellt,
${\displaystyle q_{0},0}$	die Startbedingungen sind,
${\displaystyle \{q_{f}\}}$	den Zustand der Haltebedingung darstellt.

Die partielle Überführungsfunktion ${\displaystyle \delta }$ ist wie folgt definiert (Der Zustand ${\displaystyle q_{0}}$ mit gelesenem Symbol ${\displaystyle 1}$ braucht hier nicht definiert werden, da er nie eingenommen wird):

Weitere Informationen , ...

aktueller Zustand	Symbol				neuer Zustand	Kopf- richtung
	geles.		schr.
${\displaystyle q_{0}}$	0	→		1	${\displaystyle q_{f}}$	Halt

Schließen

${\displaystyle M}$ durchläuft folgende Zustände, wobei die aktuelle Kopfposition fett gedruckt ist:

Weitere Informationen , ...

Schritt	Zust.	Band
1	${\displaystyle q_{0}}$	00
Halt	${\displaystyle q_{f}}$	10

Schließen

Fleißiger Biber mit 2 Zuständen

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

Die Überführungsfunktion ${\displaystyle \delta }$ ist wie folgt definiert:

Weitere Informationen , ...

aktueller Zustand	Symbol				neuer Zustand	Kopf- richtung
	geles.		schr.
${\displaystyle q_{0}}$	0	→		1	${\displaystyle q_{1}}$	R→
	1	→		1	${\displaystyle q_{1}}$	←L
${\displaystyle q_{1}}$	0	→		1	${\displaystyle q_{0}}$	←L
	1	→		1	${\displaystyle q_{f}}$	Halt

Schließen

${\displaystyle M}$ durchläuft folgende Zustände, wobei die aktuelle Kopfposition fett gedruckt ist:

Weitere Informationen , ...

Schritt	Zust.	Band		Schritt	Zust.	Band
1	${\displaystyle q_{0}}$	…0000000…		5	${\displaystyle q_{0}}$	…0011100…
2	${\displaystyle q_{1}}$	…0001000…		6	${\displaystyle q_{1}}$	…0111100…
3	${\displaystyle q_{0}}$	…0001100…		Halt	${\displaystyle q_{f}}$	…0111100…
4	${\displaystyle q_{1}}$	…0001100…

Schließen

Fleißiger Biber mit 3 Zuständen

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

Die Überführungsfunktion ${\displaystyle \delta }$ ist wie folgt definiert:

Weitere Informationen , ...

aktueller Zustand	Symbol				neuer Zustand	Kopf- richtung
	geles.		schr.
${\displaystyle q_{0}}$	0	→		1	${\displaystyle q_{1}}$	R→
	1	→		1	${\displaystyle q_{f}}$	Halt
${\displaystyle q_{1}}$	0	→		0	${\displaystyle q_{2}}$	R→
	1	→		1	${\displaystyle q_{1}}$	R→
${\displaystyle q_{2}}$	0	→		1	${\displaystyle q_{2}}$	←L
	1	→		1	${\displaystyle q_{0}}$	←L

Schließen

${\displaystyle M}$ durchläuft folgende Zustände, wobei die aktuelle Kopfposition fett gedruckt ist:

Weitere Informationen , ...

Schritt	Zust.	Band		Schritt	Zust.	Band		Schritt	Zust.	Band
1	${\displaystyle q_{0}}$	000000		6	${\displaystyle q_{0}}$	011100		11	${\displaystyle q_{2}}$	111100
2	${\displaystyle q_{1}}$	010000		7	${\displaystyle q_{1}}$	111100		12	${\displaystyle q_{2}}$	111101
3	${\displaystyle q_{2}}$	010000		8	${\displaystyle q_{1}}$	111100		13	${\displaystyle q_{2}}$	111111
4	${\displaystyle q_{2}}$	010100		9	${\displaystyle q_{1}}$	111100		14	${\displaystyle q_{0}}$	111111
5	${\displaystyle q_{2}}$	011100		10	${\displaystyle q_{1}}$	111100		Halt	${\displaystyle q_{f}}$	111111

Schließen

Fleißiger Biber mit 4 Zuständen

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

Die Überführungsfunktion ${\displaystyle \delta }$ ist wie folgt definiert:^[12]

Weitere Informationen , ...

aktueller Zustand	Symbol				neuer Zustand	Kopf- richtung
	geles.		schr.
${\displaystyle q_{0}}$	0	→		1	${\displaystyle q_{1}}$	R→
	1	→		1	${\displaystyle q_{1}}$	←L
${\displaystyle q_{1}}$	0	→		1	${\displaystyle q_{0}}$	←L
	1	→		0	${\displaystyle q_{2}}$	←L
${\displaystyle q_{2}}$	0	→		1	${\displaystyle q_{f}}$	Halt
	1	→		1	${\displaystyle q_{3}}$	←L
${\displaystyle q_{3}}$	0	→		1	${\displaystyle q_{3}}$	R→
	1	→		0	${\displaystyle q_{0}}$	R→

Schließen

${\displaystyle M}$ erreicht den Halt-Zustand nach 107 Schritten und mit Bandinhalt „…10111111111111…“.

Fleißiger Biber mit 5 Zuständen

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

Die Überführungsfunktion ${\displaystyle \delta }$ ist wie folgt definiert:^[12]

Weitere Informationen , ...

aktueller Zustand	Symbol				neuer Zustand	Kopf- richtung
	geles.		schr.
${\displaystyle q_{0}}$	0	→		1	${\displaystyle q_{1}}$	R→
	1	→		1	${\displaystyle q_{2}}$	←L
${\displaystyle q_{1}}$	0	→		0	${\displaystyle q_{0}}$	←L
	1	→		0	${\displaystyle q_{3}}$	←L
${\displaystyle q_{2}}$	0	→		1	${\displaystyle q_{0}}$	←L
	1	→		1	${\displaystyle q_{f}}$	Halt
${\displaystyle q_{3}}$	0	→		1	${\displaystyle q_{1}}$	←L
	1	→		1	${\displaystyle q_{4}}$	R→
${\displaystyle q_{4}}$	0	→		0	${\displaystyle q_{3}}$	R→
	1	→		0	${\displaystyle q_{1}}$	R→

Schließen