Diskussion:Ackermannfunktion

Dieser Artikel war am 29. April 2005 der Artikel des Tages.

Neuformulierung von Rozsa Peter

Rozsa Peter hat die vereinfachte Ackermannfunktion nicht, wie angegeben, im Jahr 1955, sondern bereits 1935 publiziert. Quelle: Rozsa Peter, "Konstruktion nichtrekursiver Funktionen", Mathematische Annalen 111, 1935, S. 42 -- 60 -- Dirk Hoffmann (nicht signierter Beitrag von 91.89.19.41 (Diskussion | Beiträge) 12:38, 13. Dez. 2009 (CET))

Fehler im Abschnitt "Idee"?

Wenn man in die Folge $a+b,a\cdot b,a^{b},\ldots$ die Werte $a=2$ und $b=4$ einsetzen würde, bekäme man laut Artikel die Folge 6, 8, 16, 256, $2^{2^{.^{.^{.^{2}}}}}$ (mit 256 Zweien), ...

Müsste nicht das vierte Folgenglied $^{4}2=2^{2^{2^{2}}}=65536$, das fünfte dementsprechend $^{^{^{2}2}2}2$, also ein "Power-Tower" mit 65536 Zweien sein? -- Mumpen 00:44, 18. Mai 2009 (CEST)

Weitere Beispiele

Gibt es ausser der Ackermannfunktion noch weitere Beispiele für nicht LOOP-, aber WHILE-Berechenbare Funktionen? --Derhman, 26. Okt 2006

Vorschlag

Ich möchte für eine Funktion wie die Ackermannfunktion den Begriff Operator Operator "OOperator" vorschlagen. Eine Rechenvorschrift die angibt, wie ein Operator während der Rechnung verändert wird. Im Fall der Ackermannfunktion wäre das wohl ein Potenzoperator, der auf einen + Operator angewendet wird. Wenn man das weiterspinnt fällt mir da noch die Möglichkeit ein, mehrdimensionale operatoren zu definieren, also operatoren, die nicht nur durch einen einzelnen anderen Operator modifiziert werden, sondern durch mehrere. Wenn man auf einen solchen "OOperator" nochmals einen "OOperator" anwendet, erhält man einen ganzen "OOperator Komplex".Viele Grüße, Michael Tuchscherer.

Hallo Michael! Nette Idee, aber wir als Enzyklopädie sollten keine neuen Bezeichnungen erfinden, sondern nur vorhandene erklären. Hast du dir diese Bezeichnung selbst überlegt, oder taucht die irgendwo in der Fachliteratur schon auf? Gruß, Langec ☎ 10:47, 17. Feb 2005 (CET)

Originaldefinition

Hier mal die Originaldefinition von Ackermann:

Zuerst definiert er eine Iterrationsfunktion ρ_c:

ρc(f(c),a,0)=a
ρc(f(c),a,n+1)=f(ρc(f(c),a,n))

Sodann definiert er drei weitere Funktionen:

λ(a,b) = 1, falls a=b und sonst 0.
ι(a,b) = 0, falls a=b und sonst 1.
α(a,n) = ι(n,1)·ι(n,0)·a+λ(n,1)

Als nächstes definiert er die hier auftauchende Multiplikation rekursiv. Dann kommt er zur eigentliche Funktion:

φ(a,b,0) = a+b
φ(a,b,n+1) = ρc(φ(a,c,n),α(a,n),b)

Die Funktion α ist übrigens die Funktion ψ in der Definition im Artikel. --Berni 18:57, 9. Jul 2004 (CEST)

Review

Hier die kopierte Diskussion aus dem Review. Ich habe den Artikel rausgenommen, weil im Review schon lange kein Kommentar mehr viel (mit Ausnahme meines eigenen, den ich auch umgesetzt habe). Am Artikel passierte in letzter Zeit auch nicht mehr so viel. Also habe ich ihn aus dem Review genommen und dafür auf die Kandidatenliste gesetzt. Bitte nicht hauen. Kopierte Diskussion aus dem Review folgt. -- Dishayloo [ +] 20:18, 5. Aug 2004 (CEST)

---

Motive

Diesen Artikel hatte ich etwas voreilig bei den Kandidaten für exzellente Artikel eingestellt, nachdem ich die englische Version unter Featured Articles entdeckt und den bisherigen Artikel mit der Übersetzung aus dem Englischen erweitert hatte. Ich wusste allerdings nicht, dass in der englischen WP kein so hoher Maßstab angelegt wird wie hier, und der Artikel hat eben noch einige Schwachpunkte, die ich jetzt gerne hier klären würde:

• Wie erklärt man überhaupt einem Nicht-Informatiker/Mathematiker, worum es geht? Die Definition "berechenbar, aber nicht primitiv-rekursiv" gehört z.B. unbedingt in den ersten Absatz, weil dann Leute mit Vorkenntnissen direkt wissen, worum es geht. Aber Leute ohne Vorkenntnisse verstehen hier eben nur Bahnhof.
• Wie sah Ackermanns ursprüngliche Definition aus? Die einzige Internet-Quelle ist dieses Buch, aber die taugt nichts, weil ich sie nicht verstehe. Kennt jemand ein Buch oder Vorlesungsskript, wo das drin steht?
• Sollen wir die von Stern erwähnte vereinfachte, aber nicht äquivalente Definition $a$ stehen lassen oder streichen?
• Von wem ist nun die heute übliche Definition? Von Hermes, wie einige deutsche Quellen behaupten, oder aber von Peter und Robinson, wie englische Quellen behaupten?
• Wenn ich schon was von Conway-Kettenpfeilen und Hyper-Operatoren reinschreibe, muss ich die entsprechenden Artikel wohl auch schreiben, vielleicht aus en: übersetzen. Wenn ich mal Zeit dazu habe... Überhaupt sind auch die anderen Artikel, auf die "Ackermannfunktion" verweist (z.B. primitiv-rekursive Funktion, LOOP-Programm) noch sehr kurz. Und zum Union-Find-Problem, dem einzigen mit bekannten Beispiel, wo die Inverse der Ackermannfunktion auftaucht, gibt es weder einen deutschen noch englischen Artikel. Das wäre fast Grund für eine Qualitätsoffensive "theoretische Informatik" ;-)
• Hat jemand Grafiken, die die Wertetabelle und die Bemerkungen zu Benchmarks veranschaulichen?
• Wie viel Theorie gehört in den Artikel? Das Interessanteste an der Funktion ist ja der Beweis, dass sie nicht primitiv-rekursiv ist, aber das wären mehrere Seiten trockene Formeln. Welche interessanten Bemerkungen für Laien könnte man noch einfügen?

