Home -> Themen -> Sigma-Funktion


Turing-Werkstatt

Theoretische Informatik am PC


O.Pletsch 1862 Sigma-Funktion

Definition
Die von T.Rado 19621 angegebene Sigma-Funktion, Sigma : N -> N, bezieht sich auf das Problem der Suche nach dem emsigen Biber. Sigma(n) ist festgelegt als die Anzahl von Strichen, die der emsigste Biber mit n Zuständen erzeugen kann.
1 Rado,T. : On Non-Countable Functions.
Bell.Syst.Tec.J.41 S.877-884,(1962)

Einige Werte
Sigma(1) = 1 ;
Sigma(2) = 4 ; biber2.tm liefert 4 Striche.
Sigma(3) = 6 ; biber3.tm 1 liefert 6 Striche.
Sigma(4) = 13 ; biber4.tm, 2 liefert 13 Striche.
Sigma(5) > 4098 ; buntmarx.tm von Heiner Marxen und Jürgen Buntrock liefert 4098 Striche.
1 T.Lin, ein Schüler von T.Rado bewies 1962, dass biber3.tm am produktivsten ist.
2 B.Weimann lieferte 1972 den Nachweis, dass Biber4.tm die maximale Anzahl von Strichen produziert.

Sigma wächst streng monoton
Aus einem emsigen Biber M mit n Zuständen, der Sigma(n) Striche produziert, kann man leicht durch Hinzufügen eines weiteren Zustands und durch Abändern des Stopp-Befehls eine neue Maschine M' mit n+1 Zuständen erzeugen, die einen Strich mehr als M erzeugt.
M' zeigt :   Sigma(n) < Sigma(n)+1 = Strichzahl von M' <  Sigma(n+1)

Sigma ist nicht berechenbar
Der Nachweis dieser Behauptung wird indirekt geführt :
Wir machen die Annahme, dass Sigma berechenbar ist, d.h. es gibt eine Turing-Maschine M über {' ','I'}, die Sigma berechnet. Die Anzahl der Zustände von M sei j. Wir können mit Hilfe von M zu jeder natürlichen Zahl n eine neue Maschine M* mit n+k Zuständen (wobei k=j+8) konstruieren, die genauso viele Striche erzeugt wie ein fleißiger Biber mit 2n Zuständen.
Daraus folgt :
    Sigma(2n) = Strichzahl von M* < Sigma(n+k) für alle natürlichen Zahlen n.
Diese Ungleichung verträgt sich nicht mit der Monotonie von Sigma, denn für n = 2k ergibt sich nun
    Sigma(4k) < Sigma(2k+k) = Sigma(3k). Die Annahme, daß Sigma berechenbar ist, muß falsch sein.
Wir erhalten M*, indem wir drei Maschinen hintereinandersetzen
M1 : Startet bei leerem Band und produziert n Striche,
M1 hat n Zustände,
M2 : Verdoppelt die Strichzahl auf dem Band,
M2 kann mit 8 Zuständen auskommen ( M2=mal2.tm),
M3 : Ist die Maschine M zur Berechnung von Sigma,
M3 habe j Zustände.
M* hat dann n + (8 + j) = n + k Zustände

Sigma-Funktion ist nicht berechenbar