Ackermannova funkce - Ackermann function

v teorie vypočítatelnosti, Ackermannova funkce, pojmenoval podle Wilhelm Ackermann, je jedním z nejjednodušších^[1] a nejdříve objevené příklady a celkový vypočítatelná funkce to není primitivní rekurzivní. Všechny primitivní rekurzivní funkce jsou úplné a vypočítatelné, ale funkce Ackermann ilustruje, že ne všechny celkové vypočítatelné funkce jsou primitivní rekurzivní. Po Ackermannově publikaci^[2] jeho funkce (která měla tři nezáporné celočíselné argumenty) ji mnozí autoři upravili tak, aby vyhovovala různým účelům, takže dnes „funkce Ackermann“ může odkazovat na kteroukoli z mnoha variant původní funkce. Jedna běžná verze, dva argumenty Funkce Ackermann – Péter, je definován takto pro nezáporná celá čísla m a n:

${displaystyle {egin {array} {lcl} operatorname {A} (0, n) & = & n + 1 operatorname {A} (m + 1,0) & = & operatorname {A} (m, 1) operatorname { A} (m + 1, n + 1) & = & operatorname {A} (m, operatorname {A} (m + 1, n)) konec {pole}}}$

Jeho hodnota rychle roste, a to i pro malé vstupy. Například, A(4, 2) je celé číslo 19 729 desetinných míst^[3] (ekvivalent 2⁶⁵⁵³⁶-3 nebo 2²²²²−3).

Dějiny

Na konci 20. let 20. století matematici Gabriel Súdán a Wilhelm Ackermann, studenti David Hilbert, studovali základy výpočtu. Připsány jsou Súdán i Ackermann^[4] s objevováním celkový vypočítatelné funkce (v některých odkazech nazývané jednoduše „rekurzivní“), které nejsou primitivní rekurzivní. Súdán zveřejnil méně známé Súdánská funkce, poté krátce nato a samostatně, v roce 1928, Ackermann zveřejnil svou funkci ${displaystyle varphi}$ (řecké písmeno phi ). Ackermannova funkce se třemi argumenty, ${displaystyle varphi (m, n, p)}$, je definován tak, že pro p = 0, 1, 2, reprodukuje základní operace přidání, násobení, a umocňování tak jako

${displaystyle varphi (m, n, 0) = m + n,}$

${displaystyle varphi (m, n, 1) = m imes n,}$

${displaystyle varphi (m, n, 2) = m ^ {n},}$

a pro p > 2 rozšiřuje tyto základní operace způsobem, který lze srovnávat s hyperoperace:

${displaystyle varphi (m, n, 3) = m [4] (n + 1) ,,!}$

${displaystyle varphi (m, n, p) gtrapprox m [p + 1] (n + 1) {ext {, pro}} p> 3.,!}$

(Kromě své historické role jako totálně vypočítatelné, ale nikoli primitivní rekurzivní funkce je vidět, že Ackermannova původní funkce rozšiřuje základní aritmetické operace nad rámec umocňování, i když ne tak hladce jako varianty Ackermannovy funkce, které jsou speciálně navrženy pro ten účel - jako např Goodstein hyperoperace sekvence.)

v Na nekonečno,^[5] David Hilbert předpokládal, že Ackermannova funkce nebyla primitivní rekurzivní, ale byl to Ackermann, Hilbertův osobní tajemník a bývalý student, který ve své práci hypotézu skutečně prokázal O Hilbertově konstrukci skutečných čísel.^[2][6]

Rózsa Péter^[7] a Raphael Robinson^[8] později vyvinul dvou variabilní verzi Ackermannovy funkce, kterou si oblíbilo mnoho autorů.

Zobecněný hyperoperační sekvence, např. ${displaystyle operatorname {G} (m, a, b) = a [m] b}$, je také verzí funkce Ackermann.^[9]

V roce 1963 R.C. Dolar na základě intuitivní varianty se dvěma proměnnými (F^[10]) na hyperoperační sekvence:^[11]

${displaystyle operatorname {F} (m, n) = 2 [m] n}$.

Ve srovnání s většinou ostatních verzí nemá funkce Buck žádné nepodstatné posuny:

