Post on 18-Sep-2018
transcript
Theoretische Informatik
Ackermann-Funktion
Ali Eyerta
Ackermannfunktion – Theoretische Informatik Verfasser: Ali Eyerta
Inhalt
Entstehungsgeschichte Bedeutung in der Theoretischen Informatik Ackermanns Idee Ackermann-Funktion Anwendungen
Benchmark für rekursive Aufrufe Implementation Wertetabelle Sonstiges
Funktionswert ack(4,2) Die Busy Beaver Funktion
Ende
Ackermannfunktion – Theoretische Informatik Verfasser: Ali Eyerta
Entstehungsgeschichte
1926 vermutet David Hilbert dass jede berechenbare Funktion primitiv rekursiv sei Einfach ausgedrückt: Jede durch einen Computer berechenbare
Funktion aus wenigen einfachen Regeln zusammensetzen lassen und die Dauer der Berechnung sich im Voraus abschätzen lässt.
Dies trifft auf nahezu alle in der Praxis vorkommenden Funktionen zu
1928 veröffentlich Wilhelm Ackermann eine Funktion die diese Vermutung widerlegt Diese Funktion kann von einem Computer berechnet werden ist
aber nicht primitiv rekursiv. 1955 konstruierte Rózsa Péter eine vereinfachte
Version, die die gleichen Eigenschaften besitzt
Ackermannfunktion – Theoretische Informatik Verfasser: Ali Eyerta
Bedeutung in der theo. Informatik
Suche nach Grenzen von Computern: berechenbare Funktionen dies sind Funktionen mit gegebenen Algorithmen, die
eine Turingmaschine berechnen kann
Problem: entscheiden ob eine Funktion berechenbar ist oder nicht. Algorithmus gefunden -> berechenbar Algorithmus nicht gefunden -> ungewiss
Entweder nicht berechenbar oder es gibt einen Algorithmus aber nicht gefunden
Ackermannfunktion – Theoretische Informatik Verfasser: Ali Eyerta
Bedeutung in der theo. Informatik
Alternative Definitionen werden gesucht Erster Ansatz: primitiv rekursive Funktionen
Sind Funktionen die aus wenigen Regeln und einfachen Funktionen zusammensetzen lassen
Vermutung das alle berechenbare Funktionen primitiv Rekursiv sind
Ackermanns Funktion ist berechenbar aber nicht primitiv rekursiv -> Vermutung falsch
Ackermannfunktion – Theoretische Informatik Verfasser: Ali Eyerta
Ackermanns Idee a+b, a*b, a^b,… . a*b ist gerade a+a+…+a , wobei die Variable a, b-mal vorkommt Die Idee: diese Folge als Funktion aufzufassen.
Beispiel: a = 2 und b = 4, Folge: 6, 8, 16, 65536, (mit 65536 Zweien),
Die letzte aufgeführte Zahl ist bereits wesentlich größer als die geschätzte Anzahl der Atome im gesamten Weltall.
Die Ackermannfunktion, ist also eine Funktion, die die folgenden Gleichungen erfüllt:
ack(a,b,0) = a+back(a,b,1) = a*back(a,b,2) = a^b…Ab der vierten Zeile können die Funktionswerte nicht mehr mit herkömmlichen Operatoren formuliert werden; man braucht erweiterte Notationen, wie beispielsweise den Hyper-Operator.
Ackermannfunktion – Theoretische Informatik Verfasser: Ali Eyerta
Definition Ackermann
Definition nach Ackermann (1926)
ack(a,b,0) = a+back(a,0,n+1) = psi(a,n)ack(a,b+1,n+1) = ack(a,ack(a,b,n+1),n)
psi(a,n) eine weitere Funktion, die Ackermann nicht weiter beschrieb. (Sie liefert die Startwerte a + 0, a*0 , a 0,…)
Rózsa Péter definierte 1955 eine einfachere Version der Ackermannfunktion
a(0,m) = m+1a(n+1,0) = a(n,1)a(n+1,m+1) = a(n,a(n+1,m))
Ackermannfunktion – Theoretische Informatik Verfasser: Ali Eyerta
Definition Ackermann
Beispiele:
a(0,1) a(0,1) = 1 + 1 = 2. | die erste Zeile der Definition anwenden
a(1,0)a(1,0) = a(0,1) | die zweite Zeile der Definition anwenden = 1 + 1 = 2 | die erste Zeile der Definition anwenden
a(1,1) = a(0,a(1,0)) | die dritte Zeile der Definition anwenden| a(1,0) wurde vorhin berechnet, jetzt einsetzen
= a(0,2) = 2 + 1 = 3
Wenn man vom Wachstum der Ackermannfunktion spricht, meint man oftmals die Funktion f(n): = ack(n,n,n).
Ackermannfunktion – Theoretische Informatik Verfasser: Ali Eyerta
Anwendungen
Benchmarktests für rekursive Aufrufe in Programmiersprachen
Laufzeitabschätzung bei der Union-Find-Struktur
Ackermannfunktion – Theoretische Informatik Verfasser: Ali Eyerta
Anwendungen : Benchmarktests
Bei Einführung von neuen Compilern, Programmiersprachen und Computern, wird Leistungsfähigkeit überprüft
Ackermannfunktion als Benchmark für rekursive Funktionen Ackermannfunktion besteht im wesentlichen aus
rekursiven Aufrufen
Die Schwierigkeit dabei ist nicht der Funktionswert, sondern Verschachtelungstiefe
Ackermannfunktion – Theoretische Informatik Verfasser: Ali Eyerta
Anwendungen : Benchmarktests
Problem: Stack Overflow Yngve Sundblad benutzte 1971 die Funktion f(n): = a(3,n)
um Programmiersprachen zu vergleichen Um a(3,n) zu berechnen, werden a(3,n) + 12n 2 Aufrufe −
getätigt. 1971 Größe von n=1 Heute mit Java 1.4.2 mit Standardspeichereinstellungen
n=13 Im Laufe der Berechnung viele identische Aufrufe
Intelligenter Compiler speichert diese zwischen 1971 war damit ein mit von 20 möglich
Ackermannfunktion – Theoretische Informatik Verfasser: Ali Eyerta
Implementation
Pseudo Code
function ack(n, m)
if n = 0 return m + 1
else if m = 0 return ack(n - 1, 1)
else return ack(n - 1, ack(n, m - 1))
Ackermannfunktion – Theoretische Informatik Verfasser: Ali Eyerta
Implementation
Prolog
ackermann(0,X,Y) :- X >= 0, !, Y is X + 1.
ackermann(X,0,Z) :- X > 0, !, X1 is X - 1, ackermann(X1,1,Z).ackermann(X,Y,Z) :- X > 0, Y > 0, X1 is X-1, Y1 is Y - 1,
ackermann(X,Y1,W), ackermann(X1,W,Z).
Ackermannfunktion – Theoretische Informatik Verfasser: Ali Eyerta
Wertetabelle
Ackermannfunktion – Theoretische Informatik Verfasser: Ali Eyerta
Sonstiges
Funktionswert a(4,2) Die Funktion Fleißiger Biber
1962 gab Tibor Radó mit der Funktion Fleißiger Biber (busy beaver) eine noch stärker als die Ackermannfunktion (oder jede andere berechenbare Funktion) wachsende Funktion an, die allerdings nicht mehr berechenbar ist.
Ackermannfunktion – Theoretische Informatik Verfasser: Ali Eyerta
ENDE