Hierarki med rask vekst

I beregnings- og bevisteori er et raskt voksende hierarki (noen ganger kalt et utvidet Grzegorczyk-hierarki ) en familie , indeksert av ordinaler , med raskt økende funksjoner f α : N → N (der N er l 'sett med naturlige tall {0, 1 ,…}, Og α er en ordinær mindre enn en viss tellbar ordinær som generelt er veldig stor ). Et grunnleggende eksempel er Wainer-hierarkiet , som strekker seg til alle α < ε₀ (in) . Slike hierarkier gir en naturlig måte å klassifisere beregningsfunksjoner i henhold til deres vekstrate og algoritmiske kompleksitet ; de gjør det også mulig å uttrykke veldig store tall, for eksempel de som produseres av Goodstein-sekvensene , når selv ikke noteringen av Conways lenker med piler ikke lenger er tilstrekkelig.

Definisjon

La μ være en tellbar stor ordinal slik at for hver grense ordinal α mindre enn μ, får en grunnleggende sekvens , det vil si en streng økende sekvens av ordinals med limit α. Vi definerer deretter et hierarki av funksjoner f α : N → N , for α <μ, som følger:

${\ displaystyle f_ {0} (n) = n + 1}$ ;
${\ displaystyle f _ {\ alpha +1} (n) = f _ {\ alpha} ^ {n} (n)}$ ;
${\ displaystyle f _ {\ alpha} (n) = f _ {\ alpha [n]} (n) \, \!}$ hvis α er en grenseordinær .

Her, f α n ( n ) = f α ( f α (... ( f α ( n )) ...)) angir den n- te iterert av f α påført på n , og α [ n ] i n- th element av den grunnleggende sekvensen valgt for den ordinære grensen α.

Den første delen av dette hierarkiet, dannet av funksjonene f α av den endelige indeksen (dvs. med α <ω), kalles ofte Grzegorczyk-hierarkiet på grunn av dets tette forhold til hierarkiet med funksjonssett definert av det, som vi vil se senere .

Ved å generalisere den forrige definisjonen ytterligere, oppnås et iterasjonshierarki ved å ta for f 0 hvilken som helst streng økende funksjon g : N → N slik at g (0)> 0.

For grenseordiner mindre enn ε₀ (en) , er det en naturlig definisjon av de grunnleggende sekvensene, som vi vil se nedenfor i den detaljerte beskrivelsen av Wainer-hierarkiet, men for større ordinaler blir definisjonen mye mer komplisert, og spør for eksempel bruk av de fundamentale sekvensene i hierarkiet til Veblen . Imidlertid er det fortsatt mulig utover ordinær Feferman-Schütte , Γ 0 , i det minste frem til ordinær Bachmann Howard (in) . Ved å bruke Buchholzs psi-funksjoner (en) , kan vi ytterligere utvide denne definisjonen til ordinær transfinitt iterert forståelse (se analytisk hierarki for flere detaljer). $\ Pi _ {1} ^ {1}$

Det virker usannsynlig at vi kan konstruere en eksplisitt utvidelse utover rekursive ordinaler ; således bemerker Prömel at i et slikt forsøk "vil det til og med oppstå vanskeligheter i notasjonen av ordinalene".

Wainers hierarki

Den Wainer hierarkiet er det spesielle tilfelle av funksjonshierarkiet f α (α ≤ ε 0 n) som oppnås ved å definere de grunnleggende sekvenser som følger:

For grenseverdier λ <ε 0 , skrevet i Cantors normale form ,

hvis λ = ω α 1 + ... + ω α k - 1 + ω α k med α 1 ≥ ... ≥ α k - 1 ≥ α k , så λ [ n ] = ω α 1 + ... + ω α k - 1 + ω α k [ n ],
hvis λ = ω α + 1 , så λ [ n ] = ω α n ,
hvis λ = ω α for en grense ordinal α, så λ [ n ] = ω α [ n ] ,

hvis λ = ε 0 , ta λ [0] = 0 og λ [ n + 1] = ω λ [ n ] .

Noen forfattere bruker litt forskjellige definisjoner (for eksempel ω α + 1 [ n ] = ω α ( n + 1 ), i stedet for ω α ( n ), eller definerer det bare for α <ε 0 (unntatt f ε 0 av hierarki).

Egenskaper for hierarkier

Hver f α er en applikasjon . Hvis de grunnleggende sekvensene kan beregnes (som i tilfelle av Wainer-hierarkiet), er hver f α en beregningsbar funksjon .
I Wainer-hierarkiet domineres f α av f β hvis α <β (for to funksjoner f og g : N → N , sier vi at f dominerer g hvis f ( n )> g ( n ) for alle n tilstrekkelig store) . Den samme egenskapen er faktisk sant for de fleste av hierarkiene nevnt ovenfor (når de tilsvarer grunnleggende sekvenser som tilfredsstiller en ytterligere ganske naturlig tilstand, Bachmann-egenskapen ).
I Grzegorczyk-hierarkiet domineres hver primitive rekursive funksjon av en viss f α med α <ω. Derfor, i Wainers hierarki, domineres alle primitive rekursive funksjoner av f ω (som er en variant av Ackermanns funksjon ).
For n ≥ 3 er settet i (sett) hierarkiet til Grzegorczyk sammensatt av beregningsbare kartlegginger til flere variabler som, for store nok verdier av argumentene, kan beregnes i tid begrenset av en iterert f n -1 k (med k fast) evaluert ved det største argumentet. ${\ mathcal {E}} ^ {n}$
I Wainer-hierarkiet kan hver f α med α <ε 0 beregnes av en Turing-maskin hvis stopp (for hvilken som helst inngangsverdi) kan demonstreres i Peano-aritmetikk .
Motsatt domineres enhver funksjon som kan beregnes av en Turing-maskin hvis stopp kan demonstreres i Peano-aritmetikk, av en f α av Wainer-hierarkiet, med α <ε 0 . Dermed kan vi ikke bevise at funksjonen f ε 0 er en applikasjon som bare bruker Peano-aksiomer.
Den funksjon Goodstein vokser omtrent som f ε 0 , og dominerer hver f α for α <ε 0 , slik at teorem Good ikke kan påvises i den Peano aritmetikk .
I Wainer-hierarkiet, hvis α <β <ε 0 , så dominerer f β en hvilken som helst funksjon som kan beregnes i tid og rom avgrenset av en iterert funksjon f α k .

Funksjonene til raske veksthierarkier

Bortsett fra verdien f α ( 1 ) = 2 for alle α, og fra de aller første nivåene i hierarkiet, er det generelt umulig å gi en nøyaktig verdi av disse funksjonene ved å bruke de vanlige eksponensielle notasjonene, og ikke engang å bruke de forskjellige notasjonene oppfunnet for å beskrive veldig store heltall, så raskt vokser de. Reduksjonene gitt nedenfor gir derfor bare en veldig grov størrelsesorden, dessuten i seg latterlig svak fra funksjonen f ω 2 ( n ).

Funksjonene til de endelige nivåene i et raskt voksende hierarki sammenfaller med de i Grzegorczyk-hierarkiet:

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 for n ≥ 2 (ved bruk av Knuths pilnotasjon )
f k +1 ( n ) = f k n ( n )> (2 ↑ k -1 ) n n ≥ 2 ↑ k n for n ≥ 2, k <ω (hvor ↑ k = ↑↑↑ ... ↑↑ , med k piler).

Vi finner deretter funksjonene f α i Wainer-hierarkiet (ω ≤ α ≤ ε 0 ):

f ω ( n ) = f n ( n )> 2 ↑ n - 1 n > 2 ↑ n - 2 ( n + 3) - 3 = A ( n , n ) for n ≥ 2, hvor A er funksjonen til Ackermann (hvorav f ω er en unary versjon).
f ω + 1 ( n ) = f ω n ( n )> (2 → n → n -1 → 2) (ved bruk av Conways kjedepilnotasjon ), for hvis g k ( n ) = X → n → k , så X → n → k +1 = g k n (1), og spesielt
f ω + 1 (64)> f ω 64 (6)> G, Graham-tallet (G = g 64 i sekvensen definert av g 0 = 4, g k +1 = 3 ↑ g k 3). Dette følger av det faktum at f ω ( n )> 2 ↑ n - 1 n > 3 ↑ n - 2 3 + 2, og derfor 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 ) (streng dannet av k piler →)
f ω 2 ( n ) = f ω n ( n )> ( n → n → ... → n → n ) (med n piler →)
f ε 0 ( n ) er den første funksjonen i Wainer-hierarkiet som dominerer Goodstein-funksjonen G (n) (som dessuten kan uttrykkes nøyaktig ved hjelp av funksjonene f α ; dermed har vi G (4) = f ω (3) - 2, G (8) = f ω + 1 (3) - 2, og 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 = \ prikker$

Merknader og referanser

(fr) Denne artikkelen er delvis eller helt hentet fra Wikipedia-artikkelen på engelsk med tittelen " Raskt voksende hierarki " ( se listen over forfattere ) .

Prömel, Thumser og Voigt 1991 , s. 348.
Gallier 1991 ; Prömel, Thumser og Voigt 1991 .
Caicedo 2007 , teorem 1.11.

Vedlegg

Bibliografi

(en) W. Buchholz og SS Wainer, "Provably Computable Functions and the Fast Growing Hierarchy". Logic and Combinatorics , redigert av S. Simpson, Contemporary Mathematics, Vol. 65, AMS (1987), 179-198.
(en) Andrés Eduardo Caicedo , “ Goodsteins funksjon ” , Revista Colombiana de Matemáticas , vol. 41, n o to2007, s. 381-391 ( les online ).
(en) EA Cichon og SS Wainer , " De langsomt voksende og Grzegorczyk-hierarkiene " , The Journal of Symbolic Logic , vol. 48, n o to1983, s. 399-408 ( ISSN 0022-4812 , DOI 10.2307 / 2273557 ), Lenke til matematikkanmeldelser
(no) Jean H. Gallier , “ Hva er så spesielt med Kruskals setning og ordinær Γ 0 ? En undersøkelse av noen resultater i bevisteori ” , Ann. Ren appl. Logic , vol. 53, n o 3,1991, s. 199-260 ( DOI 10.1016 / 0168-0072 (91) 90022-E , les online ), Link til matematikkanmeldelser , PDF-filer: del 1 2 3 (spesielt del 3, seksjon 12, s. 59-64, "Et glimt av hierarkier av raske og langsomt voksende funksjoner").
Jean-Yves Girard , “ Π 1 2 -logikk. I. Dilators ”, Annals of Mathematical Logic , vol. 21, n o tonitten åtti en, s. 75-219 ( ISSN 0003-4843 , DOI 10.1016 / 0003-4843 (81) 90016-4 ), Lenke til matematikkanmeldelser
(en) MH Löb og SS Wainer, "Hierarkier av tallteoretiske funksjoner", Arch. Matte. Logik 13 (1970). Rettelse, Arch. Matte. Logik 14 (1971). Del I DOI : 10.1007 / BF01967649 , Del 2 DOI : 10.1007 / BF01973616 , Rettelser DOI : 10.1007 / BF01991855 .
(en) HJ Prömel , W. Thumser og B. Voigt , “ Rask voksende funksjoner basert på Ramsey-teoremer ” , Discrete Mathematics , vol. 95, n bein 1-3,Desember 1991, s. 341-358 ( DOI 10.1016 / 0012-365X (91) 90346-4 ).
(en) SS Wainer, " Slow Growing Versus Fast Growing ". Journal of Symbolic Logic 54 (2) (1999), 608-614.

Relaterte artikler