${displaystyle {egin {array} {lr} operatorname {F} (0, n) = 2 [0] n = n + 1 operatorname {F} (1, n) = 2 [1] n = 2 + n operatorname {F} (2, n) = 2 [2] n = 2 imes n operatorname {F} (3, n) = 2 [3] n = 2 ^ {n} operatorname {F} (4, n ) = 2 [4] n = 2 ^ {2 ^ {2 ^ {{} ^ {., ^ {., ^ {., ^ {2}}}}}}} ... konec {pole}} }$

Definice a vlastnosti

Ackermannova původní funkce se třemi argumenty ${displaystyle varphi (m, n, p)}$ je definováno rekurzivně takto pro nezáporná celá čísla m, n, a p:

${displaystyle {egin {array} {lr} varphi (m, n, 0) = m + n varphi (m, 0,1) = 0 varphi (m, 0,2) = 1 varphi (m, 0 , p) = m {ext {for}} p> 2 varphi (m, n, p) = varphi (m, varphi (m, n-1, p), p-1) {ext {for}} n > 0 {ext {and}} p> 0.end {array}}}$

Z různých verzí se dvěma argumenty je ta, kterou vyvinuli Péter a Robinson (někteří autoři ji nazývají „Ackermannovou funkcí“), definována pro nezáporná celá čísla m a n jak následuje:

${displaystyle {egin {array} {lcl} operatorname {A} (0, n) & = & n + 1 operatorname {A} (m + 1,0) & = & operatorname {A} (m, 1) operatorname { A} (m + 1, n + 1) & = & operatorname {A} (m, A (m + 1, n)) konec {pole}}}$

Nemusí být hned zřejmé, že hodnocení ${displaystyle A (m, n)}$ vždy končí. Rekurze je však omezená, protože buď v každé rekurzivní aplikaci m klesá, nebo m zůstává stejný a n klesá. Pokaždé n dosáhne nuly, m klesá, takže m nakonec také dosáhne nuly. (Vyjádřeno technicky, v každém případě dvojice (m, n) klesá v lexikografický řád na párech, což je a dobře objednávající, stejně jako uspořádání jednotlivých nezáporných celých čísel; to znamená, že člověk nemůže klesnout v objednávání nekonečně mnohokrát za sebou.) Nicméně, když m klesá neexistuje žádná horní hranice toho, kolik n se může zvýšit - a často se výrazně zvýší.

Funkci Péter-Ackermann lze také vyjádřit ve vztahu k různým dalším verzím funkce Ackermann:

• hyperoperace:

${displaystyle A (m, n) = {egin {cases} 0 [m] n & {ext {, if}} m = 0 2 [m] (n + 3) -3 & {ext {, if}} m> 0 end {cases}}}$

• hyperoperace, zastoupená v Knuthova nota se šipkou nahoru (rozšířeno na celočíselné indexy ≥ −2):

${displaystyle A (m, n) = {egin {cases} 0uparrow ^ {m-2} n & {ext {, if}} m = 0 2uparrow ^ {m-2} (n + 3) -3 & {ext { , if}} m> 0 end {cases}}}$

• hyperoperace, zastoupená v Conway zřetězená šipka:

${displaystyle A (m, n) = (2ightarrow (n + 3) ightarrow (m-2)) - 3}$ pro ${displaystyle mgeq 3}$

proto

${displaystyle 2ightarrow nightarrow m = A (m + 2, n-3) +3}$ pro ${displaystyle n> 2}$.

(n = 1 a n = 2 bude korespondovat s A(m, −2) = −1 a A(m, −1) = 1, které lze logicky přidat.)

Pro malé hodnoty m jako 1, 2 nebo 3, Ackermannova funkce roste relativně pomalu vzhledem k n (nejvíce exponenciálně ). Pro m ≥ 4, ale roste mnohem rychleji; dokonce A(4, 2) je asi 2×10¹⁹⁷²⁸a desetinné rozšíření A(4, 3) je velmi velká jakýmkoli typickým měřítkem.

Zajímavým aspektem (Péter-) Ackermannovy funkce je, že jedinou aritmetickou operací, kterou kdy používá, je přidání 1. Její rychle rostoucí síla je založena pouze na vnořené rekurzi. To také znamená, že jeho doba chodu je alespoň úměrná jeho výkonu, a proto je také extrémně obrovská. Ve skutečnosti je ve většině případů doba běhu mnohem větší než výstup; viz. níže.

