Akermana funkcio

En matematiko, akermana funkcio aŭ funkcio de Ackermann-Péter estas funkcio A(m,n) kiu prenas du naturajn nombrojn kiel argumentoj kaj redonas naturan nombron. Vidu artikolon Wilhelm Ackermann.

 Difino 
La akermana funkcio estas difinita rikure por nenegativaj entjeroj m kaj n kiel sekvas (ĉi tiu estas de Rózsa Péter):

Ne estas senpere evidente ke kalkulado de ĉi tiu funkcio ĉiam finiĝas. Tamen la rikuro estas barita ĉar en ĉiu fojo aŭ m malgrandiĝas, aŭ m restas la sama kaj n malgrandiĝas. Ĉiufoje kiam n atingas nulon, m malgrandiĝas, tiel ankaŭ m post iom da ripetoj atingas nulon. En aliaj vortoj, en ĉiu okazo la paro (m, n) malgrandiĝas laŭ la leksikografia ordo. Tamen, kiam m malgrandiĝas, n povas ege pligrandiĝi.

La akermanan funkcion eblas ankaŭ esprimi nerikure:
 Per hiperoperatoro:
 A(m, n) = hyper(2, m, n + 3) - 3

 Per la indeksa versio de notacio de Knuth:


 Per sagoĉena notacio de Conway:
 A(m, n) = (2 → (n+3) → (m-2)) - 3 por m > 2
 de ĉi tie
 2 → n → m = A(m+2,n-3) + 3 por n>2
 (n=1 kaj n=2 devus respektivi al A(m, -2) = -1 kaj A(m, -1) = 1, kiuj povus esti logike adonitaj.)

En la programlingvo C la rekta laŭdifina realigo estas:

unsigned int ak(unsigned int m, unsigned int n)
{
    if (m == 0)
        return n + 1;
    else if (n == 0)
        return ak(m-1, 1);
    else
        return ak(m-1, ak(m, n - 1));
}

 Uzo 

En rikura teorio, la akermana funkcio estas simpla ekzemplo de μ-rikura funkcio (ĝenerala rikura funkcia) kiu estas ne primitive rikura funkcio. Ĝeneralaj rikuraj funkcioj estas ankaŭ sciataj kiel komputeblaj funkcioj. La aro de primitive rikuraj funkcioj estas subaro de la aro de ĝeneralaj rikuraj funkcioj. Akermana funkcio estas ekzemplo kiu montras ke la antaŭa estas severa subaro de la lasta.

 Propraĵoj 

La parto de la difino

 A(m, 0) = A(m-1, 1) respektivas al tio ke


aŭ
 hyper(2, m+1, 3) = hyper(2, m, 4)Por malgrandaj valoroj de m, 1, 2 aŭ 3, la akermana funkcio kreskas relative malrapide kun kresko de n (maksimume eksponente). Por m≥4, tamen, ĝi kreskas multe pli rapide; eĉ A(4, 2) estas proksimume 2×1019728, la rezultoj estas grandaj nombroj. Por m=4 la valoroj povas ankaŭ esti esprimitaj per supereksponento.

Unuargumenta funkcio f(n) = A(n, n), kreskas ankoraŭ multe pli rapide, pli rapide ol A(m, n) por ĉiu konstanta m.

 Tabelo de valoroj 

La sekva tabelo enhavas esprimojn laŭ difino de la funkcio:

  A(m, n) m \ n 0 1 2 3 4 n 0 0+1  1+1  2+1  3+1  4+1   1 A(0,1)  A(0,A(1,0))  A(0,A(1,1))  A(0,A(1,2))  A(0,A(1,3))  A(0, A(1, n-1)) 2 A(1,1)  A(1,A(2,0))  A(1,A(2,1))  A(1,A(2,2))  A(1,A(2,3))  A(1, A(2, n-1)) 3 A(2,1)  A(2,A(3,0))  A(2,A(3,1))  A(2,A(3,2))  A(2,A(3,3))  A(2, A(3, n-1)) 4 A(3,1)  A(3,A(4,0))  A(3,A(4,1))  A(3,A(4,2))  A(3,A(4,3))  A(3, A(4, n-1)) 5 A(4,1)  A(4,A(5,0))  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(6,0))  A(5,A(6,1))  A(5,A(6,2))  A(5,A(6,3))  A(5, A(6, n-1))