Fazit: Es würde mich reizen, so einen trockenen Stoff "exzellent" zu erklären; Ihr seid herzlich eingeladen :-) Langec 16:52, 26. Jun 2004 (CEST)

Zur inversen Ackermann-Funktion: Union-Find ist nicht das einzige Beispiel, wo diese auftaucht (siehe englischer Artikel en:Ackermann function#Inverse. Die maximale Zeitkomplexität der Aufgabe, die untere Kontur (Algorithmische Geometrie) von n Funktionskurven zu finden, liegt in O(n*inv_ack(n)), also O(n) für alle praktisch auftauchenden Werte von n (weil inv_ack so wahnsinnig langsam wächst). Quelle: http://yucs.org/~gnivasch/alpha/index.html , die für den Artikel vielleicht interessant wäre. Dort gibt es auch den Hinweis auf die Log-Stern-Funktion, die ich vergeblich in der WP gesucht habe. Die inverse Ackermannfunktion lässt sich scheinbar durch die wiederholte Anwendung des Logarithmus abschätzen (und zwar durch die Anzahl der Anwendungen, bis ein Schwellwert unterschritten wird). Dadurch wird diese auch schnell berechenbar (und die obige Abschätzung "für alle relevanten Werte" nachrechnen). Hättest du Zeit, Lust und Ahnung, einen Absatz zur inversen Ackermann-Funktion zu schreiben/übersetzen? --131.220.5.40 17:49, 20. Nov. 2007 (CET)

Bisherige Kommentare

Da ich soeben den Artikel aus der Kandidatenliste für exzellente Artikel entfernt habe, hier die dort gefallenen Kommentare (Langec 00:35, 29. Jun 2004 (CEST)):

• contra: "heute ist ... gebräuchlich" - wie sah die von Ackermann definierte Variante denn aus (kenne nur die vereinfachte)? Zu nicht primitiv-rekursiv sollte noch ein ganz, ganz kurzer Pberblick über loop-Berechenbarkeit folgen. ("Das bedeutet, dass..."). Das "wir betrachten" ist Lehrbuchstil und sollte in einer Enzyklopädie vermieden werden. Werd mich dessen wenn ich Zeit habe mal annehmen. Die intuitive Erklärung finde ich wenig intuitiv, ebenfalls die explizite Beschreibung. Anwendung fehlt noch, tatsächlich gibt es wohl ausserhalb der Theoretischen Informatik wohl kaum etwas, das die Ackermann-Funktion benötigt. Damit habe ich kein Problem, aber angemerkt werden sollte es. Wenn es doch Anwendungen gibt - nur her damit! --nd 13:49, 24. Jun 2004 (CEST)
• contra: Drei Zeilen Geschichte ganz hinten inmittn in unverständlicher Fachbuchmathematik. Keine Anwendungen, kein Grund, warum es die Formel überhaupt gibt, keine Vergleiche mit anderen Ansätzen der Berechenbarkeit, kein Wort über die konkrete Bedeutung innerhalb der Berechbarkeitstheorie, nicht ein erklärtes Formelzeichen, unkommentiere Tabelle keine Literatur ... Einer von den Artikeln, wie cih sie in letzter Zeit hassen gelernt habe. Un wetten, ich kenne die Antwort auf die Kritik schon: Das muss ein Nichtmathematiker nicht verstehen! -- Necrophorus 15:14, 24. Jun 2004 (CEST)
• contra: (1) die Ackermannfunktion, und dann werden 2 vereinfachte Versionen mit unterschiedlichen Werten angegeben, was denn nun? - (2) die Definition ist ja schön, mit ein paar Erklärungen wär sie vielleicht auch zu verstehen - (3) das Programmbeispiel entspricht nicht der Definition - (4) Explizite Beschreibung: Intuitiv definiert ..., intuitiv verstehe ich hier nur Bahnhof - es mag sein, das in en: die Kriterien anders sind, aber für de: steckt noch einiges an Arbeit drin. -- srb 19:25, 24. Jun 2004 (CEST)
• contra, stilistisch zu schwach, mit Wiederholungen, und Erklärungen, die wiederum der umfangreichen Erklärung bedürfen. Nach ein paar Umstrukturierungen kann der Artikel aber exzellent werden: Ab ins Review! -- 2⁴⁰ Bytes (Diskussion) 12:21, 26. Jun 2004 (CEST)
• pro: Mehr kann man über die Ackermann-Funktion nicht sagen. Denkt bei Eurer Bewertung immer auch an die Zielgruppe mathematischer Artikel. Stern 18:45, 27. Jun 2004 (CEST)
• contra: Das sind ja nur Tabellen und Formeln. Nirgends ist erklärt, wozu diese Funktion überhaupt funktioniert. Woppi 19:21, 28. Jun 2004 (CEST)
• contra: Noch nicht mal ich als Numeriker verstehe den Artikel. Tja Stern, was ist die Zielgruppe mathematischer Artikel? Leute, die Mathematik nur als geistige Onanie begreifen? Die mögen sich doch bitte mit einem mathematischen Lexikon begnügen. Wir sind eine Enzyklopädie. Ganz nebenbei: Der Begriff "primitiv-rekursiv" sollte im Artikel "Ackermannfunktion" direkt erklärt werden, da er für das Verständnis so extrem wichtig zu sein scheint. Erklärt wird er aber noch nicht mal im "primitiv-rekursiv"-Artikel, sondern dort auch nur kurz definiert. Der Artikel "Berechenbarkeitstheorie" ist auch noch sehr mau. Mir scheint es: mit dem derzeitigen Material in der Wikipedia ist es kaum möglich zu verstehen, was einem der vorgeschlagene Artikel überhaupt sagen will. --DaTroll 22:40, 28. Jun 2004 (CEST)

Sorry, ich habe mich hier etwas gehen lassen. Mal was konstruktives: ich bin mir ziemlich sicher, daß es eine kombinatorische Herleitung der Ackermannfunktion gibt. --DaTroll 09:44, 29. Jun 2004 (CEST)

Irgendwelche Hinweise, wie diese Herleitung aussieht? Würde mich interessieren! --Langec 16:05, 1. Jul 2004 (CEST)

Die Unterlagen sind wohl beim letzten Umzug verloren gegangen. Vermutlich ging es auch nicht um eine Herleitung der funktion selbst, sondern um eine Funktion, die vom Wachstum her O(Ackermann) ist. --DaTroll 15:22, 3. Jul 2004 (CEST)

Vollständige Überarbeitung

Berni hat einen weiteren Erklärungsversuch gestartet. Der ist nicht schlecht, aber überschneidet sich mit dem Absatz "Explizite Beschreibung". Ich versuche, das irgendwie zu mischen. Aber zuallererst übernehme ich jetzt mal den Hyper-Operator aus en:, denn der wird für diese Erklärung vorausgesetzt. --Langec 12:54, 8. Jul 2004 (CEST)

Ich habe mir den Artikel heute morgen nochmal in Ruhe durchgesehen und bin zu dem Ergebnis gelangt, dass er ziemlich unaufgeräumt ist, stark formellastig und unverständlich. Um dem zu begegnen habe ich den Morgen mit Recherchen verbracht (u.a. Originalartikel von Ackermann) und bin gerade dabei, den Artikel nochmal komplett neu zu schreiben; das bereits vorhande möchte ich dabei mit einbauen. Voraussichtlich habe ich das bis heute Abend fertig; ich kann es aber nicht versprechen, evtl. wird es bis morgen mittag dauern. Morgen mittag werde ich aber auf alle Fälle das einstellen, was ich habe, damit hier motivierte Leute nicht unnötig ausgebremst werden.--Berni 13:46, 8. Jul 2004 (CEST)

Hallo Berni, danke für deinen Einsatz! Aber pass auf, dass bei der Generalüberholung nichts verloren geht. Ich habe eben noch die Einleitung und das C-Programm überarbeitet, außerdem deine Idee und die bisherige explizite Beschreibung vereinigt. Außerdem habe ich jetzt den Hyper4-Operator aus dem Englischen übersetzt. --Langec 13:57, 8. Jul 2004 (CEST)

Hab's geseh'n. Ja, ich pass auf. Ich halte allerdings das C-Programm für Unsinn (persönliche Meinung), aber ich werde es trotzdem einbauen, da können wir dann danach drüber diskutieren.--Berni 14:38, 8. Jul 2004 (CEST)

OK, in dieser Fassung nützt das C-Programm wenig, weil es nur die Definition umsetzt und somit ziemlich ineffizient ist. Andererseits schadet es auch nicht. Interessant wäre allerdings ein Programm, das iterativ vorgeht und Zwischenergebnisse abspeichert. --Langec 16:05, 8. Jul 2004 (CEST)

Ich habe jetzt mal eine rekursionslose Version eingebaut (in C++, um die Standard-Stackklasse verwenden zu können; diese Klasse ist aber das einzige C++-typische am Code) --Ce 22:40, 8. Jul 2004 (CEST)

Naja, rekursionslos ist die nicht, die Rekursion wird halt in einem Stack+Schleife versteckt, mehr aber nicht. Was wohl Langec wollte, ist eine, die diese vielen Mehrfachberechnungen wegläßt.--Berni 16:20, 9. Jul 2004 (CEST)

Doch, sie ist rekursionslos, da sie sich nicht selbst aufruft. Dass es ohne einen Stack (der hier eine reine Datenstruktur ist, also keine Rücksprungadressen aufnimmt!) nicht geht, steht ja schon im Artikel (bzw. stand dor vor der Umarbeitung, Zitat, hervorhebung von mir: "Die Ackermannfunktion ist WHILE-berechenbar, wenn man sie iterativ statt rekursiv implementiert; dazu muss man jedoch die Verwaltung des Stacks, d.h. des Speichers für die Zwischenergebnisse, selbst programmieren"). Hierbei haben das "selbst programmieren" schon die STL-Autoren erledigt.

Das "Zwischenergebnisse abspeichern" habe ich zugegebenermaßen überlesen; allerings ist das ja unabhängig von rekursiv vs. iterativ.

Ich kann ja auch mal eine Version mit Zwischenspeichern machen; ich stelle am besten morgen ein paar Versionen mit unterschiedlichen Eigenschaften in die Diskussionsseite zwecks Entscheidung, welche letztendlich in den Artikel kommen soll. --Ce 23:25, 10. Jul 2004 (CEST)

Also ich bin da anderer Meinung. Ich stimme dir zu, dass sie keine rekursiven Aufrufe enthält. Aber ich bin immernoch der Meinung, das sie rekursiv ist. Aber wie dem auch sei, eine Version, die Zwischenergebnisse abspeichert, ist so oder so interessanter.--Berni 16:31, 12. Jul 2004 (CEST)

Neue Version

So, die Überarbeitete Version ist drin. Das ist zwar noch nicht ganz das, was ich mir heute morgen vorgestellt hatte, aber mein Kopf raucht grad, und da dachte ich, ich stell jetzt einfach mal rein, was ich bisher gemacht habe. Das Ganze hat aber noch einige Lücken/Fehler. Die, bei denen ich mir darüber bewusst bin, möchte ich hier mal hinschreiben:

• Der Name Peter hat auf einem der e einen Akzent. Ich weiss aber grad nicht welcher und auf welches e. Meinen Recherchen zufolge war Peter der erste der die neuere Definition angab. Hermes hat ziemlich sicher die Definition von Peter und Ribenboim oder wie der andere Kerl hieß, der da noch erwähnt wurde, könnte ich nirgends finden.

Wie sieht eigentlich die ursprüngliche, "umständliche" Definition von Ackermann aus? Hast du die auch irgendwo? Würde mich mal interessieren. --Langec 14:13, 9. Jul 2004 (CEST)

Kann ich nochmal raussuchen. Geht irgendwie über eine Iterationsfunktion.--Berni 16:28, 9. Jul 2004 (CEST)

Ok, hab's nochmal rausgesucht. Ich schreibs gleich mal auf die Diskussionsseite der Ackermann-Seite.--Berni 18:47, 9. Jul 2004 (CEST)

Vielen Dank :-) Ich wollte einfach mal wissen, wie diese Def. aussieht. Aber die kann man wirklich keinem zumuten... --Langec 13:10, 12. Jul 2004 (CEST)

