Hierarchie rychlého růstu

V teorii vyčíslitelnosti a důkazu je rychle rostoucí hierarchie (někdy nazývaná rozšířená Grzegorczykova hierarchie ) rodina indexovaná řadovými čísly rychle rostoucích funkcí f α : N → N (kde N je množina přirozených čísel {0, 1 ,…} A α je ordinál menší než určitý počitatelný ordinál, který je obecně velmi velký ). Zásadním příkladem je Wainerova hierarchie rozšiřující se na všechny α < ε₀ (in) . Takové hierarchie poskytují přirozený způsob klasifikace vypočítatelných funkcí podle jejich rychlosti růstu a složitosti algoritmu ; také umožňují vyjádřit velmi velká čísla, jako jsou ta, která produkují Goodsteinovy sekvence , když již nestačí ani zápis řetězových šipek Conwaye .

Definice

Nechť μ je spočítatelný velký ordinál tak, aby pro každou limitu ordinálu α menší než μ byla dána základní posloupnost , to znamená přísně rostoucí posloupnost ordinálů s limitem α. Potom definujeme hierarchii funkcí f α : N → N , pro α <μ, následovně:

${\ displaystyle f_ {0} (n) = n + 1}$ ;
${\ displaystyle f _ {\ alpha +1} (n) = f _ {\ alpha} ^ {n} (n)}$ ;
${\ displaystyle f _ {\ alpha} (n) = f _ {\ alpha [n]} (n) \, \!}$ pokud α je limitní pořadové číslo .

Zde, f alfa n ( n ) = f alfa ( f alfa (... ( f alfa ( n )), ...)) znamená n th opakována z f alfa aplikován na n , a a [ n ] v n th prvek základní posloupnosti zvolený pro ordinální limit α.

Počáteční část této hierarchie, kterou tvoří funkce f α konečného indexu (tj. S α <ω), se často nazývá Grzegorczykova hierarchie, protože má blízký vztah k hierarchii sad funkcí, které definuje, jak uvidíme později .

Při dalším zobecnění předchozí definice se hierarchie iterací získá převzetím pro f 0 jakoukoli striktně rostoucí funkci g : N → N takovou, že g (0)> 0.

Pro limitní ordinály menší než ε₀ (en) existuje přirozená definice základních posloupností, jak uvidíme níže v podrobném popisu Wainerovy hierarchie, ale u větších ordinálů se definice stává mnohem komplikovanější, když se ptáme například na použití základních sekvencí hierarchie Veblen . Zůstává to však možné i za řadovým Feferman-Schütte , Γ 0 , přinejmenším do pořadového Bachmanna Howarda (v) . Pomocí Buchholzových psích funkcí (en) můžeme tuto definici dále rozšířit na ordinál transfinitně iterovaného porozumění ( další podrobnosti viz analytická hierarchie ). $\ Pi _ {1} ^ {1}$

Zdá se nepravděpodobné, že bychom mohli sestavit explicitní rozšíření nad rekurzivní ordinály ; Prömel tedy poznamenává, že při takovém pokusu „by dokonce vznikly potíže se zápisem ordinálů“.

Wainerova hierarchie

Wainer hierarchie je zvláštní případ hierarchie funkcí f alfa (α ≤ ε 0 ), získané tím, že definuje základní sekvence, takto:

Pro limitní ordinály λ <ε 0 , napsané v Cantorově normální formě ,

pokud λ = ω α 1 + ... + ω α k - 1 + ω α k s α 1 ≥ ... ≥ α k - 1 ≥ α k , pak λ [ n ] = ω α 1 + ... + ω α k - 1 + ω α k [ n ],
jestliže λ = ω α + 1 , pak λ [ n ] = ω α n ,
pokud λ = ω α pro limitní pořadové α, pak λ [ n ] = ω α [ n ] ,

pokud λ = ε 0 , vezměte λ [0] = 0 a λ [ n + 1] = ω λ [ n ] .

