IIm18-Kreativaufgabe4

Aus ProgrammingWiki

Rado-Funktion

Der Fleißige Biber ist eine Turingmaschine, die $n$ Zustände plus einen Haltezustand einnehmen kann und dabei maximal viele Einsen auf das Band schreibt. Zudem unterliegt diese Turingmaschine einigen besonderen Regeln.

• Der Lesekopf der Turingmaschine muss sich immer nach rechts oder links bewegen. Das verharren auf einer Position ist nicht gestattet.
• Es gibt keine leeren Felder auf dem Eingabeband. Alle Felder sind zu Beginn mit dem Bandvorbelegungszeichen belegt z.B. $\$ $ oder 0.
• Die Turingmaschine muss nach einer endlichen Anzahl von Schritten im Haltezustand stoppen und darf nicht in eine Endlosschleife geraten oder Crashen.
• Die Aufgabe der Turingmaschine ist es die maximale Anzahl von Einsen mit der ihr zur Verfügung stehenden n Zustände auf das Band zu schreiben.
• Alle Turingmaschinen die nicht halten, können zwar mehr Einsen auf das Band schreiben, sind aber laut Definition keine fleißigen Bieber.

Die Fleißige Bieber Funktion oder auch Rado-Funktion ist die Funktion, die über der Anzahl der $k_n$ Einsen, die ein Fleißiger Biber mit $n$ Zuständen schreibt wie folgt definiert.

$ \Sigma(n) = k_n$

Zudem weist die Rado-Funktion folgende Eigenschaften auf:

$\Sigma(n)< \Sigma(n+1)$

Diese Eigenschaft besagt, dass es garantiert eine Fleißiger Biber Turingmaschine mit n+1 Zuständen gibt, die mehr Einsen auf das Band schreiben kann als jede Turingmaschine mit $n$ Zuständen.

$ f(n) \leq \Sigma(n+k)$

$ f(n)$ ist eine Turing Berechenbare Funktion und repräsentiert eine Turingmaschine, die unter der Verwendung von $n$ Zuständen eine beliebige Anzahl von Einsen auf das Band schreibt. Da diese Funktion Turing Berechenbar ist, weiß man mit Sicherheit, dass für diese Funktion eine Turingmaschine existiert. Die Eigenschaft der Rado-Funktion besagt, dass die Radofunktion mit $n+k$ Zuständen, wobei $n$ die Anzahl der Zustände ist, welche von der Turingmaschine verwendet werden und $k$ eine beliebige Konstante ist, mindestens so groß ist die der Wert der Funktion $f(n)$.

Bsp: $n = 2$

$k = 0$

Unter Verwendung von 2 Zuständen wird jede Turingmaschine, die beliebig viele, also $f(n)$ Einsen auf das Eingabeband schreibt höchstens so viele Einsen auf auf das Band schreiben wie der Funktionswert von $\Sigma(n)$.

$f(2) \leq \Sigma(2+0)$

Eine Turingmaschine, die f(2) berechnet schreibt höchstens 4 Einsen auf das Eingabeband schreiben.

Das Problem was jedoch existiert, ist, dass die Funktion $\Sigma(n)$ nicht berechenbar ist. Wir können also nicht berechnen, wie viele Einsen von einem Fleißigen Biber mit $n$ Zuständen, maximal auf das Band der Turingmaschine geschrieben werden können.

Die Problematik besteht darin, dass sich nicht sagen lässt, welche Turingmaschine mit $n$ Zuständen Stoppt und welche nach gewisser Zeit in eine Endlosschleife gerät. Die Anzahl der Turingmaschinen mit $n$ Zuständen kann natürlich durch die Berechnung der Anzahl aller möglichen Kombinationen von Zuständsübergängen angegeben werden. Jedoch ist durch die exponentiell wachsende Anzahl von möglichen Turingmaschinen, das ermitteln, ob die Turingmaschine Stoppt oder nicht nur für $n\leq 4$ eindeutig möglich. Zwar ist es auch noch bei $n=5$ möglich, jedoch kann für 40 Turingmaschinen mit 5 Zuständen nicht eindeutig entschieden werden, ob diese in endlicher Zeit stoppen oder in einer Endlosschleife enden.

Dass die Funktion $\Sigma(n)$ nicht Turing berechenbar ist, kann auch indirekt über ihre Eigenschaften bewiesen werden.

Anzahl der Turingmaschinen mit $n$ Zuständen:

$(2 * 2 * (n + 1))^{2n}$

für n = 5 Zustände lassen sich somit bereits $24^{10}$ verschiedene Turingmaschinen

weitere Betrachtungen

Wenn $ \Sigma(n) $ berechenbar wäre, dann könnte man $\Sigma $ auch als Aufzählprozedur der Menge aller $k_n$ ($K$) verstehen.

ABER: Wie schon beschrieben ist die Menge aller $k_n$ weder entscheidbar, noch aufzählbar. Warum das so ist soll im folgenden möglichst nachvollziehbar ergründet werden.

nicht-Entscheidbarkeit der Menge aller $k_n$: Es existiert keine charakteristische Funktion $\Chi$, die für ein gegebenes k entscheiden kann, ob dieses zur Menge aller $k_n$ gehört oder nicht.

Die Aufzählbarkeit der Menge aller $k_n$ ergäbe sich hingegen aus deren Abzählbarkeit und aus der Berechenbarkeit von $\Sigma$.

Um zu beweisen, dass die Menge aller $k_n$ abzählbar bzw abzählbar unendlich ist, muss gezeigt werden, dass es eine mindestens surjektive Abbildung der natürlichen Zahlen auf die Menge aller $k_n$ gibt: $\mathbb{N}\to K$

Um zu beweisen, dass $\Sigma$ nicht berechenbar ist verwenden wir einen Widerspruchsbeweis:

z.z.: $\Sigma$ ist nicht berechenbar

Annahme: $\Sigma$ ist berechenbar

Eigenschaft 1: $\Sigma(z) < \Sigma(z + 1)$

Eigenschaft 2: für alle n gilt: $f(n)\le\Sigma(n + z)$

$f(n)=\Sigma(2n)$

nach Eigenschaft 2:

$\Sigma(2n)\le\Sigma(n+z)$ | $n=z+1$

$\Sigma(2*(z+1))\le \Sigma(z+1+z)$

$\Sigma(2z+2)\le \Sigma(2z+1)$

nach Eigenschaft 1:

$\Sigma(2z+2)>\Sigma(2z+1)$

WIDERSPRUCH!!