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.

Enhavo

1 Difino
2 Uzo
3 Propraĵoj
4 Tabelo de valoroj
5 Elvolvado
6 Vastigaĵo
7 Inverso
8 Uzo kiel etalono
9 Vidu ankaŭ
10 Eksteraj ligiloj

Difino[redakti]

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 iu kvanto de ripetoj atingas nulon. En aliaj vortoj, en ĉiu okazo la paro (m, n) malgrandiĝas en la leksikografia ordo. Tamen, kiam m malgrandiĝas, n povas pligrandiĝi grande.

La akermana funkcio povas ankaŭ esti esprimita nerikure:

Per hiperoperatoro:

A(m, n) = hyper(2, m, n + 3) - 3

Per la indekas versio de supren-saga skribmaniero de Knuth:

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

Per ĉenita saga skribmaniero 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[redakti]

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[redakti]

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[redakti]

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 havi estas difinitaj, ekzemple 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[redakti]

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[redakti]

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[redakti]

Pro tio ke la funkcio f (n) = A(n, n) kreskas tre rapide, ĝia retroĵeto, f^-1, 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[redakti]

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.