Někteří autoři používají mírně odlišné definice (například omega α + 1 [ n ] = omega α ( n + 1 ), místo toho, omega α ( n ), nebo definovat pouze pro a <epsilon 0 (s výjimkou dříve epsilon 0 z hierarchie).

Vlastnosti hierarchií

Každé f α je aplikace . Pokud jsou základní posloupnosti vypočítatelné (jako v případě Wainerovy hierarchie), každé f α je vypočítatelná funkce .
Ve Wainerově hierarchii dominuje f α f β, pokud α <β (pro dvě funkce f a g : N → N , říkáme, že f dominuje g, pokud f ( n )> g ( n ) pro všech n dostatečně velkých). Stejná vlastnost ve skutečnosti platí pro většinu výše uvedených hierarchií (pokud odpovídají základním posloupnostem splňujícím další, spíše přirozenou podmínku, vlastnost Bachmann ).
V hierarchii Grzegorczyk každé primitivní rekurzivní funkci dominuje určité f α s α <ω. Ve Wainerově hierarchii tedy všem primitivním rekurzivním funkcím dominuje f ω (což je varianta Ackermannovy funkce ).
Pro n ≥ 3 je množina v hierarchii (množiny) Grzegorczyka složena z vypočítatelných mapování na několik proměnných, které jsou pro dostatečně velké hodnoty jejich argumentů vypočítatelné v čase ohraničeném iterovanou f n -1 k (s k fixed) vyhodnoceno při největším argumentu. ${\ mathcal {E}} ^ {n}$
V hierarchii Wainer je každé f α s α <ε 0 vypočítatelné Turingovým strojem, jehož zastavení (pro jakoukoli vstupní hodnotu) lze demonstrovat v Peano aritmetice .
Naopak všechny funkce vypočitatelný pomocí Turing stroj , jehož doraz může být prokázána v Peanovy aritmetice dominuje f alfa hierarchie Wainer, s α <ε 0 . Nemůžeme tedy dokázat, že funkce f ε 0 je aplikace využívající pouze Peanoovy axiomy.
Funkce Goodstein roste přibližně jako f epsilon 0 , a ovládá každý f alfa pro α <epsilon 0 , takže teorém Goodstein nelze prokázat v Peanovy aritmetiky .
Ve Wainerově hierarchii platí, že pokud α <β <ε 0 , pak f β dominuje jakékoli funkci vypočítatelné v čase a prostoru ohraničené iterovanou funkcí f α k .

Funkce hierarchií rychlého růstu

Kromě hodnoty f α ( 1 ) = 2 pro všechny α a od prvních úrovní hierarchie je obecně nemožné dát přesnou hodnotu těchto funkcí pomocí obvyklých exponenciálních notací, dokonce ani pomocí různých notací vynalezl k popisu velmi velkých celých čísel, tak rychle rostou. Níže uvedená redukce proto poskytují pouze velmi hrubý řád, navíc sám o sobě směšně slabý z funkce f ω 2 ( n ).

Funkce konečných úrovní jakékoli rychle rostoucí hierarchie se shodují s funkcemi hierarchie Grzegorczyk:

f 0 ( n ) = n + 1
f 1 ( n ) = f 0 n ( n ) = n + n = 2 n
f 2 ( n ) = f 1 n ( n ) = 2 n n
f 3 ( n ) = f 2 n ( n ) ≥ 2 ↑↑ n pro n ≥ 2 (pomocí Knuthovy šipkové notace )
f k +1 ( n ) = f k n ( n )> (2 ↑ k -1 ) n n ≥ 2 ↑ k n pro n ≥ 2, k <ω (kde ↑ k = ↑↑↑ ... ↑↑ , se šipkami k ).

Poté najdeme funkce f α Wainerovy hierarchie (ω ≤ α ≤ ε 0 ):

f ω ( n ) = f n ( n )> 2 ↑ n - 1 n > 2 ↑ n - 2 ( n + 3) - 3 = A ( n , n ) pro n ≥ 2, kde A je funkcí Ackermanna (z toho f ω je unární verze).
f ω + 1 ( n ) = f ω n ( n )> (2 → n → n -1 → 2) (pomocí řetězové notace Conwayovy šipky ), protože pokud g k ( n ) = X → n → k , pak X → n → k +1 = g k n (1), a to zejména
f ω + 1 (64)> f ω 64 (6)> G, Grahamovo číslo (G = g 64 v pořadí definovaném g 0 = 4, g k +1 = 3 ↑ g k 3). To vyplývá ze skutečnosti, že f ω ( n )> 2 ↑ n - 1 n > 3 ↑ n - 2 3 + 2, a proto f ω ( g k + 2)> g k +1 + 2.
f ω + k ( n )> (2 → n → n -1 → k +1)> ( n → n → k )
f ω2 ( n ) = f ω + n ( n )> ( n → n → n )
f ω2 + k ( n )> ( n → n → n → k )
f ω3 ( n )> ( n → n → n → n )
f ω k ( n )> ( n → n → ... → n → n ) (řetězec tvořený k šipkami →)
f ω 2 ( n ) = f ω n ( n )> ( n → n → ... → n → n ) (s n šipkami →)
f ε 0 ( n ) je první funkcí Wainerovy hierarchie, která dominuje Goodsteinově funkci G (n) (kterou lze navíc přesně vyjádřit pomocí funkcí f α ; máme tedy G (4) = f ω (3) - 2, G (8) = f ω + 1 (3) - 2 a G (19) = ). $\ scriptstyle f _ {{\ omega ^ {\ omega}}} (f_ {1} (f_ {0} (3))) - 2 = f _ {{\ omega ^ {\ omega}}} (8) - 2 = f _ {{\ omega ^ {8}}} (8) -2 = f _ {{\ omega ^ {7} .8}} (8) -2 = f _ {{\ omega ^ {7} .7 + 8}} (8) -2 = \ tečky$

Poznámky a odkazy

(fr) Tento článek je částečně nebo zcela převzat z anglického článku Wikipedie s názvem „ Rychle rostoucí hierarchie “ ( viz seznam autorů ) .

Promel, Thumser a Voigt 1991 , s. 348.
Gallier 1991 ; Prömel, Thumser a Voigt 1991 .
Caicedo 2007 , Věta 1.11.

Dodatky

Bibliografie

(en) W. Buchholz a SS Wainer, „Prokazatelně vypočítatelné funkce a rychle rostoucí hierarchie“. Logic and Combinatorics , edited by S. Simpson, Contemporary Mathematics, Vol. 65, AMS (1987), 179-198.
(en) Andrés Eduardo Caicedo , „ Goodsteinova funkce “ , Revista Colombiana de Matemáticas , sv. 41, n O 22007, str. 381-391 ( číst online ).
(en) EA Cichon a SS Wainer , „ Pomalu rostoucí hierarchie Grzegorczyků “ , The Journal of Symbolic Logic , sv. 48, n O 21983, str. 399-408 ( ISSN 0022-4812 , DOI 10.2307 / 2273557 ), Matematický Recenze odkaz
(en) Jean H. Gallier , „ Co je tak zvláštního na Kruskalově větě a pořadovém čísle 0 ? Průzkum některých výsledků v teorii důkazů “ , Ann. Pure Appl. Logic , sv. 53, n o 3,1991, str. 199-260 ( DOI 10.1016 / 0168-0072 (91) 90022-E , číst online )„Odkaz na matematické recenze , soubory PDF: část 1 2 3 (zejména část 3, část 12, str. 59–64,„ Pohled na hierarchii funkcí rychlého a pomalého růstu “).
Jean-Yves Girard , „ Π 1 2 - logické. I. Dilators ”, Annals of Mathematical Logic , sv. 21, n O 2devatenáct osmdesát jedna, str. 75-219 ( ISSN 0003-4843 , DOI 10.1016 / 0003-4843 (81) 90016-4 ), Matematický Recenze odkaz
(en) MH Löb a SS Wainer, „Hierarchie číselných teoretických funkcí“, Arch. Matematika. Logik 13 (1970). Oprava, Arch. Matematika. Logik 14 (1971). Část I DOI : 10.1007 / BF01967649 , Část 2 DOI : 10.1007 / BF01973616 , Opravy DOI : 10.1007 / BF01991855 .
(en) HJ Prömel , W. Thumser a B. Voigt , „ Rychle rostoucí funkce založené na Ramseyových větách “ , Discrete Mathematics , sv. 95, n kost 1-3,Prosince 1991, str. 341-358 ( DOI 10.1016 / 0012-365X (91) 90346-4 ).
(en) SS Wainer, „ Pomalu rostoucí versus rychle rostoucí “. Journal of Symbolic Logic 54 (2) (1999), 608-614.

Související články