Verze s jedním argumentem F(n) = A(n, n) což zvyšuje obojí m a n zároveň převyšuje každou primitivní rekurzivní funkci, včetně velmi rychle rostoucích funkcí, jako je exponenciální funkce, faktoriální funkce, multi- a superfaktoriální funkce a dokonce i funkce definované pomocí Knuthovy šipky nahoru (kromě případů, kdy je použita indexovaná šipka nahoru). Je to vidět F(n) je zhruba srovnatelný s F_ω(n) v rychle rostoucí hierarchie. Tento extrémní růst lze využít k tomu, aby to ukázal F, což je zjevně vypočítatelné na stroji s nekonečnou pamětí, jako je a Turingův stroj a tak je vypočítatelná funkce, roste rychleji než jakákoli primitivní rekurzivní funkce, a proto není primitivní rekurzivní.

V kategorii s exponenciály pomocí izomorfismu ${displaystyle ((X imes Y) ightarrow Z) cong (Xightarrow (Yightarrow Z))}$ (v informatice se tomu říká kari ) lze Ackermannovu funkci definovat pomocí primitivní rekurze nad funkcionály vyššího řádu takto:

${displaystyle {egin {array} {lcl} operatorname {Ack} (0) & = & operatorname {S} operatorname {Ack} (m + 1) & = & operatorname {Iter} (operatorname {Ack} (m)) end { pole}}}$

kde S (n) = n + 1 je obvyklé nástupnická funkce a Iter označuje funkční síla operátor, definovaný také primitivní rekurzí:

${displaystyle {egin {array} {lcl} operatorname {Iter} (f) (0) & = & f (1) operatorname {Iter} (f) (n + 1) & = & f (operatorname {Iter} (f) (n)). end {array}}}$

Funkce ${displaystyle mathrm {Ack}}$ takto definovaný souhlasí s Ackermannovou funkcí ${displaystyle A}$ definováno výše: ${displaystyle mathrm {Ack} (m) (n) = A (m, n)}$.

Počet rekurzí před návratem Ackermana (3,3)

Příklad rozšíření

Chcete-li zjistit, jak funkce Ackermann roste tak rychle, pomůže vám to rozšířit některé jednoduché výrazy pomocí pravidel v původní definici. Například lze plně vyhodnotit ${displaystyle A (1,2)}$ následujícím způsobem:

${displaystyle {egin {aligned} 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.end {zarovnáno}}}$

Demonstrovat jak ${displaystyle A (4,3)}$Výsledek výpočtu je v mnoha krocích a ve velkém počtu:

${displaystyle {egin {aligned} 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)))) & = ldots & = A (3, A (3, A (3,13))) & = ldots & = A (3, A (3,65533)) & = ldots & = A (3,2 ^ {65536} -3) & = ldots & = 2 ^ {2 ^ {přesahující {65536} {}}} - 3. end {zarovnáno}}}$

Tabulka hodnot

Výpočet funkce Ackermann lze přepracovat na základě nekonečné tabulky. Nejprve umístěte přirozená čísla podél horního řádku. Chcete-li určit číslo v tabulce, vezměte číslo hned doleva. Potom použijte toto číslo k vyhledání požadovaného čísla ve sloupci daném tímto číslem a o jeden řádek nahoru. Pokud vlevo není žádné číslo, jednoduše se podívejte na sloupec se záhlavím „1“ v předchozím řádku. Tady je malá levá horní část tabulky:

Hodnoty A(m, n)

