Nopeasti kasvava hierarkia

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 22. maaliskuuta 2020 tarkistetusta versiosta . tarkastukset vaativat 9 muokkausta .

Nopeasti kasvava hierarkia (kutsutaan myös laajennetuksi Grzegorczyk-hierarkiaksi ) on nopeasti kasvavien funktioiden perhe, joka on indeksoitu järjestysluvuilla . Tunnetuin nopeasti kasvavan hierarkian erikoistapaus on Loeb -Weiner -hierarkia.

Määritelmä

Nopeasti kasvava hierarkia määritellään seuraavilla säännöillä

  1. (yleensä voi olla mikä tahansa kasvutoiminto),
  2. ,
  3. jos raja-kertaluku,
    • missä on jollekin rajajärjestäjälle määritetyn perussekvenssin n:s elementti .
    • Nopeasti kasvavasta hierarkiasta on useita versioita, mutta tunnetuin on Loeb-Weiner-hierarkia, jossa Cantor-normaalimuodossa kirjoitettujen rajajärjestysten perussekvenssit määritellään seuraavilla säännöillä:
  4. ,
    • varten ,
  5. ,
  6. jos raja-kertaluku,
  7. ja .

Yllä olevat rajajärjestyksen perussekvenssit on annettu Veblen -funktioita ja Buchholz-funktioita käsittelevissä artikkeleissa

Esimerkkejä

,

.

funktioille, jotka on indeksoitu äärellisillä järjestysluvuilla ,

.

Erityisesti, jos n = 10:

,

,

.

Siten jo ensimmäinen transfiniittinen järjestysluku vastaa Knuthin nuolen merkinnän rajaa .

Kuuluisa Graham-luku on pienempi kuin .

Määritelmän yksinkertaisuuden ja selkeyden vuoksi nopeasti kasvavaa hierarkiaa käytetään analysoimaan erilaisia ​​merkintöjä suurten lukujen kirjoittamista varten .

Knuthin merkintä Conway-merkintä Bowersin merkintä
merkintäraja
esimerkkejä

Yllä oleva määritelmä määrittelee nopeasti kasvavan hierarkian aina . Lisäkasvua varten voit käyttää Veblen-funktiota ja muita vielä tehokkaampia järjestyslukujen merkintöjä [1] .

Esimerkkejä

Katso myös

Muistiinpanot

  1. Kerr, Josh Hämmästynyt: nopeasti kasvava hierarkia maallikoille – eli valtavat määrät . Haettu 7. lokakuuta 2016. Arkistoitu alkuperäisestä 13. heinäkuuta 2019.

Linkit