In der Berechenbarkeitstheorie ist die Funktion von Ackermann, genannt nach Wilhelm Ackermann, eines der einfachsten und am frühsten entdeckten Beispiele einer berechenbaren Gesamtfunktion, die rekursiv nicht primitiv ist. Alle primitiven rekursiven Funktionen sind ganz und berechenbar, aber die Funktion von Ackermann illustriert, dass nicht alle berechenbaren Gesamtfunktionen rekursiv primitiv sind.

Nach der Veröffentlichung von Ackermann seiner Funktion (der drei Argumente der natürlichen Zahl hatte) haben viele Autoren es modifiziert, um verschiedenen Zwecken anzupassen, so dass heute "sich die Funktion von Ackermann" auf einige von zahlreichen Varianten der ursprünglichen Funktion beziehen kann. Eine allgemeine Version, die Zwei-Argumente-Ackermann-Péter-Funktion, wird wie folgt für natürliche Zahlen M und n definiert:

:

\begin {Fälle }\

n+1 & \mbox {wenn} M = 0 \\

(m-1, 1) & \mbox {wenn} m> 0 \mbox {und} n = 0 \\

(m-1, (M, n-1)) & \mbox {wenn} m> 0 \mbox {und} n> 0.

\end {Fälle }\

</Mathematik>

Sein Wert wächst schnell sogar für kleine Eingänge. Zum Beispiel (4,2) ist eine ganze Zahl von 19,729 dezimalen Ziffern.

Geschichte

Gegen Ende der 1920er Jahre studierten die Mathematiker Gabriel Sudan und Wilhelm Ackermann, Studenten von David Hilbert, die Fundamente der Berechnung. Sowohl Sudan als auch Ackermann wird das Entdecken berechenbarer Gesamtfunktionen zugeschrieben (genannt einfach "rekursiv" in einigen Verweisungen), die rekursiv nicht primitiv sind. Sudan hat die kleiner bekannte Funktion von Sudan dann kurz später und unabhängig 1928 veröffentlicht, Ackermann hat seine Funktion veröffentlicht. Die Drei-Argumente-Funktion von Ackermann wird solch definiert, dass für p = 0, 1, 2, sie die grundlegenden Operationen der Hinzufügung, Multiplikation und exponentiation als wieder hervorbringt

:::

und für p> 2 erweitert es diese grundlegenden Operationen in einem Weg, der zufällig expressible in der-Pfeil-Notation von Knuth als ist

:

(Beiseite von seiner historischen Rolle als total-computable-but-not-primitive-recursive Funktion, wie man sieht, erweitert die ursprüngliche Funktion von Ackermann die grundlegenden arithmetischen Operationen außer exponentiation, obwohl nicht so nahtlos, wie Varianten der Funktion von Ackermann tun, die zu diesem Zweck — wie die Hyperoperationsfolge von Goodstein spezifisch entworfen werden.)

In Auf dem Unendliche hat David Hilbert Hypothese aufgestellt, dass die Funktion von Ackermann rekursiv nicht primitiv war, aber es war Ackermann, der persönliche Sekretär von Hilbert und ehemaliger Student, der wirklich die Hypothese in seiner Zeitung Auf dem Aufbau von Hilbert der Reellen Zahlen bewiesen hat. Auf dem Unendliche war das wichtigste Papier von Hilbert auf den Fundamenten der Mathematik, als das Herz des Programms von Hilbert dienend, um das Fundament von transfiniten Zahlen durch das Gründen von ihnen auf begrenzten Methoden zu sichern.

Rózsa Péter und Raphael Robinson haben später eine Zwei-Variablen-Version der Funktion von Ackermann entwickelt, die bevorzugt von vielen Autoren geworden ist.

Definition und Eigenschaften

Die ursprüngliche Drei-Argumente-Funktion von Ackermann wird rekursiv wie folgt für natürliche Zahlen M, n, und p definiert:

:

\varphi (M, n, 0) = M + n \\

\varphi (M, 0, 1) = 0 \\

\varphi (M, 0, 2) = 1 \\

