Ackermann-funksjon

I rekursjonsteorien er Ackermann-funksjonen (også kjent som Ackermann function-Péter ) et enkelt eksempel på en rekursiv funksjon som ikke er primitiv rekursiv , funnet i 1926 av Wilhelm Ackermann . Det presenteres ofte i formen som er foreslått av matematikeren Rózsa Péter , som en funksjon med to naturlige heltallsparametre som argumenter og som returnerer et naturlig heltall som verdi, vanligvis betegnet med A ( m , n ).

Historie

På 1920-tallet studerte Wilhelm Ackermann og Gabriel Sudan , den gang studenter under David Hilbert , grunnleggende beregning. Sudan er den første som gir et eksempel på en rekursiv, men ikke-rekursiv primitiv funksjon, da kalt Sudan-funksjonen . Rett etter og uavhengig, i 1928 , ga Ackermann ut sitt eget eksempel på en primitiv rekursiv, men ikke-rekursiv funksjon. Opprinnelig betraktet Ackermann en funksjon ϕ ( m , n , p ) avhengig av tre variabler.

Ackermann viste at hans funksjon φ var faktisk en rekursiv funksjon, det vil si en funksjon som en idealisert datamaskinen kan beregne. I On Infinity antok David Hilbert at Ackermanns funksjon ikke var primitiv rekursiv . Denne antagelsen ble etablert av Ackermann selv i artikkelen Zum Hilbertschen Aufbau der reellen Zahlen . On Infinity var Hilberts viktigste artikkel om Foundations of Mathematics , og tjente som hjertet i hans program for å fikse grunnlaget for transfinite tall .

En funksjon av bare to variabler ble gitt senere av Rózsa Péter og Raphael Robinson ; det er sistnevnte som i dag er kjent som Ackermann-funksjonen.

Definisjon

Ackermann-Péter-funksjonen er definert rekursivt som følger:

A (m, n) = {\ begin {cases} n + 1 & {\ mbox {si}} m = 0 \\ A (m-1,1) & {\ mbox {si}} m> 0 {\ mbox {et}} n = 0 \\ A (m-1, A (m, n-1)) & {\ mbox {si}} m> 0 {\ mbox {et}} n> 0. \ end { saker}}

Med andre ord :

A (0, n) = n + 1 \,

A (m + 1.0) = A (m, 1) \,

A (m + 1, n + 1) = A (m, A (m + 1, n)) \,

Vi viser da at:

{\ displaystyle A (1, n) = 2 + (n + 3) -3}

{\ displaystyle A (2, n) = 2 \ ganger (n + 3) -3}

{\ displaystyle A (3, n) = 2 ^ {n + 3} -3}

{\ displaystyle A (4, n) = 2 ^ {2 ^ {2 ^ {\ cdots ^ {2}}}} - 3}

med ( n + 3) to stablet, bemerket også ved hjelp av Knuths itererte kraftnotasjon .

{\ displaystyle 2 \ uparrow \ uparrow (n + 3) -3}

{\ displaystyle A (5, n) = 2 \ uparrow \ uparrow (2 \ uparrow \ uparrow (2 \ uparrow \ uparrow (\ cdots \ uparrow \ uparrow 2))) - 3}

med ( n + 3) to, også bemerket .

{\ displaystyle 2 \ uparrow \ uparrow \ uparrow (n + 3) -3}

og mer generelt:

A (m, n) = 2 \ oppover ^ {{(m-2)}} (n + 3) -3

Ackermann foreslo opprinnelig denne funksjonen med tre parametere:

{\ displaystyle {\ begin {cases} \ phi (m, n, 0) = m + n \\\ phi (m, 0, p + 1) = \ alpha (m, p) = {\ begin {cases} 0, & {\ text {si}} p = 0 \\ 1, & {\ text {si}} p = 1 \\ m, & {\ text {si}} p \ geq 2 \ end {cases}} \\\ phi (m, n + 1, p + 1) = \ phi (m, \ phi (m, n, p + 1), p) \ end {cases}} \, \!}

Den tilfredsstiller følgende bånd:

\ phi (a, b, 0) = a + b \,

\ phi (a, b, 1) = a \ cdot b

\ phi (a, b, 2) = a ^ {b} \,

og, mer generelt, hvis er definert av ${\ displaystyle f_ {n}}$

{\ displaystyle f_ {n} (c) = \ phi (a, c, n)}

${\ displaystyle \ phi (a, b, n + 1)}$ er $b th$ iterert fra i ${\ displaystyle f_ {n}}$ ${\ displaystyle \ alpha (a, n)}$

Verditabell

Verdier av A ( m , n )

m \ n	0	1	2	3	4	ikke
0	1	2	3	4	5	n + 1
1	2	3	4	5	6	n + 2
2	3	5	7	9	11	2 n + 3
3	5	1. 3	29	61	125	2 n + 3 - 3
4	1. 3	65533	2 65536 - 3	A (3, 2 65536 - 3)	A (3, A (4, 3))	2 2 ... 2 - 3 ( n + 3 termer)
5	65533	A (4, 65533)	A (4, A (5, 1))	A (4, A (5, 2))	A (4, A (5, 3))	A (4, A (5, n-1))
6	A (5, 1)	A (5, A (5, 1))	A (5, A (6, 1))	A (5, A (6, 2))	A (5, A (6, 3))	A (5, A (6, n-1))

