Die Webseiten der Fachschaft Informatik am ERG Saalfeld

Fleißiger-Biber-Funktion / Rado-Funktion - die Grenzen der Berechenbarkeit

Fleißige Biber sind spezielle Turingmaschinen, die möglichst viele Einsen auf das Band schreiben und die nach einer endlichen Anzahl Rechenschritte den Halt-Zustand einnehmen (also anhalten).

Was ist eine "Fleißiger-Biber-Funktion"?

Die Rado-Funktion (auch Fleißiger-Biber-Funktion) gibt die maximale Anzahl der Einsen an, die ein fleißiger Biber mit einer gegebenen Anzahl von Zuständen schreiben kann. Beides wurde erstmals 1962 vom ungarischen Mathematiker Tibor Rado betrachtet.

Definition: Uber die Anzahl k_n von Einsen, die ein fleißiger Biber mit n Zustanden schreibt, ist der Wert der Rado-Funktion an der Stelle n definiert: ∑(n) = k_n

Warum ist das so wichtig?

⇒ Nicht lösbares Problem

Die Bestimmung der fleißigen Biber ist ein Problem, das nicht allgemein algorithmisch lösbar ist.

So ist nicht generell entscheidbar, ob eine gegebene Turingmaschine mit 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 der Summe (n) weder entscheidbar, noch rekursiv aufzählbar, obwohl die Summe (n) wohldefiniert ist.

Wegen dieser Eigenschaften der Wertemenge ist die Rado-Funktion nicht berechenbar.

Man kann außerdem zeigen, dass ihr asymptotisches Wachstum stärker ist als das jeder berechenbaren Funktion.

Beispiele

Stellen wir uns jetzt eine Turing-Maschine vor, die folgendes Problem lösen soll: Schreibe maximal viele Einsen auf das Band und stoppe dann.

ein Zustand, also n = 1

Hätte diese Maschine nur einen Zustand, könnte sie nur eine einzige Eins schreiben. Dieser Zustand wäre zum Beispiel: "wenn eine Null auf dem Band steht, schreibe eine Eins, rücke ein Feld nach rechts, halte an". Würde die Maschine wieder in den selben Zustand gehen, statt anzuhalten, würde sie unendlich viele Einsen auf das Band schreiben und niemals anhalten.

Ein fleißiger Biber mit nur einem Zustand kann höchstens einen Strich auf das leere Band drucken. z.B. erledigt dies das folgende Programm:

          0  #  1  S  0
          0  1  1  S  0

Im Simulator sieht die Ausgabe dann so aus:

zwei Zustände, also n = 2

Ein fleißiger Biber mit zwei Zuständen kann höchstens vier Striche auf das leere Band drucken. z.B. erledigt dies das folgende Programm:

          0  1  1  L  1
          0  #  1  R  1
          1  1  1  S  0
          1  #  1  L  0

Im Simulator sieht die Ausgabe dann so aus:

drei Zustände, also n = 3

z.B. erledigt dies das folgende Programm:

          0  1  1  S  0
          0  #  1  R  1
          1  1  1  R  1
          1  #  #  R  2
          2  1  1  L  0
          2  #  1  L  2

Aufgaben

Teste die Fleißigen Biber für die Zustände 1,2 und 3.
Überprüfe, ob es sich bei 2 Zuständen ebenfalls um einen fleißigen Biber handelt, wenn man die Kopfbewegung in der ersten Zeile in R - für Rechts ändert. Wenn nicht, wie viele Striche/Einsen werden geschrieben?
Wie viele Striche/Einsen schreibt der Fleißige Biber für 3 Zustände maximal auf das Band?

Weblinks

zurück