\varphi (M, 0, p) = M &\\Text {für} p> 2 \\

\varphi (M, n, p) = \varphi (M, \varphi (M, n-1, p), p - 1) &\\Text {für} n> 0 \text {und} p> 0.

\end {Fälle }\\, \! </Mathematik>

Der verschiedenen Zwei-Argumente-Versionen wird diejenige, die von Péter und Robinson entwickelt ist (hat "die" Funktion von Ackermann durch einige Autoren genannt), für natürliche Zahlen M und n wie folgt definiert:

:\begin {Fälle }\n+1 & \mbox {wenn} M = 0 \\(m-1, 1) & \mbox {wenn} m> 0 \mbox {und} n = 0 \\(m-1, (M, n-1)) & \mbox {wenn} m> 0 \mbox {und} n> 0.\end {Fälle }\</Mathematik>

Es kann nicht sofort offensichtlich sein, dass die Einschätzung dessen immer endet. Jedoch wird der recursion begrenzt, weil in jeder rekursiven Anwendung entweder M Abnahmen, oder M dasselbe und N-Abnahmen bleibt. Jedes Mal, dass n Null, M Abnahmen erreicht, so erreicht M schließlich Null ebenso. (Ausgedrückt mehr technisch in jedem Fall nimmt das Paar (M, n) in der lexikografischen Ordnung auf Paaren ab, die ein gut bestellender gerade wie die Einrichtung von einzelnen natürlichen Zahlen ist; das bedeutet, dass man in der Einrichtung ungeheuer oft in der Folge nicht hinuntergehen kann.) Jedoch, wenn M abnehmen, gibt es nicht gebunden ober, wie viel n vergrößern kann — und es häufig außerordentlich zunehmen wird.

Die Funktion von Péter-Ackermann kann auch in Bezug auf verschiedene andere Versionen der Funktion von Ackermann ausgedrückt werden:

• die mit einem Inhaltsverzeichnis versehene Version der-Pfeil-Notation von Knuth (erweitert zu Indizes der ganzen Zahl -2):

:: (M, n) =

Der:The-Teil der Definition A (M, 0) = (m-1, 1) entspricht

• Hyper-Maschinenbediener:

:: (M, n) = hyper (2, M, n + 3)  3.

• Conway hat Pfeil-Notation gekettet:

:: (M, n) = (2  (n+3)  (M  2))  3 für m> 2

:hence

:: 2  n  M = (m+2, n-3) + 3 für n> 2.

: (n=1 und n=2 würde (M, 2) = 1 und (M, 1) = 1 entsprechen, der logisch hinzugefügt werden konnte.)

Für kleine Werte der M wie 1, 2, oder 3, wächst die Funktion von Ackermann relativ langsam in Bezug auf n (höchstens exponential). Für die M  4, jedoch, wächst es viel schneller; sogar (4, 2) ist ungefähr 2, und die dezimale Vergrößerung (4, 3) ist durch jedes typische Maß sehr groß.

Wenn wir die Funktion f (n) = definieren (n, n), der sowohl M als auch n zur gleichen Zeit vergrößert, haben wir eine Funktion einer Variable, die jede primitive rekursive Funktion, einschließlich sehr schnell wachsender Funktionen wie die Exponentialfunktion, die Factorial-Funktion, mehr - und Superfactorial-Funktionen überragt, und sogar definierte Verwenden--Pfeil-Notation von Knuth fungiert (außer, wenn der mit einem Inhaltsverzeichnis versehene-Pfeil verwendet wird).

Dieses äußerste Wachstum kann ausgenutzt werden, um zu zeigen, dass f, der auf einer Maschine mit dem unendlichen Gedächtnis wie eine Maschine von Turing offensichtlich berechenbar ist und auch eine berechenbare Funktion ist, schneller wächst als jede primitive rekursive Funktion und deshalb rekursiv nicht primitiv ist. In einer Kategorie mit exponentials, mit dem Isomorphismus (in der Informatik wird das genannt mit Currysoße zubereitend), kann die Funktion von Ackermann über primitiven recursion über höherwertigen functionals wie folgt definiert werden:

:

\begin {Reihe} {lcl }\

\operatorname {Ack} (0) & = & \operatorname {Succ} \\

\operatorname {Ack} (m+1) & = & \operatorname {Iter} (\operatorname {Ack}) (M)

\end {ordnen }\

</Mathematik>

wo Succ die übliche Nachfolger-Funktion ist und Iter durch primitiven recursion ebenso definiert wird:

:\begin {Reihe} {lcl }\

\operatorname {Iter} (f) (0) & = & f (1) \\

\operatorname {Iter} (f) (n+1) & = & f (\operatorname {Iter} (f) (n)).

\end {ordnen }\</Mathematik>

Ein interessanter Aspekt der Funktion von Ackermann ist, dass die einzigen arithmetischen Operationen, die sie jemals verwendet, Hinzufügung und Subtraktion 1 sind. Seine Eigenschaften kommen allein aus der Macht von unbegrenztem recursion. Das deutet auch an, dass seine Laufzeit mindestens zu seiner Produktion proportional ist, und auch äußerst riesig ist auch. In der Aktualität für die meisten Fälle ist die Laufzeit viel größer als die Produktion; sieh unten.

Tisch von Werten

Die Computerwissenschaft der Funktion von Ackermann kann in Bezug auf einen unendlichen Tisch neu formuliert werden. Wir legen die natürlichen Zahlen entlang der Spitzenreihe. Um eine Zahl im Tisch zu bestimmen, nehmen Sie die Zahl sofort nach links, dann schlagen Sie die erforderliche Zahl in der vorherigen Reihe an der Position nach, die durch die gerade genommene Zahl gegeben ist. Wenn es keine Zahl an seiner linken Seite gibt, schauen Sie einfach auf die Säule angeführt "1" in der vorherigen Reihe. Hier ist ein kleiner ober verlassener Teil des Tisches:

Die Zahlen verzeichnet hier in einer rekursiven Verweisung sind sehr groß und können in einer anderen Form nicht leicht in Notenschrift geschrieben werden.

Trotz der großen Werte, die in dieser frühen Abteilung des Tisches vorkommen, sind einige noch größere Zahlen wie die Zahl von Graham definiert worden, die mit keiner kleinen Anzahl von Pfeilen von Knuth geschrieben werden kann. Diese Zahl wird mit einer Technik gebaut, die der Verwendung der Funktion von Ackermann zu sich rekursiv ähnlich ist.

Das ist eine Wiederholung des obengenannten Tisches, aber mit den Werten, die durch den relevanten Ausdruck aus der Funktionsdefinition ersetzt sind, um das Muster klar zu zeigen:

Vergrößerung

Um zu sehen, wie die Funktion von Ackermann so schnell wächst, hilft sie, einige einfache Ausdrücke mit den Regeln in der ursprünglichen Definition auszubreiten. Zum Beispiel können wir folgendermaßen völlig bewerten:

:

(1,2) & = (0, (1, 1)) \\

& = (0, (0, (1, 0))) \\

& = (0, (0, (0, 1))) \\

& = (0, (0, 2)) \\

& = (0, 3) \\

& = 4.

\end {richten} </Mathematik> {aus}

Zu demonstrieren, wie 's Berechnung auf viele Schritte und auf eine Vielzahl hinausläuft:

:

(4, 3) & = (3, (4, 2)) \\

& = (3, (3, (4, 1))) \\

& = (3, (3, (3, (4, 0)))) \\

& = (3, (3, (3, (3, 1)))) \\

& = (3, (3, (3, (2, (3, 0))))) \\

& = (3, (3, (3, (2, (2, 1))))) \\

& = (3, (3, (3, (2, (1, (2, 0)))))) \\

& = (3, (3, (3, (2, (1, (1, 1)))))) \\

& = (3, (3, (3, (2, (1, (0, (1, 0))))))) \\

& = (3, (3, (3, (2, (1, (0, (0, 1))))))) \\

& = (3, (3, (3, (2, (1, (0, 2)))))) \\

& = (3, (3, (3, (2, (1, 3))))) \\

