Die Ackermann-Funktion ist ein prominentes Beispiel f\u00fcr eine rekursive Funktion, die jetzt \u2014 und noch die n\u00e4chsten Jahrzehnte \u2014 Informatiker im Studium besch\u00e4ftigt. <\/p>\n
Sie ist nach F. Wilhelm Ackermann (1886-1962) benannt. Viele Funktionen der mathematischen Praxis sind primitiv rekursiv, und David Hilbert stellte 1926 die Frage, ob alle Funktionen, deren Argumente und Werte nat\u00fcrliche Zahlen sind, primitiv rekursiv sind. Die Ackermann-Funktion steigt sehr stark an und ist f\u00fcr Theoretiker ein Beispiel daf\u00fcr, dass es berechenbare Funktionen gibt, die aber nicht primitiv rekursiv sind. Im Jahre 1928 zeigte Ackermann dies an einem Beispiel: der Ackermann-Funktion.6 Sie w\u00e4chst st\u00e4rker als es Substitution und Rekursion erm\u00f6glichen und nur f\u00fcr kleine Argumente lassen sich die Funktionswerte noch ohne Rekursion berechnen. Darin bestand auch die Beweisidee von Ackermann, eine Funktion zu definieren, die schneller w\u00e4chst als alle primitiv rekursiven Funktionen. Wir wollen hier nicht die originale Version von Ackermann benutzen, die durch die Funktionalgleichung<\/p>\n
f(n‘, x‘, y‘) = f(n, f(n‘, x, y), x)<\/p>\n
ausgedr\u00fcckt wird, sondern die vereinfachte Variante von Hans Hermes. Wir wollen die Version von Hermes aber fortan auch Ackermann-Funktion nennen, da sie direkt aus dem Original gewonnen wird. F\u00fcr die oben angegebene Funktion muss in der Abhandlung von Ackermann nachgebl\u00e4ttert werden, um den Nachweis des Nicht-primitiv-rekursiv-Seins zu finden.<\/p>\n
Die neue Ackermann-Funktion ist eine Abbildung von zwei ganzen Zahlen auf eine ganze Zahl a(n,m). Sie ist mathematisch durch folgende Gesetzm\u00e4\u00dfigkeit definiert:<\/p>\n
a(0,m) = m + 1
a(n,0) = a(n – 1, 1)
a(n,m) = a(n – 1, a(n, m – 1))<\/p>\n
Die Ackermann-Funktion ist daf\u00fcr ber\u00fchmt, die Rechenkapazit\u00e4t ganz schnell zu ersch\u00f6pfen. Sehen wir uns die Implementierung in Java an und testen wir das Programm mit ein paar Werten.<\/p>\n
class Ackermann\n{\n public static long ackermann( long n, long m )\n {\n if ( n == 0 )\n return m + 1;\n else\n \n if ( m == 0 )\n return ackermann( n - 1, 1 );\n else\n return ackermann( n - 1, ackermann(n, m - 1) );\n \n }\n public static void main( String args[] )\n {\n int x = 2,\n y = 2;\n System.out.println( "ackermann(" + x + "," + y + ")=" + ackermann(x,y) );\n }\n}<\/pre>\nF\u00fcr den Aufruf ackermann(1, 2) veranschaulicht die folgende Ausgabe die rekursive Eigenschaft der Ackermann-Funktion. Die Stufen der Rekursion sind durch Einr\u00fcckungen deutlich gemacht:<\/p>\n
a(1,2):\n a(0,a(1,1)):\n a(0,a(1,0)):\n a(1,0):\n a(0,1)=2\n a(1,0)=2\n a(0,2)=3\n a(0,a(1,0))=3\n a(0,3)=4\n a(0,a(1,1))=4\na(1,2)=4<\/pre>\nBei festen Zahlen l\u00e4sst sich der Wert der Ackermann-Funktion direkt angeben.
\n
a(1,n) = n + 2 <\/p>\n
a(2,n) = 2n + 3 <\/p>\n
a(3,n) = 2n+3 – 3<\/p>\n
F\u00fcr gro\u00dfe Zahlen \u00fcbersteigt die Funktion aber schnell alle Berechnungsm\u00f6glichkeiten. Zum Vergleich: Die Ackermannfunktion berechnet beim Zahlenpaar (4,7) etwa 0,2*10^20. Unter der Definition a(0,y) = y+1; a(x+1) = a(x,1); a(x+1,y+1) = a(x, (a+1),y)) ergibt sie die folgende gro\u00dfe Tabelle.<\/p>\n
| \n A(x,y)<\/p>\n<\/th>\n | \n y = 0<\/p>\n<\/th>\n | \n y = 1<\/p>\n<\/th>\n | \n y = 2<\/p>\n<\/th>\n | \n y = 3<\/p>\n<\/th>\n | \n y = 4<\/p>\n<\/th>\n | \n y = 5<\/p>\n<\/th>\n<\/tr>\n |
|---|---|---|---|---|---|---|
| \n x = 0<\/p>\n<\/td>\n | \n 1<\/p>\n<\/td>\n | \n 2<\/p>\n<\/td>\n | \n 3<\/p>\n<\/td>\n | \n 4<\/p>\n<\/td>\n | \n 5<\/p>\n<\/td>\n | \n 6<\/p>\n<\/td>\n<\/tr>\n |
| \n x = 1<\/p>\n<\/td>\n | \n 2<\/p>\n<\/td>\n | \n 3<\/p>\n<\/td>\n | \n 4<\/p>\n<\/td>\n | \n 5<\/p>\n<\/td>\n | \n 6<\/p>\n<\/td>\n | \n 7<\/p>\n<\/td>\n<\/tr>\n |
| \n x = 2<\/p>\n<\/td>\n | \n 3<\/p>\n<\/td>\n | \n 5<\/p>\n<\/td>\n | \n 7<\/p>\n<\/td>\n | \n 9<\/p>\n<\/td>\n | \n 11<\/p>\n<\/td>\n | \n 13<\/p>\n<\/td>\n<\/tr>\n |
| \n x = 3<\/p>\n<\/td>\n | \n 5<\/p>\n<\/td>\n | \n 13<\/p>\n<\/td>\n | \n 29<\/p>\n<\/td>\n | \n 61<\/p>\n<\/td>\n | \n 125<\/p>\n<\/td>\n | \n 253<\/p>\n<\/td>\n<\/tr>\n |
| \n x = 4<\/p>\n<\/td>\n | \n 13<\/p>\n<\/td>\n | \n 65533<\/p>\n<\/td>\n | \n 265536-3<\/p>\n<\/td>\n | \n 2265536-3<\/p>\n<\/td>\n | \n a(3,<\/p>\n 2265536-3)<\/p>\n<\/td>\n | \n a(3,a(4,4))<\/p>\n<\/td>\n<\/tr>\n |
| \n x = 5<\/p>\n<\/td>\n | \n 65533<\/p>\n<\/td>\n | \n a(4,65533)<\/p>\n<\/td>\n | \n a(4,<\/p>\n a(4,65533))<\/p>\n<\/td>\n | \n a(4,a(5,2))<\/p>\n<\/td>\n | \n a(4,a(5,3))<\/p>\n<\/td>\n | \n a(4,a(5,4))<\/p>\n<\/td>\n<\/tr>\n |
| \n x = 6<\/p>\n<\/td>\n | \n a(4,65533)<\/p>\n<\/td>\n | \n a(5,<\/p>\n a(4,65533))<\/p>\n<\/td>\n | \n a(5,a(6,1))<\/p>\n<\/td>\n | \n a(5,a(6,2))<\/p>\n<\/td>\n | \n a(5,a(6,3))<\/p>\n<\/td>\n | \n a(5,a(6,4))<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n Ackermann-Funktion f\u00fcr einige Werte<\/i><\/p>\n Die Ackermann Funktion w\u00e4chst, obwohl sie Turing-berechenbar ist, schneller als alle primitiv rekursiven Funktionen. Normale mathematische Notationen versagen beim Schreiben dieser gro\u00dfen Zahlen und eine andere M\u00f6glichkeit muss her um gro\u00dfe Zahlen zu definieren. Schauen wir uns doch erst einmal an, woher die gro\u00dfen Zahlen \u00fcberhaupt kommen. Dazu eine alternative Definition, nach der ersten Zahle entwickelt:<\/p>\n a(0,n) = n + 1 a(2,n) = 2 * (n + 3) – 3 <\/p>\n a(3,n) = 2 ^ (n + 3) – 3 <\/p>\n a(4,n) = 2 ^ 2 ^ … ^ 2 – 3 (wobei die Potenz (n+3)-mal erhoben wird) <\/p>\n Schon bei der Definition von a(4,n) tritt n mal eine Zweierpotenz auf. Mit der herk\u00f6mmlichen Schreibweise unhandelbar. Gl\u00fccklicherweise haben sich ber\u00fchmte M\u00e4nner mit neuen Notationen einen Namen gemacht, unter ihnen der nimmer m\u00fcde werdende Donald E. Knuth. Er schuf 1976 die Up-Arrow-Notation (auf deutsch etwa Nach-oben-Pfeil-Notation \u2013 wir bleiben an dieser Stelle aber englisch). Die Schreibweise wird am besten an der Motivation, die Multiplikation einzuf\u00fchren, verdeutlicht. Addieren wir n mal den Summanden m, so entspricht dies einer Multiplikation vom m mit der Anzahl n (m + m + … + m = m * n). Bilden wir die Potenz einer Zahl, multiplieren wir n mal m, so schreibt sich dies m ^ n = m m … m = mn. F\u00fchren wir dies weiter. Was kommt mach dem n-maligen Produkt? Es kommt danach die n-te Potenz (in Zeichen m^^n, daher zwei mal das Zeichen ^^). Fassen wir bisheriges mit einigen Beispielen zusammen:<\/p>\n \n 2^2 = 2*2 = 4 <\/p>\n 2^3 = 2*2*2 = 8 <\/p>\n 2^4 = 2*2*2*2 = 16 <\/p>\n 3^2 = 3*3 = 9 <\/p>\n 3^3 = 3*3*3 = 27 <\/p>\n 3^4 = 3*3*3*3 = 81 <\/p>\n 4^2 = 4*4 = 16 <\/p>\n 4^3 = 4*4*4 = 64 <\/p>\n 4^4 = 4*4*4*4 = 256 <\/li>\n \n 2^^2 = 2^2 = 4 <\/p>\n 2^^3 = 2^2^2 = 2^4 = 16 <\/p>\n 2^^4 = 2^2^2^2 = 2^16 = 65536 <\/p>\n 3^^2 = 3^3 = 27 <\/p>\n 3^^3 = 3^3^3 = 3^27 = 7625597484987 <\/p>\n 3^^4 = 3^3^3^3 = 3^3^27 = 3^7625597484987 <\/li>\n \n 2^^^2 = 2^^2 = 4 <\/p>\n 2^^^3 = 2^^2^^2 = 2^^4 = 65536 <\/p>\n 2^^^4 = 2^^2^^2^^2 = 2^^65536 = 2^2^…^2 (65536 mal) <\/p>\n 3^^^2 = 3^^3 = 7625597484987 <\/p>\n 3^^^3 = 3^^3^^3 = 3^^7625597484987 = 3^3^…^3 (7625597484987 mal) <\/p>\n 3^^^4 = 3^^3^^3^^3 = 3^^3^^7625597484987 = 3^3^…^3 (3^^7625597484987 mal) <\/li>\n \n 2^^^^2 = 2^^^2 = 4 <\/p>\n 2^^^^3 = 2^^^2^^^2 = 2^^^4 = 2^2^…^2 (65536 mal) <\/p>\n 2^^^^4 = 2^^^2^^^2^^^2 = 2^^^2^2^…^2 (65536 mal) <\/p>\n 3^^^^2 = 3^^^3 = 3^3^…^3 (7625597484987 mal) <\/p>\n 3^^^^3 = 3^^^3^^^3 = 3^^^3^3^…^3 (7625597484987mal) <\/p>\n = 3^^3^3^…^3 (3^3^…^3 (7625597484987 mal) mal) <\/li>\n Nun endlich lassen sich die gro\u00dfen Zahlen mit kleinen Formeln schreiben. So f\u00fcr die ersten f\u00fcnf Elemente:<\/p>\n a(1, n) = 2 + (n + 3) – 3 a(3, n) = 2 ^ (n + 3) – 3 <\/p>\n a(4, n) = 2 ^^ (n + 3) – 3 <\/p>\n a(5, n) = 2 ^^^ (n + 3) – 3<\/p>\n John H. Conway geht noch einen Schritt weiter, denn auch die Up-Arrow-Schreibweise kann die Formel f\u00fcr a(m,n) nicht ohne den Zusatz \u00bb^…^ und dass n-2 mal\u00ab l\u00f6sen. Conway schafft dies mit seiner Chained-Arrow Notation (zu deutsch etwa Ketten-Pfeil Notation, aber wir bleiben wieder beim englischen Begriff). Conway f\u00fchrt f\u00fcr \u00bb^…^\u00ab die Schreiweise<\/p>\n a -> b -> c = a ^^…^^ b<\/p>\n ein, wobei c die Anzahl der Potenzen beschreibt. Nun endlich vereinfacht sich auch der die Ackermann-Funktion. Es folgt:<\/p>\n a(m, n) = 2 -> (n + 3) -> (m – 2) – 3<\/p>\n","protected":false},"excerpt":{"rendered":" Die Ackermann-Funktion ist ein prominentes Beispiel f\u00fcr eine rekursive Funktion, die jetzt \u2014 und noch die n\u00e4chsten Jahrzehnte \u2014 Informatiker im Studium besch\u00e4ftigt. Sie ist nach F. Wilhelm Ackermann (1886-1962) benannt. Viele Funktionen der mathematischen Praxis sind primitiv rekursiv, und David Hilbert stellte 1926 die Frage, ob alle Funktionen, deren Argumente und Werte nat\u00fcrliche Zahlen […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_post_was_ever_published":false,"_links_to":"","_links_to_target":""},"categories":[1],"tags":[],"class_list":["post-2224","post","type-post","status-publish","format-standard","hentry","category-allgemein"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts\/2224","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/comments?post=2224"}],"version-history":[{"count":1,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts\/2224\/revisions"}],"predecessor-version":[{"id":2225,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/posts\/2224\/revisions\/2225"}],"wp:attachment":[{"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/media?parent=2224"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/categories?post=2224"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.tutego.de\/blog\/javainsel\/wp-json\/wp\/v2\/tags?post=2224"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}} |