Radonsche Funktion/ Fleißiger Biber

Moin moin,

Kann mir jemand auf Abiturniveau erklären, warum der fleißige Biber nicht berechenbar ist bzw warum die Radonsche Funktion nicht berechenbar ist ?
Das ganze Zeugs auf Wikipedia hat mir nur noch weiter verwirrt.

Hier die Beschreibung aus Wikipedia:

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 Kette von Einsen maximaler Länge schreibt. **Für einzelne Turingmaschinen geringer Komplexität ist das allerdings möglich. Also ist die Menge der Werte von Σ(n) weder entscheidbar, noch rekursiv aufzählbar, obwohl Σ(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 Σ nicht berechenbar. Man kann außerdem zeigen, dass ihr asymptotisches Wachstum stärker ist als das jeder berechenbaren Funktion.**

Beim fettgeschriebenen Teil hörts bei mir mit der Logik auf.
Kann jemand versuchen mir das zu erklären und/oder mir ein Beispiel zu geben ?

Danke !

Weihnachtliche Grüße

Lusches

Christoph

Der Beweis, dass Σ(n) nicht berechenbar ist, ist ein Beweis durch Widerspruch. Der Beweis ist ziemlich technisch, würde ich sagen, und den meisten Informatikern genügt wohl "das ist offensichtlich nicht berechenbar".

Für den den Beweis nimmst du erst einmal an, dass Σ(n) berechenbar ist, und zeigst dann, dass diese Annahme unweigerlich zu einem Widerspruch führen muss. Daraus folgt, dass die Annahme falsch war, und Σ(n) nicht berechenbar ist.

Der grobe Beweis sieht so aus:
1. Annehmen, dass Σ(n) berechenbar ist.
2. Turingmaschine M hernehmen, die Σ(n) berechnet.
3. Maschine M so umändern, dass sie auf einem leeren Band starten kann und Σ(n) viele 1en schreibt.
4. Feststellen, dass die umgeänderte Maschine nur n-2 Zustände braucht, um Σ(n) viele 1en zu schreiben.
5. Daraus eine neue Maschine mit n Zuständen bauen, die Σ(n)+1 berechnet.
6. Widerspruch zur Definition von Σ(n)!

Schritt 1: Angenommen Σ(n) ist berechenbar.

Schritt 2: Das heißt, es gibt eine Turingmaschine M mit k Zuständen, die n als Eingabe nimmt und Σ(n) berechnet. Wir können annehmen, dass diese Turingmaschine ihren Input und Output als Folge von 1en sieht. Die Turingmaschine M erwartet also als Eingabe eine Folge von n hintereinanderstehenden 1en auf dem Band und schreibt Σ(n) viele 1en aufs Band.

Schritt 3: In der Definition von Σ ist nur von Turingmaschinen die Rede, die auf einem leeren Band starten. Unser M erwartet aber schon n viele 1en auf dem Band, dass müssen wir erstmal reparieren. Um n viele 1en auf ein leeres Band zu schreiben, genügen mit Sicherheit (c * log n) Zustände, wobei c eine Konstante ist. Weil das Argument dafür etwas unnötig lang ist, hab ich das unten in die Fußnote (*) geschrieben.

Insgesamt haben wir jetzt also eine Konstante c gefunden und eine Methode, um mit nur (c * log n) Zuständen die Zahl n aufs Band zu schreiben. Jetzt können wir diese Methode an unser M von oben dranschrauben und bekommen für jedes n eine neue Maschine N(n) mit (k + c * log n) Zuständen. Die Maschine N(n) schreibt Σ(n) viele 1en aufs Band und terminiert dann.

Wichtig ist, dass wir jetzt nicht mehr nur eine Maschine haben, sondern für jedes n haben wir eine andere Maschine N(n).

Schritt 4: Der Term k + c * log n wächst langsamer als n, also gibt es ein x, sodass k + c * log x < x - 1 ist. Das bedeutet, dass die Maschine N(x) mindestens 2 Zustände weniger als x Zustände hat.

Schritt 5: Nun bringt N(x) es aber fertig, Σ(x) viele 1en aufs Band zu schreiben, und das mit höchstens x - 2 Zuständen. Jetzt hält uns nichts davon ab, N(x) um zwei Zustände zu erweitern. Mit diesen zwei Zuständen können wir genau eine weitere 1 aufs Band schreiben, nachdem N(x) fertig ist. Die Maschine, die wir jetzt haben, hat höchstens x Zustände und schreibt Σ(x) + 1 viele 1en aufs Band.

Schritt 6: Das ist nun ein direkter Widerspruch zur Definition von Σ(x): Eine Maschine mit höchstens x Zuständen kann höchstens Σ(x) viele 1en aufs Band schreiben.

Also war unsere Annahme in Schritt 1 falsch und Σ kann nicht berechenbar sein.

(Dieser Beweis erhebt keinen Anspruch auf Korrektheit. Es ist schon eine Weile her, dass ich diese Funktion betrachtet hab.)

(*)
Das liegt daran, dass man die Operation "Zahl der 1er auf dem Band verdoppeln" mit einer festen Anzahl Zuständen realisieren kann, egal wieviele 1er schon auf dem Band stehen. Wichtig dabei ist, dass die 1er auf dem Band ein zusammenhängendes Segment bilden, das Band also so aussieht:

...00000011111111111111....11111110000000...
         ^

Die Turingmaschine steht auf der ersten 1, rechts kommen endlich viele 1en und danach 0en, nach links kommen nur 0en. In so einer Situation kann man die Operation "Zahl der 1er auf dem Band verdoppeln" mit endlich vielen Zuständen implementieren, egal wie viele 1er es schon gibt. Das kann man auch so sehen, dass die Funktion $$n \mapsto 2n$$ berechenbar ist, und es deswegen schon eine Turingmaschine geben muss, die das macht.

Angenommen, man braucht c Zustände, um die "1er-verdoppel-Operation" zu bauen.

Wenn du jetzt eine Maschine nimmst, die im ersten Schritt eine einzige 1 aufs Band setzt, und dann diese "1er-verdoppel"-Aktionen (log n) mal ausführt (das ist der 2er-Logarithmus), dann hast du danach n viele 1er auf dem Band. Wir können der Einfachheit halber annehmen, dass n eine 2er-Potenz ist, dann ist log n immer eine ganze Zahl.

Das war jetzt ein bisschen unpräzise. In Wirklichkeit braucht man nicht (c * log n) Zustände, sondern (c * log n + d), mit einer weiteren Konstanten d (denn die allererste 1 zu schreiben kostet auch Zustände). Aber es ist nicht wirklich tragisch hier, diese Konstante zu ignorieren, die ändert nichts an der Argumentation.

Christoph

Die Argumentation oben zeigt "direkt", dass Σ nicht berechenbar ist. Nachdem ich nochmal drüber nachgedacht habe, ist mir klar geworden, dass es auch kürzer geht: Man könnte Σ aufs Halteproblem zurückführen, das bekanntermaßen nicht entscheidbar ist (darüber gibt's sehr viele Artikel). Wenn dir das Halteproblem nichts sagt, ist die Argumentation im letzten Posting vielleicht trotzdem leichter einzusehen.

"Aufs Halteproblem zurückführen" bedeutet hier folgendes: Angenommen Σ ist berechenbar, dann können wir für beliebige Turingmaschinen M entscheiden, ob sie terminiert oder nicht.

Angenommen Σ ist berechenbar. Sei M eine beliebige Turingmaschine. Betrachte die Turingmaschine N, die M simuliert und in jedem Simulationsschritt eine 1 aufs Band schreibt (und zwar so, dass die Simulation dadurch nicht gestört wird).

Nachdem die Maschine N die Maschine M für n Zeitschritte simuliert hat, stehen mindestens n viele 1en auf dem Band, nach Konstruktion von N. Außerdem terminiert N genau dann, wenn M terminiert.

Angenommen, N hat k Zustände. Dann kann N maximal Σ(k) viele 1en aufs Band geschrieben haben, wenn es terminiert. Das ist die Definition von Σ(k).

Wenn Σ(k) jetzt berechenbar wäre, könnten wir einfach N solange laufen lassen, bis mehr als Σ(k) viele 1en auf dem Band stehen, und zwar so, dass die Maschine M für mehr als Σ(k) Schritte simuliert wurde. Dann steht wegen der Definition von Σ(k) fest, dass N nicht mehr terminieren wird.

Denn würde N terminieren, dürften am Ende maximal Σ(k) viele 1en auf dem Band sein. Die 1en, die die Simulationsschritte zählen, werden aber nie weniger. Wenn N also schon Σ(k) viele Simulationsschritte durchgeführt hat, ist klar, dass es nicht mehr terminieren kann.

Wenn N nicht terminiert, terminiert auch M nicht. Wenn Σ berechenbar ist, könnten wir also in endlicher Zeit entscheiden, ob eine beliebige Turingmaschine M terminiert oder nicht. Das ist aber unmöglich, also ist Σ nicht berechenbar.