& = (3, (3, (3, (2, (0, (1, 2)))))) \\

& = (3, (3, (3, (2, (0, (0, (1, 1))))))) \\

& = (3, (3, (3, (2, (0, (0, (0, (1, 0)))))))) \\

& = (3, (3, (3, (2, (0, (0, (0, (0, 1)))))))) \\

& = (3, (3, (3, (2, (0, (0, (0, 2)))))) \\

& = (3, (3, (3, (2, (0, (0, 3))))) \\

& = (3, (3, (3, (2, (0, 4))))) \\

& = (3, (3, (3, (2, 5)))) \\

& =... \\

& = (3, (3, (3, 13))) \\

& =... \\

& = (3, (3, 65533)) \\

& =... \\

& = (3, 2^ {65536} - 3) \\

& =... \\

& = 2^ {2^ {\overset {65536} {}}} - 3. \\

\end {richten} </Mathematik> {aus}

Schriftlich als eine Macht 10 ist das zu 10 grob gleichwertig.

Gegenteil

Da die Funktion f (n) = (n, n) betrachtet oben sehr schnell wächst, wächst seine umgekehrte Funktion, f, sehr langsam. Dieses Gegenteil Funktion von Ackermann f wird gewöhnlich durch α angezeigt. Tatsächlich α ist (n) weniger als 5 für jede praktische Eingangsgröße n, da (4, 4) auf der Ordnung dessen ist.

Dieses Gegenteil erscheint in der Zeitkompliziertheit von einigen Algorithmen, wie die Datenstruktur des zusammenhanglosen Satzes und der Algorithmus von Chazelle für minimale Überspannen-Bäume. Manchmal werden die ursprüngliche Funktion von Ackermann oder andere Schwankungen in diesen Einstellungen verwendet, aber sie alle wachsen in ähnlich hohen Tempos. Insbesondere einige modifizierte Funktionen vereinfachen den Ausdruck durch das Beseitigen der 3 und ähnlichen Begriffe.

Eine Zwei-Parameter-Schwankung des Gegenteils Funktion von Ackermann kann wie folgt definiert werden, wo die Fußboden-Funktion ist:

:

Diese Funktion entsteht in genaueren Analysen der Algorithmen, die oben erwähnt sind, und gibt einen mehr raffinierten fristgebundenen. In der Datenstruktur des zusammenhanglosen Satzes vertritt M die Zahl von Operationen, während n die Zahl der Elemente vertritt; im minimalen Überspannen-Baumalgorithmus vertritt M die Zahl von Rändern, während n die Zahl von Scheitelpunkten vertritt.

Mehrere ein bisschen verschiedene Definitionen von α (M, n) bestehen; zum Beispiel wird Klotz n manchmal durch n ersetzt, und die Fußboden-Funktion wird manchmal durch eine Decke ersetzt.

Andere Studien könnten eine umgekehrte Funktion von derjenigen definieren, wo M auf eine Konstante gesetzt, solch wird, dass das Gegenteil für eine besondere Reihe gilt.

Gebrauch als Abrisspunkt

Die Funktion von Ackermann, wegen seiner Definition in Bezug auf äußerst tiefen recursion, kann als ein Abrisspunkt einer Fähigkeit eines Bearbeiters verwendet werden, recursion zu optimieren. Der erste Gebrauch der Funktion von Ackermann war auf diese Weise durch Yngve Sundblad, Die Funktion von Ackermann. Ein Theoretischer, rechenbetontes und Formel Manipulationsstudie. (BIT 11 (1971), 107119).

Dieses Samenpapier wurde von Brian Wichmann (Mitverfasser des Schleifstein-Abrisspunkts) in einer Trilogie von Papieren aufgenommen, die zwischen 1975 und 1982 geschrieben sind.

Zum Beispiel, ein Bearbeiter, der, im Analysieren der Berechnung (3, 30), ist im Stande, Zwischenwerte wie (3, n) und (2, n) in dieser Berechnung zu sparen, anstatt sie wieder zu rechnen, Berechnung (3, 30) durch einen Faktor von Hunderttausenden beschleunigen kann. Außerdem, wenn (2, n) direkt aber nicht als eine rekursive Vergrößerung der Form (1, (1, geschätzt wird (1... (1, 0)...))), das wird bedeutende Zeitdauer sparen. Das Rechnen (1, n) nimmt in n Zeit in Anspruch. Das Rechnen (2, n) verlangt quadratische Zeit, da es sich zu O (n) ausbreitet, hat Anrufe (1, i) für den verschiedenen ich verschachtelt. Das Rechnen (3, n) verlangt Zeit, die zu 4 proportional ist. Die Berechnung (3, 1) im Beispiel nimmt oben 16 (4) Schritte.

(4, 2) kann durch die einfache rekursive Anwendung der Funktion von Ackermann in keiner lenksamen Zeitdauer vielleicht geschätzt werden. Statt dessen werden Abkürzungsformeln solcher als (3, n) = 8×23 als eine Optimierung verwendet, um einige der rekursiven Anrufe zu vollenden.

Eine praktische Methode, Ackermann ähnliche Funktionen zu schätzen, soll memoization von Zwischenergebnissen verwenden. Ein Bearbeiter konnte diese Technik auf eine Funktion automatisch mit den "Merkzettel-Funktionen von Donald Michie" anwenden.

Zahlen von Ackermann

Im Buch von Zahlen definieren John Horton Conway und Richard K. Guy die Folge von Zahlen von Ackermann, um 11, 2  2, 3  3, usw. zu sein; d. h. die n-te Zahl von Ackermann wird definiert, um nn zu sein (n = 1, 2, 3...), wo mn die-Pfeil-Version von Knuth der Funktion von Ackermann ist.

Die ersten paar Zahlen von Ackermann sind:

:* 11 = 1 = 1,

:* 2  2 = 22 = 2 = 4,

:* 3  3 = 3  3  3 = 3  (333) =

Die vierte Zahl von Ackermann, 4  4, kann in Bezug auf tetration Türme wie folgt geschrieben werden:

:4  4 = 4  4  4  4 = 4  4  (4  4  4  4)

:::

Erklärung: In der mittleren Schicht gibt es einen Turm von tetration, dessen volle Höhe ist und das Endresultat die Spitzenschicht von tetrated 4's ist, wessen volle Höhe der Berechnung der mittleren Schicht gleichkommt. Bemerken Sie, dass über den Größe-Vergleich der einfache Ausdruck 4 bereits einen googolplex überschreitet, so ist die vierte Zahl von Ackermann ziemlich groß.

Wechselweise kann das in Bezug auf exponentiation Türme als geschrieben werden

:::

\left.

\begin {Matrix} 4^ {4^ {\\cdot^ {\\cdot^ {\\cdot^ {\\cdot^ {4}}}}} }\\Ende {Matrix-}\

\right \}\

\left.

\begin {Matrix} 4^ {4^ {\\cdot^ {\\cdot^ {\\cdot^ {4}}}} }\\Ende {Matrix-}\

\right \}\