• Der Conway-Operator und das Hyper-Zeug fehlt noch. Ich wollte das noch einbauen, aber bin grad nimmer in der Lage dazu. Mach ich morgen, wenn's bis dahin noch niemand anderes getan hat.

Den Anfang dazu habe ich gemacht, bei der Idee. Der Conway-Operator ist eigentlich nur sinnvoll, wenn dazu auch jemand einen Artikel schreibt. --Langec 14:13, 9. Jul 2004 (CEST)

Seh ich auch so.--Berni 16:28, 9. Jul 2004 (CEST)

Ich hab' grad nochmal drüber nachgedacht. Ich bin inzwischen der Meinung, dass es so, wie es jetzt ist, gut ist. --Berni 19:49, 9. Jul 2004 (CEST)

• Der Beweis fehlt.

Der käme ja sowieso in einen von dir vorgesehenen Expertenabschnitt. Beweise sind ja in der Wikipedia nicht unbedingt erforderlich. --Langec 13:29, 9. Jul 2004 (CEST)

Ja, sind nicht erforderlich, aber hier finde ich, kann er schon hin, weil es ja einer der wesentlichen Punkte für die Existens der Ackermannfunktion ist.--Berni 16:28, 9. Jul 2004 (CEST)

So jetzt ist eine Beweisskizze da. Ausführlicher macht es meines Erachtens keinen Sinn.--Berni 19:49, 9. Jul 2004 (CEST)