La sekva tabelo enhavas la samajn nombrojn kiel la antaŭa tabelo, sed kun la valoroj anstataŭ la esprimoj laŭ la difino. La nombroj listigitaj tamen ĉi tie en rikura formo estas tre granda kaj ne povas esti facile skribitaj per kutimaj manieroj.

{| class=wikitable
! !! colspan=6 | A(m, n)|-
! m \ n! 0
! 1
! 2
! 3
! 4
! n
|-
! 0
| 1 || 2 || 3 || 4 || 5 || n + 1|-
! 1
| 2 || 3 || 4 || 5 || 6 || n + 2 = 2 + (n + 3) - 3|-
! 2
| 3 || 5 || 7 || 9 || 11 || 2n + 3 = 2(n + 3) - 3|-
! 3
| 5 || 13 || 29 || 61 || 125 || 2(n+3) - 3
|-
! 4
| 13 || 65533
| 265536 - 3
| 
| 
| 
|-
! 5
| 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(6, 0))
| A(5, A(6, 1))
| A(5, A(6, 2)) || A(5, A(6, 3)) || A(5, A(6, n-1))
|}

Malgraŭ tio ke nombroj en la tabelo estas grandaj, iuj eĉ pli grandaj nombroj estis difinitaj, ekzemple la nombro de Graham, kiu ne povas esti skribita kiel valoro de la akermana funkcio kun arbitre malgrandaj argumentoj. Ĉi tiu nombro tamen povas esti konstruita per ripeta (64 foje) apliko de funkcio, simila al akermana funkcio.

 Elvolvado 

Oni povas elvolvi valoron de la funkcio por iuj argumentoj, laŭ la difino. Ekzemple, oni povas plene komputi valoron A(1, 2):

A(1,2) = A(0, A(1, 1))
 = A(0, A(0, A(1, 0)))
 = A(0, A(0, A(0, 1)))
 = A(0, A(0, 2))
 = A(0, 3)
 = 4

Por A(4, 3) en iuj ŝtupoj de la elvolvado komencas aperi tre grandaj nombroj:

A(4, 3) = A(3, A(4, 2))
 = A(3, A(3, A(4, 1)))
 = A(3, A(3, A(3, A(4, 0))))
 = A(3, A(3, A(3, A(3, 1))))
 = A(3, A(3, A(3, A(2, A(3, 0)))))
 = A(3, A(3, A(3, A(2, A(2, 1)))))
 = A(3, A(3, A(3, A(2, A(1, A(2, 0))))))
 = A(3, A(3, A(3, A(2, A(1, A(1, 1))))))
 = A(3, A(3, A(3, A(2, A(1, A(0, A(1, 0)))))))
 = A(3, A(3, A(3, A(2, A(1, A(0, A(0, 1)))))))
 = A(3, A(3, A(3, A(2, A(1, A(0, 2))))))
 = A(3, A(3, A(3, A(2, A(1, 3)))))
 = A(3, A(3, A(3, A(2, A(0, A(1, 2))))))
 = A(3, A(3, A(3, A(2, A(0, A(0, A(1, 1)))))))
 = A(3, A(3, A(3, A(2, A(0, A(0, A(0, A(1, 0))))))))
 = A(3, A(3, A(3, A(2, A(0, A(0, A(0, A(0, 1))))))))
 = A(3, A(3, A(3, A(2, A(0, A(0, A(0, 2))))))
 = A(3, A(3, A(3, A(2, A(0, A(0, 3)))))
 = A(3, A(3, A(3, A(2, A(0, 4)))))
 = A(3, A(3, A(3, A(2, 5))))
 = ...
 = A(3, A(3, A(3, 13)))
 = ...
 = A(3, A(3, 65533))
 = ...

La plua elvolvado ne estas montrita, ĉar A(3, 65533) = 265536-3 kiu estas tro granda nombro.

 Vastigaĵo 

500px|eta|A(4,z) en la kompleksa z-ebeno. Estas desegnita niveloj, respektivaj al entjeraj valoroj de Re(A(4,z)) kaj de Im(A(4,z)).
Se konsideri la funkcion f(z)=A(m,z) de variablo z por konstanta natura m, la unuaj tri el ĉi tiuj funkcioj A(1,z), A(2,z), A(3,z) estas analitikaj funkcioj en la tuta z-ebeno, ĉar ili povas esti esprimitaj per elementaj funkcioj kaj do permesas simplan analitikan vastigaĵon por kompleksaj valoroj de la z.

Ne estas ankoraŭ trovita ĉi tia vastigaĵo por f(z)=A(m,z) kun entjera m>3. La bildo prezentas la eblan komprenon de ĉi tia vastigaĵo, kiu restas limigita je . La desegnaĵo indikas ke, eble, la vastigaĵo de A(4,z), analitika en la tuta z-ebeno, estas ne ebla; la analitika vastigaĵo devus havi specialaĵon je z=-5 kaj tranĉon je la reela akso por z<-5. Ĉi tiaj tranĉo kaj specialaĵo aspektas al esti tipaj ankaŭ por la supereksponenta funkcio.

 Inverso 

Pro tio, ke la funkcio f (n) = A(n, n) kreskas tre rapide, ĝia inverso, f−1, kreskas tre malrapide. La kutima notacio por tiu ĉi inversa akermana funkcio f−1 estas α. Fakte, α(n) estas malpli granda ol 5 por ĉiu konjektebla eniga n, pro tio ke A(4, 4) estas proksimume . Se la eniga valoro estas rilata al iuj valoroj de la reala universo, α(n) ofte povas esti taksita kiel konstanto.

Ĉi tiu inversa funkcio aperas en la tempa komplikeco de iuj algoritmoj, ekzemple la disa-ara datumstrukturo kaj algoritmo de Bernard Chazelle por minimuma generanta arbo.

Du-parametra varianto de la inversa akermana funkcio povas esti difinita kiel:

Ĉi tiu funkcio aperas en pli preciza analizo de la algoritmo, kaj donas pli precizan tempan baron. En la disa-ara datumstrukturo, m estas la kvanto de operacioj kaj n estas la kvanto de eroj; en la minimumo generanta arba algoritmo, m estas la kvanto de lateroj kaj n estas la kvanto de verticoj.

Kelkaj malmulte malsamaj difinoj de α(m, n) ekzistas; ekzemple, log2 n estas iam anstataŭigita per n, kaj la planka funkcio estas iam anstataŭigis per plafona funkcio.

 Uzo kiel etalono 

La akermana funkcio, pro ĝia difino kun de ege profunda rikuro, povas esti uzata por provi kiel bona estas la optimumigo de rikuro farata de iu kompililo.

Ekzemple, kompililo kiu, analizinte la kalkulado de A(3, 30), povas konservi interajn valorojn A(3, n) kaj A(2, n) anstataŭ rekomputi ilin, povas akceli la kalkulado de A(3, 30) per faktoro de centoj da miloj. Ankaŭ, se A(2, n) estas komputata rekte sed ne kiel rikura elvolvaĵo A(1, A(1, A(1,...A(1, 0)...))), ĉi tio savas tempon.

Rekta komputo de A(1, n) prenas linearan tempon de n. Rekta komputo de A(2, n) postulas kvadratan tempon, pro tio ke ĝi elvolviĝas al O(n) da nestitaj vokoj de A(1, k) por diversaj k. Komputo de A(3, n) postulas tempon O(4n+1). La kalkulado de A(3, 1) en la ekzemplo pli supre prenas 16=42 paŝojn.

A(4, 2) ne povas esti komputita per simpla rikura laŭ la difino en taŭga daŭro. Anstataŭe, formuloj kiel ekzemple A(3, n) = 8×2n-3 estas uzataj por optimumigo de la rikuro.

 Vidu ankaŭ 

 Granda O
 Rikuro (komputiko)
 Akermana nombro

 Eksteraj ligiloj 


 Scott Aaronson, Kiu povas nomi la plej grandan nombron? (1999)
 Pri akermana funkcia kun tabelo de valoroj
 Hiperoperacioj: akermana funkcio kaj nova aritmetika operacio
 Versioj de akermana funkcio de Robert Munafo priskribas kelkaj variadoj de la difino.
 A(4,2) enhavas 19729 ciferojn 
 Gabriel Nivasch, Inversa akermana funkcio 
 Raimund Seidel, Inversa akermana funkcio
 Funkcioj similaj al la inversa akermana funkcio 




 Ekzemplo: eksplicita memoranta funkcia versio de akermana funkcio, realigita en Pl/SQL
 Etalonoj de rapideco 

Kategorio:Aritmetiko
Kategorio:Grandaj nombroj
Kategorio:Specialaj funkcioj
Kategorio:Teorio de kalkulado
Kategorio:Rekursia teorio