Fandom

VroniPlag Wiki

Analyse:Wl/Fragment 092 18

31.385Seiten in
diesem Wiki
Seite hinzufügen
Diskussion0

Störung durch Adblocker erkannt!


Wikia ist eine gebührenfreie Seite, die sich durch Werbung finanziert. Benutzer, die Adblocker einsetzen, haben eine modifizierte Ansicht der Seite.

Wikia ist nicht verfügbar, wenn du weitere Modifikationen in dem Adblocker-Programm gemacht hast. Wenn du sie entfernst, dann wird die Seite ohne Probleme geladen.


Typus
KeineWertung
Bearbeiter
Schumann
Gesichtet
No.png
Untersuchte Arbeit:
Seite: 92, Zeilen: re.Sp. 18-33, li.Sp. 24-29
Quelle: Wikipedia Ackermannfunktion 2012
Seite(n): 0, Zeilen: 0
Aus dieser Definition ist nicht sofort ersichtlich, dass die Funktion für alle nicht negativen, ganzzahligen n und m definiert ist. Das ergibt sich jedoch daraus, dass in jedem Schritt, entweder m verringert oder aber m erhöht und n verringert wird. Jedes Mal, wenn m null erreicht, wird n verringert, also muss auch n irgendwann null erreichen, und dann liefert die erste Zeile der Definition den Funktionswert. Zu beachten ist allerdings, dass es bei einer Verringerung von m keine obere Schranke für das Wachstum von n in den folgenden Funktionsaufrufen gibt. Das Besondere an der Ackermannfunktion ist nun, dass sie stärker wächst als jede primitiv-rekursive Funktion. Hierauf beruht auch der Beweis von Ackermann, dass diese Funktion nicht primitiv-rekursiv ist.

Die folgende Tabelle zeigt einige Funktionswerte für kleine Werte von n und m. Die nicht vollständig ausgerechneten Werte sind zu groß, um sie dezimal darzustellen:

[Tabelle]

Diese Entdeckung von Ackermann führte zu einer Erweiterung der Definition der primitiv-rekursiven Funktionen, indem man eine weitere Konstruktionsregel, die sogenannte μ‑Rekursion, einführte, und so die Klasse der μ‑rekursiven Funktionen erhielt, die die Klasse der primitiv-rekursiven Funktionen echt umfasst.

Aus dieser Definition ist nicht sofort ersichtlich, dass die Funktion für alle nicht negativen, ganzzahligen n und m definiert ist. Das ergibt sich jedoch daraus, dass in jedem Schritt, entweder m verringert oder aber m erhöht und n verringert wird. Jedes Mal, wenn m Null erreicht, wird n verringert, also muss auch n irgendwann Null erreichen, und dann liefert die erste Zeile der Definition den Funktionswert. Zu beachten ist allerdings, dass es bei einer Verringerung von n keine obere Schranke für das Wachstum von m in den folgenden Funktionsaufrufen gibt.

[...]

Führt man auf der Klasse der primitiv-rekursiven Funktionen eine weitere Konstruktionsregel, die sogenannte µ-Rekursion, ein, erhält man eine größere Klasse ebenfalls berechenbarer Funktionen, die die Ackermannfunktion enthält. Man nimmt an, dass diese Klasse der µ-rekursiven Funktionen der Klasse der intuitiv berechenbaren Funktionen entspricht (Church'sche These).

Beweis

Der Beweis, dass die Ackermannfunktion berechenbar ist, aber nicht primitiv-rekursiv, nutzt im Wesentlichen aus, dass die Ackermannfunktion stärker wächst als jede primitiv-rekursive Funktion.

[...]

Wertetabelle

Die folgende Tabelle zeigt einige Funktionswerte für kleine Werte von n und m. Die nicht vollständig ausgerechneten Werte sind zu groß, um sie dezimal darzustellen.

[Tabelle]

Anmerkungen
Sichter

Auch bei Fandom

Zufälliges Wiki