Die Ackermann-Funktion

Letztmalig dran rumgefummelt: 20.01.12 17:41:08

	Eines der Flagschiffe der Informatik: die Ackermann-Funktion! Jede For-berechenbare Funktion ist total. Jede totale berechenbare Funktion, für die wir mit einem For-Programm eine Abschätzung für die maximale Anzahl von Schleifendurchläufen angeben können, ist ebenfalls For-berechenbar. Es stellt sich die Frage, ob jede totale berechenbare Funktion durch ein For-Programm darstellbar ist.
	1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Literatur 7. Linkliste zum Thema 8. Verwandte Themen
	Klassische algorithmisch lösbare Probleme Logo für die Ackermann-Funktion begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Informatik-Profi-Wissen
	Quellen: Lehr- und Übungsbuch Informatik Band 1 - 5 Seite ??? Technische und Theoretische Informatik  Seite ???
	Wilhelm Friedrich Ackermann (* 29. März 1896 in Schönebecke (Herscheid); † 24. Dezember 1962 in Lüdenscheid) war ein deutscher Mathematiker. Ackermann studierte von 1914-1924 mit Unterbrechungen durch Teilnahme am Ersten Weltkrieg Mathematik, Physik und Philosophie an der Universität Göttingen. Er war ein Schüler von David Hilbert in Göttingen und wurde berühmt durch die nach ihm benannte Ackermann-Funktion, ein Beispiel für eine rekursive Funktion, die jedoch nicht primitiv-rekursiv ist. 1924 promovierte er bei Hilbert mit der Arbeit „Begründung des ‚tertium non datur‘ mittels der Hilbertschen Theorie der Widerspruchsfreiheit“. Danach erhielt er für drei Jahre ein Forschungsstipendium, das ihm einen Aufenthalt in Cambridge ermöglichte. In Göttingen schloss er 1928 den Vorbereitungsdienst für das Lehramt an höheren Schulen ab. Danach war er zunächst ein Jahr an der damaligen Konrad-Schlaun-Oberrealschule in Münster tätig. Von 1929 bis 1948 unterrichtete er am Gymnasium Arnoldinum in Burgsteinfurt, 1935 wurde er dort zum Studienrat befördert. 1948 kehrte er in seine Heimatstadt Lüdenscheid zurück, wo er bis 1961 am Mädchengymnasium unterrichtete. 1957 wurde er dort zum Fachoberstudienrat für Mathematik befördert. Er war korrespondierendes Mitglied der Akademie der Wissenschaften in Göttingen und Honorarprofessor an der Westfälischen Wilhelms-Universität in Münster. Gemeinsam mit David Hilbert verfasste er 1928 das Buch Grundzüge der theoretischen Logik. Außerdem wurde er durch Arbeiten zum Entscheidungsproblem der Prädikatenlogik, zur Widerspruchsfreiheit der elementaren Zahlentheorie und zur Mengenlehre bekannt. Er verstarb unerwartet im Alter von 62 Jahren am 24. Dezember 1962. Noch drei Tage zuvor hielt er an der Westfälischen Wilhelms-Universität in Münster eine Vorlesung über mathematische Grundlagenforschung. Eine Antwort auf die Frage, warum Ackermann nicht die Universitätslaufbahn eingeschlagen hat, gibt Constance Reid: „Hilbert was very opposed to marriage for young scientists anyway. […] Later, when Wilhelm Ackermann, with whom he had worked and collaborated on a book, married, Hilbert was very angry. He refused to do anything more to further Ackermann's career.“ Das Ackermann trotz seiner erhelblichen Unterrichtstätigkeit noch Zeit für mathematische Arbeiten gefunden hatte, ist beeindruckend. Beispielsweise unterrichtete er im Sommerhalbjahr 1929 am Arnoldinum 26 Wochenstunden und war dort zeitweise sogar der einzige Mathematiklehrer. Im Nachruf des Arnoldinums heißt es: „Oberstudienrat Dr. Ackermann war aber nicht nur ein allseits geschätzter und beliebter Lehrer, sondern auch ein weltbekannter Wissenschaftler […]“ Während seiner Studienzeit in Göttingen lernte er Fritz Lettenmeyer (1891-1953) kennen, der 1920-1922 mit Unterbrechungen für vier Semester in Göttingen weitere Studien betrieb. Der passionierte Alpinist Lettenmeyer machte zusammen mit Ackermann die Gratüberschreitung Huderbankspitze – Kaiserkopf – Hochglück mit Übernachtung in der Lamsenjochhütte 1953m.
	Wilhelm Friedrich Ackermann

1. Problembeschreibung

	For-berechenbare Funktionen sind genau die primitiv rekursiven Funktionen. Ackermann, ein Assistent von David Hilbert, hat eine Funktion gefunden, die zwar total und berechenbar ist, jedoch nicht primitiv rekursiv. Wir wollen hier den Beweis nicht nachvollziehen, wohl aber den Gedankengang, der Ackermann zu seiner Funktion führte. Dazu betrachten wir noch einmal die primitiv rekursiven Definitionen von Addition, Multiplikation, Exponentiation, ...
	Sie wiederlegt Hilberts Vermutung, dass jede berechnenbare Funktion, primitiv rekursiv ist. ack 0 x = x + 1 ack x 0 = ack (x-1) x ack x y = ack(x-1) (ack x (y-1))   Ackemann-Funktion per Definition Funktionswerte der Ackermann-Funktion
	Nun ist auch logisch woher der Name "Flaggenproblem" rührt, nämlich davon, dass die Farbenfolge der Steinchen im geordneten Zustand (von links gesehen) der niederländischen Nationalflagge entspricht. Man kann aber die Problematik der niederländischen Nationalflagge auf jede andere Flagge, die ebenfalls 3 Farben hat, übertragen.

2. Hintergründe, Zusammenhänge - Einordnung in Klassen

	effiziente Lösung nur als rekursiver Algorithmus

3. Lösungsalgorithmus

Dies war die zweite Aufgabe des Flaggenproblems, nämlich nicht nur das Umsortieren der Steinchen, sondern auch das Umsortieren so effizient wie möglich zu machen. E. W. Dijkstra, der Entwickler des Flaggenproblems, ist dabei folgendermaßen vorgegangen. Er schrieb ein Programm in PASCAL in dem der gesuchte Algorithmus als Prozedur dargestellt wird. Hier eine vereinfachte Version seines entworfenen Algorithmus in PASCAL (blau sind die Erklärungen):

4. Programmvorschläge

5. Zusammenfassung

6. Weiterführende Literatur

	der Lösungsalgorithmus der Türme von Hanoi ist nicht komplex, jedoch schon mit geringer Anzahl n mächtig

7. Links zum Thema

	http://de.wikipedia.org/wiki/Ackermannfunktion

8. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	das 8-Dame-Problem des Cliquen-Problem Domino-Problem das Entscheidbarkeitsproblem die Fibonacci-Zahlen das Flaggenproblem das Halteproblem das Hamilton-Problem das K-Farben-Problem der Kaprekar-Algorithmus die Magischen Quadrate das PASCAL'sche Dreiecksproblem das Philosophenproblem das Königsberger-Brückenproblem das Post'schen Korrespondenzproblem das Rucksackproblem das Rundreiseproblem das Springer-Problem die Türme von Hanoi das Wortproblem das Wüstenfit-Problem
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost im Mai 2007