Zumal dann aus der nächsten Studenten-Generation keiner mehr die Lemmata zur Monotonie der A.-Funktion selber beweisen müsste, weil jeder aus der Wikipedia abschreiben könnte ;-) --Langec 13:10, 12. Jul 2004 (CEST)

• "Laufzeitabschätzung bei Union-Find" ist inkonsistent, zudem wird Union-Find ncht erklärt. An dieser Stelle noch eine Anmerkung: Ein Freund von mir hatte sich den Beweis hierfür mal angesehen und meint, dass da garnicht die Umkehrfunktion der Ackermannfunktion benutzt würde, sondern die Umkehrfunktion von Hyper4. Für die Praxis macht das allerdings keinen Unterschied.

Aha, gut zu wissen, dass das die Umkehrfunktion von Hyper4 ist, war mir gar nicht aufgefallen. Aber wie gesagt, es macht keinen Unterschied. Die Funktionswerte der Ackermannfunktion interessieren ja in der Praxis nicht, nur das Wachstumsverhalten. --Langec 13:29, 9. Jul 2004 (CEST)

• Implementation, Wertetabelle und Genauere Betrachtung würde ich rausschmeißen, bzw. stark kürzen.

Wertetabelle sollte drinbleiben, denke ich. Sonst kann sich ja keiner was unter der Funktion vorstellen. Oder kann man sie irgendwie sinnvoll grafisch darstellen? --Langec 13:29, 9. Jul 2004 (CEST)

Ne, graphisch ist das ein senkrechter Strich. Die Funktion wächst einfach zu schnell. Ich würde die Wertetabelle aber dennoch etwas zusammenschrumpfen, da man sich unter a(5,a(6,2)) doch nix vernünftiges vorstellen kann. Vielleicht macht es sinn, bei solchen einträgen eine Abschätzung ala 10^10^xxx einzufügen.--Berni 16:28, 9. Jul 2004 (CEST)

• Der Busy-Beaver Abschnitt ist sehr kurz.

... das gehört auch in einen extra Artikel, siehe z.B. en:Busy beaver --Langec 13:29, 9. Jul 2004 (CEST)

Hm, unter Turingmaschine ist ein zu den Bibern ein Link auf Tibor Radó, der angeblich diese Funktionen erdacht hat. Ich linke da mal vorläufig hin, aber was ist nun richtig? --Langec 13:45, 9. Jul 2004 (CEST)

Es wird wohl eher Radó gewesen sein, siehe z.B. diese Quelle. --Langec 13:48, 9. Jul 2004 (CEST)

Ja, war Rado. Hab' ich schlecht recherchiert...--Berni 16:28, 9. Jul 2004 (CEST)

Irgendwann müsste man (ich, vielleicht) die Busy-Beaver-Funktion dann auch mal aus dem Radó-Artikel in einen eigenen auslagern (siehe auch en:) --Langec 13:10, 12. Jul 2004 (CEST)

• Stilistische ist noch einiges zu machen. An vielen Stellen ist der Text Schulbuch artig.
• Primitiv-rekursiv habe ich nicht konsequent mit Bindestrich geschrieben

Frage: was für nicht-primitiv-rekursive Funktionen kommen im Compilerbau vor? (Wir haben hier nur eine Schmalspur-Compilerbau-Vorlesung :-( ) Wenn du das erwähnst, dann gib bitte auch ein Beispiel!--Langec 14:01, 9. Jul 2004 (CEST)

Ich kenne selber kein Beispiel. Das habe ich nur in einem Lehrbuch gefunden. Allerdings weiss ich auch nimmer welches der vielen, die ich gewältzt habe, es war. Ich vermute aber, dass es sich um Optimierungsalgorithmen handelt, da diese ja auch Funktionen wie Ackermann optimieren können müssen.--Berni 16:28, 9. Jul 2004 (CEST)

Mir ist gerade auf gefallen, dass Schöning "primitiv rekursiv" ohne Bindestrich schreibt. Welche Version ist jetzt richtig? Germinsten vor ;-) --Berni 19:49, 9. Jul 2004 (CEST)