n m	0	1	2	3	4	n
0	1	2	3	4	5	${displaystyle n + 1}$
1	2	3	4	5	6	${displaystyle n + 2 = 2 + (n + 3) -3}$
2	3	5	7	9	11	${displaystyle 2n + 3 = 2cdot (n + 3) -3}$
3	5	13	29	61	125	${displaystyle 2 ^ {(n + 3)} - 3}$
4	13 ${displaystyle = {2 ^ {2 ^ {2}}} - 3}$ ${displaystyle = 2uparrow uparrow 3-3}$	65533 ${displaystyle = {2 ^ {2 ^ {2 ^ {2}}}} - 3}$ ${displaystyle = 2uparrow uparrow 4-3}$	265536 − 3 ${displaystyle = {2 ^ {2 ^ {2 ^ {2 ^ {2}}}}} - 3}$ ${displaystyle = 2uparrow uparrow 5-3}$	${displaystyle {2 ^ {2 ^ {65536}}} - 3}$ ${displaystyle = {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2}}}}}} - 3}$ ${displaystyle = 2uparrow uparrow 6-3}$	${displaystyle {2 ^ {2 ^ {2 ^ {65536}}}} - 3}$ ${displaystyle = {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2}}}}}}} - 3}$ ${displaystyle = 2uparrow uparrow 7-3}$	${displaystyle {egin {matrix} underbrace {{2 ^ {2}} ^ {{cdot} ^ {{cdot} ^ {{cdot} ^ {2}}}}} _ {n + 3} -3end {matrix} }}$ ${displaystyle = 2uparrow uparrow (n + 3) -3}$
5	65533 ${displaystyle = 2uparrow uparrow (2uparrow uparrow 2) -3}$ ${displaystyle = 2uparrow uparrow uparrow 3-3}$	${displaystyle 2uparrow uparrow uparrow 4-3}$	${displaystyle 2uparrow uparrow uparrow 5-3}$	${displaystyle 2uparrow uparrow uparrow 6-3}$	${displaystyle 2uparrow uparrow uparrow 7-3}$	${displaystyle 2uparrow uparrow uparrow (n + 3) -3}$
6	${displaystyle 2uparrow uparrow uparrow uparrow 3-3}$	${displaystyle 2uparrow uparrow uparrow uparrow 4-3}$	${displaystyle 2uparrow uparrow uparrow uparrow 5-3}$	${displaystyle 2uparrow uparrow uparrow uparrow 6-3}$	${displaystyle 2uparrow uparrow uparrow uparrow 7-3}$	${displaystyle 2uparrow uparrow uparrow uparrow (n + 3) -3}$
m	${displaystyle (2ightarrow (3) ightarrow (m-2)) - 3}$	${displaystyle (2ightarrow (4) ightarrow (m-2)) - 3}$	${displaystyle (2ightarrow (5) ightarrow (m-2)) - 3}$	${displaystyle (2ightarrow (6) ightarrow (m-2)) - 3}$	${displaystyle (2ightarrow (7) ightarrow (m-2)) - 3}$	${displaystyle (2ightarrow (n + 3) ightarrow (m-2)) - 3}$

Čísla zde, která jsou vyjádřena pouze rekurzivní umocněním nebo Knuth šípy jsou velmi velké a zabírají příliš mnoho místa na to, aby byly notovány v jednoduchých desetinných číslicích.

Navzdory velkým hodnotám vyskytujícím se v této rané části tabulky byly definovány některé ještě větší počty, například Grahamovo číslo, které nelze zapsat žádným malým počtem Knuthových šipek. Toto číslo je konstruováno technikou podobnou rekurzivní aplikaci Ackermannovy funkce na sebe.

Toto je opakování výše uvedené tabulky, ale s hodnotami nahrazenými příslušným výrazem z definice funkce, aby se vzor jasně ukázal:

Důkaz, že funkce Ackermann není primitivní rekurzivní

Funkce Ackermann v jistém smyslu roste rychleji než kterákoli jiná primitivní rekurzivní funkce a proto není sám o sobě primitivní rekurzivní.

Konkrétně to jeden ukazuje každé primitivní rekurzivní funkci ${displaystyle f (x_ {1}, ldots, x_ {n})}$ existuje nezáporné celé číslo ${displaystyle t}$ taková, že pro všechna nezáporná celá čísla ${displaystyle x_ {1}, ldots, x_ {n}}$,

