Fandom

VroniPlag Wiki

Quelle:Wl/Wikipedia Ackermannfunktion 2012

< Quelle:Wl

31.268Seiten 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.

Angaben zur Quelle [Bearbeiten]

Titel    Ackermannfunktion
Verlag    (Wikipedia)
Datum    23. Dezember 2012
URL    http://de.wikipedia.org/w/index.php?title=Ackermannfunktion&oldid=111379176

Literaturverz.   

nein
Fußnoten    nein
Fragmente    2


Fragmente der Quelle:
[1.] Analyse:Wl/Fragment 091 19 - Diskussion
Zuletzt bearbeitet: 2014-07-06 19:35:55 Schumann
Fragment, KeineWertung, SMWFragment, Schutzlevel, Wikipedia Ackermannfunktion 2012, Wl, ZuSichten

Typus
KeineWertung
Bearbeiter
Schumann
Gesichtet
No.png
Untersuchte Arbeit:
Seite: 91, Zeilen: re.Sp. 19-32
Quelle: Wikipedia Ackermannfunktion 2012
Seite(n): 0, Zeilen: 0
Zunächst entstand der Begriff der primitiv rekursiven Funktion. Vereinfacht bedeutet dies, dass sich jede durch einen Computer berechenbare Funktion aus einigen wenigen, sehr einfachen Regeln zusammensetzen lässt, und dass sich die Dauer der Berechnung im Voraus abschätzen lässt.

Dies trifft auf in der Tat auf nahezu alle in der Praxis vorkommenden Funktionen zu. Noch im Jahre 1926 vermutete David Hilbert (Abb. 5.4), dass jede berechenbare Funktion primitiv-rekursiv sei. Allerdings konnte Ackermann im gleichen Jahr eine Funktion konstruieren, die diese Vermutung widerlegte, und veröffentlichte sie 1928. Ihm zu Ehren wird diese Funktion heute Ackermannfunktion genannt. Sie kann von einem Computer in endlicher Zeit ausgewertet werden, ist aber nicht primitiv-rekursiv.

Entstehungsgeschichte

1926 vermutete David Hilbert, dass jede berechenbare Funktion primitiv-rekursiv sei. Vereinfacht bedeutet dies, dass sich jede durch einen Computer berechenbare Funktion aus einigen wenigen, sehr einfachen Regeln zusammensetzen lässt und dass sich die Dauer der Berechnung im Voraus abschätzen lässt. Dies trifft auf nahezu alle in der Praxis vorkommenden Funktionen zu.

Ebenfalls 1926 konstruierte Ackermann eine Funktion, die diese Vermutung widerlegt, und veröffentlichte sie 1928. Ihm zu Ehren wird diese Funktion heute Ackermannfunktion genannt. Sie kann von einem Computer in endlicher Zeit ausgewertet werden, ist aber nicht primitiv-rekursiv.

Anmerkungen
Sichter

[2.] Analyse:Wl/Fragment 092 18 - Diskussion
Zuletzt bearbeitet: 2014-07-06 20:04:02 Schumann
Fragment, KeineWertung, SMWFragment, Schutzlevel, Wikipedia Ackermannfunktion 2012, Wl, ZuSichten

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