Ich sag mal pragmatisch: wenigstens die WP sollte eine einheitliche Schreibweise pflegen. Und ich habe soeben mal dafür gesorgt, dass es bei uns einheitlich "primitiv-rekursiv" heißt. Wer dann rausfindet, was wirklich richtig ist, kann es immer noch ändern. --Langec 13:10, 12. Jul 2004 (CEST)

• Links fehlen noch.
• Ein Bild von Ackermann und Peter wäre schön. Hat sonst noch wer eine Idee, für graphische Auflockerungen?
• LOOP-Programme/WHILE-Programme habe ich bereits entfernt, die haben da nichts zu suchen. Im Artikel werden durchgängig die alternativen Bezeichnungen primitiv-rekursiv bzw. μ-Rekursiv benutzt. LOOP/WHILE führt da nur zu Verwirrungen.--Berni 17:30, 8. Jul 2004 (CEST)

Die zweite Zeile der rekursiven Definition ist: $\phi (a,b,n+1)=\psi (a,n)$. Soll da nicht eher links vom Gleichheitszeichen $\phi (a,0,n)$ stehen? Würde mir an der Stelle logischer erscheinen. -- Dishayloo [ +] 04:29, 2. Aug 2004 (CEST)

Wertetabelle

Die Anmerkung an der Zelle für a(4,2) verwundert mich ein wenig. Dass die angegebene Zahl 19729 Dezimalstellen lang ist, sollte offensichtlich sein, da sie auch im Dezimalsystem angegeben ist: $2^{65536}-3\approx 2\cdot 10^{19728}$ (nicht signierter Beitrag von 92.225.78.163 (Diskussion) 17:51, 28. Jul 2010 (CEST)) Die Werte passen nicht zur obigen Definition. Wie auch weiter unten explizit steht, ist a(0,n) = n+1. (nicht signierter Beitrag von 95.112.189.146 (Diskussion) 21:47, 11. Jan. 2011 (CET))

Berechnung von a(4,2)

Im Artikel steht: Es sei noch festgehalten, dass der Funktionswert a(4,2), der in Form einer 19727-stelligen Dezimalzahl auf verschiedenen Internetseiten auftaucht, wahrscheinlich nicht mit der rekursiven Definition der Ackermannfunktion praktisch berechnet werden kann, weil dafür bei weitem zu viel Speicherplatz für die Zwischenergebnisse benötigt würde.

Schaut man sich aber die Seite unten an, auf der der dezimale Wert von a(4,2) steht, so findet man ein LISP-Programm, mit welchem der Wert ermittelt wurde. Dieses Programm ist auf jeden Fall rekursiv.

Ansonsten guter Artikel!

Wie das <math>-Zeugs so ausschaut...

Da hier offensichtlich regelmäßig Leute der Meinung sind, dass das besser wird, wenn man jede Formel in eine <math>-Umgebung packt, hier mal ein Screenshot, wie das bei mir so ausschaut:

Ein weiterer Nachteil von diesen vielen <math>-umgebung ist der, dass der Server mehr belastet wird, was auch keinen Sinn ergibt.--Berni 15:15, 27. Sep 2004 (CEST)

Wachstum der Tangens-Funktion

Folgenden Absatz habe ich mal wieder aus dem Artikel gelöscht, weil er mir unwissenschaftlich erscheint:

Jedoch bleibt eine Funktion in Bezug auf schnelles Wachstum ungeschlagen: Der Tangens. Jedoch ist dieser nicht für alle reellen Zahlen definierbar bzw. hat periodische Singularitäten.

Warum?

1. Die Ackermannfunktion bzw. Busy-Beaver-Funktion ist eine diskrete Funktion. Solche Funktionen haben keine Pole, weshalb viele Methoden aus der Analysis unbrauchbar sind, um ihr Wachstum zu charakterisieren.
2. Der Tangens als reelle Funktion ist deshalb mit diesen diskreten Funktionen überhaupt nicht vergleichbar.
3. Der Tangens ist wohl auch nicht die am schnellsten wachsende Funktion, wie die Formulierung suggeriert; jede andere Funktion mit einem Pol täte es auch.

Viele Grüße, Langec ☎ 14:04, 30. Apr 2005 (CEST)

klare und einfache Definition

Leider sind beide gegebenen Definitionen in einem unklaren Stil gehalten. Interessanterweise ist die zweite Definition schlicht weg eine komplett andere Funktion; sie hat sogar eine abweichende Anzahl an Argumenten. Deswegen ist hier eine eindeutige und klare Definition:

$A(0,x,y)=y+1$

$A(1,x,0)=x$

$A(2,x,0)=0$

$A(n+3,x,0)=1$

$A(n+1,x,y+1)=A(n,x,A(n+1,x,y))$

