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