${displaystyle f (x_ {1}, ldots, x_ {n})$

Jakmile je toto stanoveno, z toho vyplývá ${displaystyle A}$ sám o sobě není primitivní rekurzivní, protože jinak řečeno ${displaystyle x_ {1} = x_ {2} = t}$ by vedlo k rozporu ${displaystyle A (t, t)$.

Důkaz^[12] postupuje následovně: definujte třídu ${displaystyle {mathcal {A}}}$ všech funkcí, které rostou pomaleji než funkce Ackermann

${displaystyle {mathcal {A}} = vlevo {fmid existuje t forall x_ {1} cdots forall x_ {n}: f (x_ {1}, ldots, x_ {n})$

a ukaž to ${displaystyle {mathcal {A}}}$ obsahuje všechny primitivní rekurzivní funkce. Toho se dosahuje tím, že se to ukáže ${displaystyle {mathcal {A}}}$ obsahuje konstantní funkce, následnickou funkci, projekční funkce a že je uzavřen pod operacemi složení funkce a primitivní rekurze.

Inverzní

Protože funkce  F(n) = A(n, n) uvažovaný výše roste velmi rychle, jeho inverzní funkce, F⁻¹, roste velmi pomalu. Tento inverzní Ackermannova funkce F⁻¹ je obvykle označeno α. Ve skutečnosti, α(n) je menší než 5 pro jakoukoli praktickou velikost vstupu n, od té doby A(4, 4) je v pořadí ${displaystyle 2 ^ {2 ^ {2 ^ {2 ^ {16}}}}}$.

Tato inverze se objeví v čase složitost některých algoritmy, tak jako disjunktně nastavená datová struktura a Chazelle Algoritmus pro minimální kostry. Někdy se v těchto nastaveních používá Ackermannova původní funkce nebo jiné variace, ale všechny rostou podobně vysokou rychlostí. Zejména některé upravené funkce zjednodušují výraz tím, že vylučují -3 a podobné výrazy.

Dvouparametrovou variantu inverzní Ackermannovy funkce lze definovat následovně, kde ${displaystyle lfloor xfloor}$ je funkce podlahy:

${displaystyle alpha (m, n) = min {igeq 1: A (i, lfloor m / nfloor) geq log _ {2} n}.}$

Tato funkce vzniká při přesnějších analýzách výše zmíněných algoritmů a poskytuje propracovanější časovou vazbu. V disjunktně nastavené datové struktuře m představuje počet operací while n představuje počet prvků; v algoritmu minimální kostry, m představuje počet hran, zatímco n představuje počet vrcholů. Několik mírně odlišných definic α(m, n) existovat; například, log₂ n je někdy nahrazen n, a funkce podlahy je někdy nahrazena a strop.

Jiné studie mohou definovat inverzní funkci jedné, kde m je nastaveno na konstantu, takže inverze platí pro konkrétní řádek. ^[13]

Inverzní funkce Ackermanna je primitivní rekurzivní.^[14]

Použít jako měřítko

Funkce Ackermann, díky své definici z hlediska extrémně hluboké rekurze, může být použita jako měřítko překladač Schopnost optimalizovat rekurzi. První publikované použití Ackermannovy funkce tímto způsobem bylo v roce 1970 Dragoș Vaidou^[15] a téměř současně v roce 1971 Yngve Sundblad.^[16]

Seminární práci Sundblad převzal Brian Wichmann (spoluautor Referenční hodnota Whetstone ) v trilogii článků napsaných v letech 1975 až 1982.^[17][18][19]

Viz také

• Teorie vypočítatelnosti
• Dvojitá rekurze
• Rychle rostoucí hierarchie
• Funkce Goodstein
• Primitivní rekurzivní funkce
• Rekurze (informatika)

Reference

Bibliografie

externí odkazy

• "Ackermannova funkce". Encyclopedia of Mathematics. Stiskněte EMS. 2001 [1994].
• Weisstein, Eric W. "Ackermannova funkce". MathWorld.
• Tento článek zahrnuje public domain materiál zNIST dokument:Černý, Paul E. „Ackermannova funkce“. Slovník algoritmů a datových struktur.
• Animovaná kalkulačka funkcí Ackermann
• Scott Aaronson, Kdo může pojmenovat největší číslo? (1999)
• Ackermannovy funkce. Zahrnuje tabulku některých hodnot.
• Hyper-operace: Ackermannova funkce a nová aritmetická operace
• Velká čísla Roberta Munafa popisuje několik variant definice A.
• Gabriel Nivasch, Inverzní Ackermann bez bolesti na inverzní Ackermannovu funkci.
• Raimund Seidel, Porozumění inverzní Ackermannově funkci (Prezentace ve formátu PDF).
• Funkce Ackermann napsaná v různých programovacích jazycích, (zapnuto Rosettský kód )
• Ackermannova funkce (Archivováno 2009-10-24) —Některé studie a programování Harry J. Smith.