Vielleicht noch elementarer ist allerdings die Anwendnung der sogenannten "Nachfolgerfunktion", welche jeder natürlichen Zahl einfach ihren Nachfolger zuordnet (also x'=x+1). Damit könnte man sich den Rückgriff auf die Addition sparen:

$A(0,x,y)=y'$

$A(1,x,0)=x$

$A(2,x,0)=0$

$A(n''',x,0)=1$

$A(n',x,y')=A(n,x,A(n',x,y))$

Etwas unschön ist natürlich, dass man drei verschiedene Gleichungen für die Anfangsbedingungen A(-,x,0) angeben muss. Wer eine sinnvolle und verständliche Form hat, wie man das eleganter schreiben kann - möglicherweise über eine Art neutrales Element -, soll sich bitte melden. Allerdings einfach eine Funktion $\phi$ dazu zu erfinden, die halt gerade diese Eigenschaften hat, ist wohl eher kontraproduktiv und führt keineswegs zu einer Verbesserung der Definition.

Keine Ahnung, wie man das besser schreiben könnte. Dumm ist nur, dass es wohl nicht die Ackermannfunktion gibt, sondern mehrere Definitionen ähnlicher Funktionen, die aber alle so genannt werden. Ich wüsste auch mal gerne, ob eine davon als "Standard" akzeptiert wird. Wenn ja, sollten wir die natürlich hier nennen. --Langec ☎ 18:18, 13. Dez 2005 (CET)

Es scheint sich einerseits um eine drei-argumentige Funktion zu handeln, die für Mathematiker interessant ist, weil die Funktion bei entsprechender Wahl des ersten Parameters die mathematischen "Standard"-Operationen liefern (Nachfolger,+.*,^,...).

Andererseits wird aber wohl auch eine zwei-parametrige Funktion so bezeichnet, die wohl für Informatiker interessant ist, da sie sehr schnell steigt und mit ihr der Aufwand ihrer Berechnung und somit sich ein nicht triviales Aufwandsklassen-Problem ergibt..., 2006-03-06,14:48

a(m,n) statt a(n,m)

Bin ich der einzige, der es komisch findet, dass n der erste Parameter und m der zweite ist? Gewöhnlich wird es andersrum definiert (so auch im englischen Artikel). Ich finde das sehr verwirrend. --Oxygene 19:24, 3. Jan. 2007 (CET)

Java 1.4.2, n = 13

Im Text steht "Zum Vergleich hierzu: Mit Java 1.4.2, mit den Standardspeichereinstellungen, erreicht man heutzutage n = 13." Woher stammt diese Aussage? Quellen? Ich laufe mit der einfachen rekursiven Implementierung sehr schnell in einen StackOverflow. --Ahoehma 08:05, 18. Mär. 2010 (CET)

obere Schranke

"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."

Es ist nicht ganz klar, was dieser Satz überhaupt bedeuten soll. Geht es, wenn von "folgenden Funktionsaufrufen" die Rede ist, um das, was bei der Berechnung der Ackermannfunktion auf Rechenanlagen vermittels funktionaler Programmiersprachen passiert? Mathematik und Algorithmik sind nicht dasselbe. Die Definition der Ackermannfunktion ist älter als das Konzept der funktionalen Programmiersprache, und ihre Eigenschaften sind unabhängig von solchen Berechnungsmodellen. Schlimmer ist: Die Behauptung ist falsch. Selbst wenn man sie wohlwollend liest als "dass es ... keine allgemeine obere Schranke für das Wachstum von n gibt", ist nichts gesagt, was die Ackermannfunktin für den Mathematiker interessant macht. Entscheidend ist, dass man keine solche Schranke angeben kann, ohne die Berechnung (oder eine dazu äquivalente) durchzuführen.--217.232.202.228 20:18, 29. Mär. 2010 (CEST)

Verwechslungsgefahr der beiden (vielen?) Definitionen

So viel Arbeit auch in diesen Artikel geflossen sein mag, meiner Meinung nach wird das fast komplett dadurch zunichte gemacht, dass der Artikel sehr unklar mit den mehreren Definitionen umgeht. Einige Unklarheiten, die mir aufgefallen sind:

• Laut Einleitung gab es ursprünglich eine solche Funktion, später dann eine ganze Reihe davon. Im Folgenden werden aber nur das Original und eine weitere Variante eingeführt, was ja nicht gerade eine ganze Reihe ist.
• Auf den ersten Blick wird dann $\varphi (a,b,c)$ als Ackermanns Definiton eingeführt, und ${\textrm {a}}(n,m)$ als Péters Variante. Immerhin ist dies eindeutig und wird im Restlichen Artikel auch überall dort gut durchgezogen, wo die Funktionsnamen direkt durch die beiden Zeichen angegeben werden.
• Allerdings wird dann im Folgenden stets Ackermannfunktion gesagt, auch wenn fast immer die Ackermann-Péter-Funktion gemeint ist. In manchen Texte mag es ja ok sein, Ackermann zu schreiben und Ackermann-Péter zu meinen, aber in einem Artikel, der beides diskutiert, finde ich eine klare Verwendung obligatorisch.
• Mehrfachdefinition von f (wir haben doch noch 25 (-1 für's a) weitere Buchstaben in unserem schönen Alphabet...)
  • Für die Betrachtung des Wachstums werden dann zwei Verkürzungen angegeben, die beide mit $f(n)$ bezeichnet werden, und die als $f(n)=\varphi (n,n,n)$ bzw. $f(n)={\textrm {a}}(n,n)$ definiert sind.
  • Im Abschnitt Benchmark für rekursive Aufrufe wird zunächst ein drittes f, nämlich $f(n)={\textrm {a}}(3,n)$ eingeführt.
  • Und direkt darunter im Abschnitt Laufzeitabschätzungen mit der Umkehrfunktion wieder zu einer alten Definition von f zurückgekehrt.
• Dann folgen vier Implementierungen der Ackermannfunktion, von denen offenbar die ersten drei (Pseudocode, Pseudocode und Haskell) die Definition von Péter und die letzte (Prolog) die von Ackermann darstellen - warum das?
• Als Bezeichner werden hier ack für Péter und ackermann für Ackermann eingeführt. Da fragt man sich z.B., ob diese Schreibweise auch anderswo geläufig ist, oder ad hoc für das Beispiel entwickelt wurde. Falls letzteres der fall ist, dann wären doch ack_pet, ackermann_peter, ap, a (in Anlehnung an die Funktionsdefinition, dann vieleicht phi für das letzte Beispiel) oder peter bessere Namen für die ersten drei Programmbeispiele.
• Letzlich lässt der Artikel die Frage offen, ob die Variante von Péter eine komplett andere Funktion ist als das Original von Ackermann, oder ob eine der beiden Funktionen zur Berechnung aller oder mancher Werte der anderen Funktion genutzt werden kann.

Sorry wenn sich dieser Kommentar mal wieder nach unkonstruktivem Meckern anhört. Ich weiß, das Wikipedia vom Mitmachen lebt und ich auch versuchen könnte, es selbst besser zu machen. Aber erstens bin ich mir bei meinen obigen Beoachtungen teils selbst noch unsicher, andererseits finde ich, wenn ein Artikel schon den Excellenz-Aufkleber trägt und dann noch so eklatante Probleme bestehen, dann darf man auch mal meckern. --Prauch 09:43, 12. Aug. 2010 (CEST)

Die Prolog-Implementierung realisiert auch die Definition von Péter. Weil es in Prolog keine Funktionen, sondern nur Prädikate gibt, taucht der "Rückgabewert" auch in der Parameterliste auf. --77.20.43.8 23:21, 10. Apr. 2017 (CEST)

Aktuelle Version der originalen Ackermann Funktion is falsch

die originale Ackermann-Funktion $\varphi$ beginnt mit $\varphi (a,b,0)=a+b\,$ und nicht wie angegeben mit $\varphi (a,b,0)=a+1$ (auch wenn das logisch vielleicht schöner ist).

Die Ironie ist, dass der Orignal-Artikel auf deutsch ist, es aber auf der deutschen Wikipedia-Seite falsch ist, während es auf der englischen richtig ist!

Ich hab nur im Moment keine Zeit, die Seite komplett umzuarbeiten - mit allen Implikationen zu Aussagen über die Funktion (und es sieht so aus, als wenn die historischen Versionen schon mal richtig waren, gesehen an einigen Diskussionsbeiträgen.) (nicht signierter Beitrag von Bo198214 (Diskussion | Beiträge) 10:32, 22. Apr. 2011 (CEST))

Ist nun umgesetzt... --Daniel5Ko 21:44, 8. Jun. 2011 (CEST)

Quelle: Busy Beaver wächst schneller als Ackermannfunktion

Hallo, ich hätte für die Aussage, dass die Busy Beaver Funktion schneller wächst als die Ackermannfunktion gerne eine Quelle. --MartinThoma (Diskussion) 11:08, 17. Apr. 2012 (CEST)

Bitteschön, siehe z.B. hier: Grenzen der Mathematik, Hoffmann, Dirk W., 2013, Seite 266: „So lässt sich beweisen, dass die Biberfunktion stärker wachsen muss als jede berechenbare Funktion“. --2003:D4:C705:8501:5805:3D26:CFAE:8036 13:47, 20. Jun. 2020 (CEST)

Modifizierte Ackermannfunktion - Quelle und Komplexität

Für die modifizierte Ackermannfunktion habe ich leider nur eine Quelle gefunden, in der sie angewendet wird. Kennt jemand den Ursprung dieser Variante? Zudem suche ich noch eine Quelle für die Komplexität der modifizierten Funktion. Die Inversen liegen in der gleichen Komplexitätsklasse, bei $A(n)\in \Theta (\varphi (n,n,n))$ bin ich mir nicht ganz sicher. --Cerotidinon (Diskussion) 10:32, 17. Feb. 2014 (CET)

Exzellent?

Dieser Artikel wurde vor ziemlich genau 10 Jahren, am 22. August 2004, für exzellent erklärt. Damals waren die Kriterien noch etwas andere, und seither ist er meiner Meinung nach nicht besser geworden. Es gab viele einzelne Beiträge, aber es fehlt dem Artikel eine einheitliche Linie. Vor 5 Jahren hat jemand in der Diskussion eingeworfen, dass die Jahreszahl von Rózsa Péters Arbeit falsch ist – bis heute ist dem niemand nachgegangen. Im Artikel ist die Péter-Ackermann-Funktion definiert als:

$\operatorname {a} (0,m)=m+1$

$\operatorname {a} (n+1,0)=\operatorname {a} (n,1)$

$\operatorname {a} (n+1,m+1)=\operatorname {a} (n,\operatorname {a} (n+1,m))$

In Péters Arbeit (Seite 59) lautet die Definition:

$\operatorname {\varphi } (0,n)=2n+1$

$\operatorname {\varphi } (m+1,0)=\operatorname {\varphi } (m,1)$

$\operatorname {\varphi } (m+1,n+1)=\operatorname {\varphi } (m,\operatorname {\varphi } (m+1,n))$

Abgesehen von der unterschiedlichen Nomenklatur gibt es hier einen zusätzlichen Faktor 2. Gründliche Quellenarbeit sieht anders aus. Falls sich in nächster Zeit nicht jemand die Mühe macht, den Artikel zu überarbeiten (ich selber kann das nicht, dazu fehlen mir die Fachkenntnisse – auch wenn ich nicht ganz ahnungslos bin), schlage ich vor, den Artikel zur Abwahl des Exzellenz-Status zu stellen. --Feldkurat Katz (Diskussion) 17:19, 15. Aug. 2014 (CEST)

Vorschlag: eine weitere Fußnote (2) unter Wertetabelle

Feld a(5,2) = a(4,a(5,1))²

² damit man sich einen Begriff machen kann, das ist eine Zahl mit etwa 10 hoch 19729 Dezimalstellen (es gäbe in unfaßbar vielen Universen ähnlich unserem (etwa 10 hoch 1000, um einige Trilliarden mehr oder weniger wollen wir uns nicht streiten) nicht genug Papier, um sie aufzuschreiben)

Gerrit 77.64.252.70 13:57, 3. Mai 2015 (CEST)

1926 und Definition von Péter

„[…] eine 1926 von Wilhelm Ackermann gefundene […]“ – Gibt es Belege dafür, dass sie 1926 gefunden wurde? Ackermanns Ergebnis wird 1926 von David Hilbert erwähnt, das muss aber nicht heißen, dass er die Funktion nicht noch früher gefunden hat. In der Schrift heißt es in einer Fußnote: „Vortrag, gehalten am 4. Juni 1925 […].“ Unter der Voraussetzung, dass die Stelle über Ackermann nicht nachträglich ergänzt wurde, lag Hilbert dieses Ergebnis also bereits 1925 vor. Und – who knows? – vielleicht fand er die Funktion noch früher. An der Formulierung „Ebenfalls 1926 konstruierte Ackermann eine Funktion, die diese Vermutung widerlegt, und veröffentlichte sie 1928“ ist auch problematisch, dass nicht klar ist, ob die Funktion, die er 1928 veröffentlichte, wirklich dieselbe ist wie die, die er 1926 (oder noch früher) fand, oder eine Abwandlung. Die in der Arbeit von Hilbert erwähnte ist nämlich φ mit φ_n(a, b) = a⁽ⁿ⁾b (⁽ⁿ⁾ sei der hypern-Operator), dagegen gilt für die 1928 veröffentlichte Funktion:

$a^{(n)}b={\begin{cases}\varphi (a,b,n-1)&1\leq n\leq 3\\\varphi (a,b-1,n-1)&n\geq 4\end{cases}}$

Die „Definition von Péter“ stammt eigentlich von Raphael M. Robinson, beruht aber auf der von Péter. -- IvanP (Diskussion) 14:31, 19. Mär. 2016 (CET)

Berechnung von: $\varphi (10,2,3)\,$

$\varphi (10,2,3)\,=10\uparrow \uparrow 2=10\uparrow 10$

$\varphi (10,2,3)\,=\varphi (10,\varphi (10,1,3)\,,2)\,=\varphi (10,\varphi (10,\varphi (10,0,3)\,,2)\,,2)\,=\varphi (10,\varphi (10,10,2)\,,2)\,=10\uparrow 10\uparrow 10$

Wo ist mein Denkfehler? (nicht signierter Beitrag von 141.20.50.81 (Diskussion) 15:01, 30. Jan. 2017 (CET))

Ich vermute, das liegt an den im Abschnitt eins hier darüber angesprochenen unterschiedlichen Definitionen von $\varphi$. -- HilberTraum (d, m) 19:19, 30. Jan. 2017 (CET)

"einfachere" Version der Ackermannfunktion von Rózsa Péter

Die Ackermannfunktion wird vorne leicht verständlich so definiert:

Die Ackermannfunktion, notiert als $\varphi$, ist also eine Funktion, die die folgenden Gleichungen erfüllt: $\varphi (a,b,0)=a+b\,$ $\varphi (a,b,1)=a\cdot b$ $\varphi (a,b,2)=a^{b}\,$ $\ldots$

Wie erhalte ich nun mit der "einfachere" Version von Péter mit zwei Parametern z. B. das Produkt zweier Zahlen? Da sie ja auch als "die" Ackermanfunktion ("in einer einfacherern Version") definiert ist, muss es also (n,m) abhängig von (a,b) so geben, dass seine Funktion (a ist hier schon als Paramtername von phi vergeben) Péter(n,m) == phi(a,b,1).

Da das vermutlich allgemein nicht geht (für jeden "dritten" Parameter von phi), wieso ist dann die Péter'sche Funktion auch "die" "Ackermannfunktion"?

Oder muss man vorne im Artikel besser zwischen "der" und "einer" Ackermannfunktion unterscheiden?

--AchimP (Diskussion) 15:54, 31. Okt. 2018 (CET)

Widerspruch in 'Entstehungsgeschichte'?

David Hilberts Vermutung wird genannt und erklärt. Dabei klingt es durch die Ausdrucksweise m.E. so, als sei dies Fakt: ... bedeutet dies .... Dies trifft auf nahezu alle in der Praxis vorkommenden Funktionen zu. (wenn man nicht genau liest und nahezu ignoriert). Jetzt habe ich schon zwei einhalb (falsche) Aussagen geschluckt und glaube die Vermutung schon.

Dann folgt die Aussage, die Vermutung wurde durch Ackermann widerlegt. Das ist m.E. so ziemlich verwirrend (bzw. es liest sich nicht so rund).

Der Klarheit halber würde ich daher die Vermutung im Konjunktiv formulieren:

Vereinfacht bedeutete dies, dass sich jede durch einen Computer berechenbare Funktion aus einigen wenigen, sehr einfachen Regeln zusammensetzen ließe und dass sich die Dauer der Berechnung im Voraus abschätzen ließe. Für die meisten in der Praxis vorkommenden Funktionen träfe diese Vermutung auch zu.

Doch 1926 konstruierte ...

Ansonsten super Artikel!! --H3xc0d3r (Diskussion) 18:46, 6. Jul. 2019 (CEST)

Exzellent?

Liebe Community, aus meiner Sicht erfüllt der Artikel nicht (mehr) die heutigen Standards für exzellente Artikel. Er mag als lesenswert durchgehen, aber es fehlt zum Beispiel an zu vielen Stellen an Einzelnachweisen. Ich bin aber für jegliche Diskussionen offen, und möchte der Autorenschaft die Gelegenheit geben, ihre Gedanken einzubringen. Dennoch ziehe ich in Erwägung, in den kommenden Wochen einen Abwahlantrag zu stellen. Liebe Grüße -- Googolplexian (Diskussion) 16:00, 3. Okt. 2023 (CEST)

Abwahl bei KALP (Ergebnis: Verlust der Auszeichnung)

Hallo zusammen, der Artikel wurde 2004 ausgezeichnet und erfüllt nicht mehr die Standards eines exzellenten Artikels. Eines der größten Probleme ist die Belegsituation. Meine Nachricht auf der Diskussionsseite blieb für einige Wochen nicht beantwortet. Daher leider  keine Auszeichnung. Liebe Grüße -- Googolplexian (Diskussion) 10:58, 20. Jan. 2024 (CET)

Hab gerade mal versucht, einige Quellen zu ergänzen, bin aber leider nicht weit gekommen. Zu Hilberts ursprünglicher Annahme, alle Funktionen seien primitiv rekursiv, hab ich beispielsweise keine gefunden.  keine Auszeichnung --Anagkai (Diskussion) 12:17, 20. Jan. 2024 (CET)

 keine Auszeichnung --Thornard ^Diskussion 19:33, 21. Jan. 2024 (CET)

Hier ist die alte Auszeichnungs-Diskussion: KEA Ackermannfunktion 2004. LG --Andreas Werle (Diskussion) 16:36, 27. Jan. 2024 (CET)

Per eindeutigem Ergebnis hiermit abgewählt --Vive la France2 (Diskussion) 13:47, 2. Feb. 2024 (CET)