\dots

\left.

\begin {Matrix} 4^ {4^ {4^4} }\\Ende {Matrix-}\

\right \}\

4,

</Mathematik>

:where die Zahl von Türmen auf der vorherigen Linie (einschließlich des niedrigstwertigen "4") ist

:\left.

\begin {Matrix} 4^ {4^ {\\cdot^ {\\cdot^ {\\cdot^ {\\cdot^ {4}}}}} }\\Ende {Matrix-}\

\right \}\\left.\begin {Matrix} 4^ {4^ {\\cdot^ {\\cdot^ {\\cdot^ {4}}}} }\\Ende {Matrix-}\\right \}\\dots\left.\begin {Matrix} 4^ {4^ {4^4} }\\Ende {Matrix-}\\right \}\4,</Mathematik>:where die Zahl von Türmen auf der vorherigen Linie (einschließlich des niedrigstwertigen "4") ist:\left.\begin {Matrix} 4^ {4^ {\\cdot^ {\\cdot^ {\\cdot^ {4}}}} }\\Ende {Matrix-}\\right \}\\left.\begin {Matrix} 4^ {4^ {\\cdot^ {\\cdot^ {\\cdot^ {4}}}} }\\Ende {Matrix-}\\right \}\\left.\begin {Matrix} 4^ {4^ {4^4} }\\Ende {Matrix-}\\right \}\4,</Mathematik>