Epistemologisk betydning

Den eneste operasjonen som utføres i løpet av Ackermann-funksjonen er tillegg av 1 (når m er null). Til tross for dette vokser denne funksjonen ekstremt raskt: A (4.2) har allerede 19 729 sifre, og er mye mer enn det estimerte antall atomer i universet. Denne ekstreme veksten kan utnyttes for å vise at funksjonen f definert av f ( n ) = A ( n , n ) vokser raskere enn noen primitiv rekursiv funksjon og dermed at A ikke er en.

Dette er likevel definerbar primitiv rekursjon av høyere orden ( T-systemet til Gödel og dets utvidelser). Den kan også beregnes av en Turing-maskin . Ackermanns funksjon er derfor et eksempel på en rekursiv funksjon, men ikke en primitiv rekursiv funksjon. Dette er kanskje det mest siterte eksemplet på en slik funksjon (spesielt hos Knuth ).

Ackermanns funksjon viser at begrepet beregnbarhet introdusert av de eneste primitive rekursive funksjonene ikke samsvarer med den mest generelle forestillingen om beregnbarhet, nemlig Kirkens avhandling . Ackermanns funksjon kan faktisk beregnes i betydningen Turing og Church, men ikke av en primitiv rekursiv funksjon.

Fra et historisk synspunkt er det interessant å merke seg at de første programmererne som brukte Fortran hevdet uten bevis at den hadde kompleksiteten av rekursive funksjoner. For å gi bevis , foreslo logikeren Rice i 1965 et program i Fortran (selvfølgelig ikke rekursivt) som beregnet Ackermann-funksjonen.

Gjensidig

Det omvendte av Ackermanns funksjon brukes også. Siden funksjonen f definert av f ( n ) = A ( n , n ) som tidligere ble ansett, virkelig vokser veldig raskt, vokser dens gjensidighet veldig veldig sakte. Det vises spesielt i algoritmer for å uttrykke kompleksitet . I dette området bemerkes det ofte . Det finnes for eksempel i analysen av visse datastrukturer som Union-Find , i en algoritme for beregning av det spennende treet med minimal vekt og i algoritmisk geometri . Det kan defineres ganske enkelt uten å kalle Ackermann-funksjonen, ved å definere det inverse Ackermann-hierarkiet (som også viser den itererte logaritmen ). ${\ displaystyle \ alpha (n)}$

Praktiske applikasjoner

Ettersom Ackermanns funksjon krever mye beregning selv for små innganger, blir den noen ganger brukt som et testprogram for implementering av et programmeringsspråk: spesielt bruker den rekursjon på en veldig krevende måte , så vel som søstrene fib ( Fibonacci-sekvens ) og tak ( Takeuchi-funksjon ).

I tillegg til å direkte teste ytelsen til et programmeringsspråk, har Ackermanns funksjon blitt brukt som et eksempel for å studere programtransformasjoner og optimaliseringer, spesielt innen programspesialisering og delvis evaluering. ( In ) .

Referanser

(i) Cristian Calude, Solomon Marcus og Ionel Tevy, "The første eksempel på en rekursiv funksjon qui er ikke primitive rekursiv" Historia Math. , vol. 6, nr . 4, 1979 , s. 380-384 .
(de) David Hilbert , “ Über das Unendliche ” , Mathematische Annalen , vol. 95,1926, s. 161-190 ( les online ), trad. : (no) On the infinite og André Weil , " On the infinite ", Acta Mathematica , vol. 48, n bein 1-2,1926, s. 91-122 ( DOI 10.1007 / BF02629757 ).
(De) Wilhelm Ackermann , " Zum Hilbertschen Aufbau der reellen Zahlen " , Mathematische Annalen , vol. 99,1928, s. 118-133 ( les online ).
(de) Wilhelm Ackermann , " Zum Hilbertschen Aufbau der reellen Zahlen " , Mathematische Annalen , vol. 99,1928, s. 118-133 ( les online ), s. 120
HG Ris, Rekursjon og Iterasjon , Com. ACM, vol. 8, 1965, s. 114-115 leses online .
Gabriel Nivasch, " Invers Ackermann uten smerte " ,2009.
Raimund Seidel, “ Understanding the inverse Ackermann function ” , på 22. europeiske workshop om beregningsgeometri ,2006.
(i) Yanhong Liu og A. Scott D. Stoller, " Optimizing Ackermanns Function by Incrementalization " Workshop on Partial Evaluation and Semantics-Based Program Manipulation , 2003 .

Se også

Relaterte artikler

Eksterne linker

Implementering på forskjellige programmeringsspråk på rosettacode.org
The Great Numbers Race av Scott Aaronson , oversatt på smwhr-bloggen, og den originale versjonen: Hvem kan nevne det største tallet? (1999), et essay om begrepet stort antall.