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):

A(m,n)={\begin{cases}n+1&{\mbox{ se }}m=0\\A(m-1,1)&{\mbox{ se }}m>0{\mbox{ kaj }}n=0\\A(m-1,A(m,n-1))&{\mbox{ se }}m>0{\mbox{ kaj }}n>0\end{cases}}

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:

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

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

2\uparrow ^{m+1}3=2\uparrow ^{m}4

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×10¹⁹⁷²⁸, 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	$n+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.

	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⁽ⁿ⁺³⁾ - 3
4	13	65533	2⁶⁵⁵³⁶ - 3	${2^{2^{65536}}}-3$	${2^{2^{2^{65536}}}}-3$	${\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} -3\\{n+3}{\mbox{ da 2 }}\end{matrix}}$
5	65533	${\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} -3\\65536{\mbox{ da 2 }}\end{matrix}}$	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) = 2⁶⁵⁵³⁶-3 kiu estas tro granda nombro.

Vastigaĵo

*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 $\pm i\infty$ . 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 retroĵeto, f⁻¹, kreskas tre malrapide. Ĉi tiu inversa akermana funkcio f⁻¹ estas kutime skribata kiel α. Fakte, α(n) estas malpli granda ol 5 por ĉiu konjektebla eniga n, pro tio ke A(4, 4) estas proksimume $2^{2^{10^{19729}}}$ . Se la eniga valoro estas rilatanta al iu iuj valoroj de la reala universo, α(n) ofte povas esti estimita kiel estante 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:

\alpha (m,n)=\min\{i\geq 1:A(i,\lfloor m/n\rfloor )\geq \log _{2}n\}.

Ĉ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, log₂ 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(4ⁿ⁺¹). La kalkulado de A(3, 1) en la ekzemplo pli supre prenas 16=4² 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×2ⁿ-3 estas uzataj por optimumigo de la rikuro.

Vidu ankaŭ

Eksteraj ligiloj

Eric W. Weisstein, Akermana funkcio en MathWorld.
Paul E. Black, Akermana funkcio en la vortaro de algoritmoj kaj datumaj strukturoj de NIST
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 Arkivigite je 2008-03-17 per la retarkivo Wayback Machine
Gabriel Nivasch, Inversa akermana funkcio Arkivigite je 2011-09-30 per la retarkivo Wayback Machine
Raimund Seidel, Inversa akermana funkcio
Funkcioj similaj al la inversa akermana funkcio Arkivigite je 2008-12-04 per la retarkivo Wayback Machine
.
.
.
. Alirita 2006-06-13.
Ekzemplo: eksplicita memoranta funkcia versio de akermana funkcio, realigita en Pl/SQL
Etalonoj de rapideco Arkivigite je 2004-08-24 per la retarkivo Wayback Machine