wo die Zahl "4" s in jedem Turm, auf jeder der Linien oben, durch den Wert des folgenden Turms an seiner rechten Seite (wie angezeigt, durch eine geschweifte Klammer) angegeben wird.

Funktion von Ackermann auf Programmiersprachen

C

interne Nummer Ackermann (int M, interne Nummer n)

{\

wenn (M == 0) n+1 zurückgeben;

sonst, wenn (n == 0) Ackermann (M 1,1) zurückgeben;

geben Sie sonst Ackermann (m-1, Ackermann (M, n-1)) zurück;

}\

</nowiki> </pre>

Haskell

ack M 0 = ack (M - 1) 1

ack M n = ack (M - 1) (ack M (n - 1)) </nowiki> </pre>

Einleitung

ackermann (0, N, R):-R ist N+1.

ackermann (M, 0, R):-M1 ist m-1,

ackermann (M1,1, R).

ackermann (M, N, R):-M1 ist m-1,

N1 ist n-1,

ackermann (M, N1, R1),

ackermann (M1, R1, R).

</nowiki> </pre>

Ada

fungieren Sie Ackermann (M, n: Ganze Zahl) kehren zurück Ganze Zahl ist

beginnen Sie

wenn M = 0 dann

geben Sie n + 1 zurück;

elsif m> 0 und n = 0 dann

geben Sie Ackermann (M - 1, 1) zurück;

elsif m> 0 und n> 0 dann

geben Sie Ackermann (M - 1, Ackermann (M, n - 1)) zurück;

Ende wenn;

Ende Ackermann;

</nowiki> </pre>

Pascal

Programm ackermann; {vereinbar bis (4,0) }\

Gebrauch crt;

Verfahren leerpar (var M, n:integer);

beginnen Sie

writeln ('ingrese el un numero');

readln (m);

writeln ('ingrese el otro numero');

readln (n);

Ende;

fungieren Sie ackermann (M, n:integer): longint;

beginnen Sie

wenn m=0 dann

ackermann: = n+1

sonst

wenn (m> 0) und (n=0) dann

ackermann: = ackermann (M 1,1)

sonst

wenn (m> 0) und (n> 0) dann

ackermann: = ackermann ((m-1), ackermann (M, n-1));

Ende;

var

M, n:integer;

beginnen Sie

clrscr;

leerpar (M, n);

writeln (ackermann (M, n));

readkey;

Ende.

Pythonschlange

def Ackermann (n, m):

wenn n == 0:

geben Sie m+1 zurück

elif M == 0:

geben Sie Ackermann (n-1,1) zurück

sonst:

geben Sie Ackermann (n-1, Ackermann (n, m-1)) zurück

</nowiki> </pre>

Siehe auch

• Berechenbarkeitstheorie
• Recursion (Informatik)
• Primitive rekursive Funktion
• Verdoppeln Sie recursion

Links

• Eine belebte Funktionsrechenmaschine von Ackermann
• Scott Aaronson, Der kann die größte Zahl nennen? (1999)
• Funktion von Ackermann. Schließt einen Tisch von einigen Werten ein.
• Hyperoperationen: Die Funktion von Ackermann und neue arithmetische Operation
• Die große Anzahl von Robert Munafo beschreibt mehrere Schwankungen auf der Definition von A.
• Gabriel Nivasch, Gegenteil Ackermann ohne Schmerz auf dem Gegenteil Funktion von Ackermann.
• Raimund Seidel, das Gegenteil Funktion von Ackermann (PDF Präsentation) Verstehend.
• Die Funktion von Ackermann, die auf verschiedenen Programmiersprachen, (auf dem Code von Rosetta) geschrieben ist
• Die Funktion von Ackermann (Archiviert am 2009-10-24) - etwas Studie und Programmierung durch Harry J. Smith