Reuzen Getallen Bootstrap

van Giga Gerard

“Row, row, row your boat,
Gently down the stream.
Merrily, merrily, merrily, merrily,

          Life is but a dream

§2. Rijen

Vandaag vertrekken we voor een lange reis naar het grootste getal. Monster aan en wandel over Giga Gerard’s:
„Reuzen Getallen Bootstrap”
G of giga is het voor­voegsel voor miljard 109, wat we liever schrijven als een macht 10^9 of met units 1 en telbare sterren.
1111111111**111111111
Een bootstrap is een opstart [boot] pro­gramma voor computers, dus deze opera­ties legggen we zo dadelijk uit. Unaire notatie met enen voor natuur­lijke getallen bespraken we in §1.1.

Straks in §2.0 her­halen we getallen, wat vermenig­vuldigen is. Ook presen­teren we een meta notatie voor de her­haling van woorden.
Blog §2.1 gaat over machten en hoe nu verder… We experi­menteren met opera­toren en functies en testen meer­voudige recursie.
In §2.2 geven we een histo­risch over­zicht van de super­machten van Knuth, Hilbert, Ackermann en Péter. En onze super­sterren natuur­lijk, die we l-r evalueren met behulp van pop­sterren. Bijzonder zijn de hek­machten, die half zo super­snel gaan.

Het thema van hoofdstuk §2 is rijen. Van een rij getallen of lineaire array kunnen we de index getallen uit­breiden tot een index rij, die zelf ook weer index rijen bevat. Geneste arrays tot op elk niveau.
In deze structuren passen we twee soorten regels toe. De super radix gebaseerd op het op­laden met de constante a, de aas, wat op termijn minimaal is. En onze array functie gebaseerd op het op­laden vanuit sub­totaal b, de bel, wat op termijn maximaal is.
Systemen voor de evaluatie van expressies, waar af­getelde iter­atoren opnieuw worden op­geladen, noemen we blazers. We blazen azen op de rij §2.3 en in nesten §2.4 om onze structuur te determineren. En we blazen bellen in §2.5 en §2.6 en daarmee willen we de array functies van Bird evenaren.

Lectori salutem Welkom aan boord.

X

§2.0 Herhalen

Vermenigvuldigen is herhaald optellen. We schrijven deze opera­tie met een ster a*b tussen twee getallen, om b keer a te nemen. Getallen 1.. zijn op­gebouwd uit units 1 en zo bezien is vermenig­vuldiging al een her­haling op her­haling.

  • a*1 ?= a (een keer)
  • a*b1 ?= a+a*b (meer keer) == a..+a*1 :b = a.. :b1

Scan expressies l-r (links naar rechts) en probeer deze regels toe te passen. Varia­belen uit verschil­lende regels zijn onafhankelijk.

Bij voorwaardelijke toewijzing ?= kan een regel de expressie alleen ver­anderen, als er geen opera­tie die voor­rang heeft op volgt.
Dus a*3 = a+a*2 = a+a+a*1 = aa+a*1 = aa+a = aaa is hoe we een ex­pressie uit­werken, waarbij vermenig­vuldiging * voor­rang krijgt en we een enkele op­telling + links laten liggen.

Bij herhaalde toepassing == van regels volgt een resultaat meteen. Soms korten we dit af tot enkele gelijk­heid = om een makke­lijke uit­werking samen te vatten.

Een andere manier van optellen is, om getallen om te draaien en dan samen te voegen. Dit pop­tellen + kan ook staps­gewijs, per tel.

  • b+1 ?= 1b
  • b+a1 ?= 1b+a == a1b

In Cantor's oneindige valt 1ω = ω weg, maar telt ω1 gewoon op. Stel dat we, in dit niet commu­tatieve on­eindige, een serie a van links bij een on­eindig grotere b voegen. Als de serie on­eindig lang genoeg is domineert die de uit­komst, waar b van rechts bij optelt.
Op de pop wijze van optellen kunnen we operaties met een ω on­eindig item a van l-r evalueren.

Metamatiek 2.0

We gebruiken twee meta notaties voor tekst herhaling, bedoeld om de uit­werking van ex­pressies inzich­telijk te maken.
In regex notatie wordt een karakter herhaald door het aantal {n} erna tussen krul­haken te zetten.
In onze repex notatie wordt een woord geselecteerd tussen punten, en repeteert deze achter de dubbele punt, rechts van de expressie.

  • W.. :5 = WWWWW
  • Wi..X..Yi :3: = W1W2W3XY3Y2Y1
  • V.W..X..Y.Z :2: = VWWXYYZ
  • i..Xj..Z :3 :4 = 6X1X2X3X4Z

Woord selectie begint bij de grens van de expressie (witruimte) of anders links van een . punt. Deze selectie eindigt rechts met twee punten, waarop het geselec­teerde woord her­haald wordt.
De rep of repetitie :n telt de herhalingen van links naar rechts, of twee­zijdig :n: van buiten naar binnen.

Index variabelen i en j incrementeren in een reeks. Vanaf 1 in het begin (meestal links) neemt de index per stap 1 toe, van index i=1 tot eind index i=n. Het aantal stappen en het begin blijkt uit de rep.

We willen maximale algoritmes niet op reps baseren, maar op simpele regels die we staps­gewijs toe­passen: met een eerste en steeds een volgende stap.
Onze reductie trein beweegt van vertrek expressie, onze input, naar aankomst expressie, de output, en arriveert op vele tussen­stations.

G0.=Gi.. :u  =>
   G0=1.. :Gi=Gu

Omdat gelijkheid = van expressies transitief is, blijven de resul­taten kloppen. Al deze ex­pressies zijn slechts andere vormen van de output Gu die na complete evaluatie wordt bereikt.

In de voorrangsregels voor operatoren gaan machten ^ voor * sterren, en een plus + of pop komt in de evaluatie laatst.

  • + ?< *{n} ?< ^ (operator prece­dentie)
  • ^.. :n ?< ^.. :n1 (meer eerst)

Voor supermachten geschreven met dakjes of supers ^.. geldt de gebrui­keljke prece­dentie van de meer­derheid, en in gelijke gevallen zijn ze rechts asso­ciatief. Er is een teken minder nodig a^{n}b = a*{n1}b dan voor super­machten met sterren.

Onze supersterren *.. evalueren we l-r (links asso­ciatief) zonder dat verge­lijking nodig is. Hoewel prece­dentie van de minder­heid uit hun definitie zou moeten volgen. Immers a*{0}b = ab wordt van nature direkt opgeteld.

In de volgende secties zullen machten ^ of ** (als herhaling van vermenig­vuldigen) en super­machten zoals tetratie ^^ of *** (als een toren van machten) verder worden uit­gewerkt.
Operatoren als + * ^ helpen om moeilijk telbare getallen makkelijk op te schrijven, maar het kan ook zonder.

In radix systemen, zoals ons tien­tallig stelsel, worden de expo­nenten van machten van 10 gerepre­senteerd door hun positie in een reeks cijfers. De cijfers c zelf her­halen deze machten.

..ci.c0 n:  waar 0c<10
   = c0.+ci*10^i.. :n

Ieder cijfer ci vermenigvuldigt zijn macht van 10 en daarna wordt die serie opge­teld tot een getal, dat uniek is voor de cijfer­reeks.
Best knap, hoe kunnen kinderen zoiets ingewikkelds leren…?

X

§2.1 Machten

Er zijn drie elementaire operaties tussen getallen. Optellen + wat samen­voegen uit­stelt, vermenig­vuldigen * en machts­verheffing met ^ of ** als operator. Zowel de operatie als het resultaat hiervan noemen we een macht.

Machtsverheffen is herhaald vermenig­vuldigen met het­zelfde getal. Dat kan per stap worden gedaan, met als operator ^ een dakje.

  • a^1 ?= a
  • a^b1 ?= a^b*a == a^1.*a.. :b = a*..a :b

De voorwaardelijke toewijzing ?= staat hier, omdat een macht rechts in een reeks elemen­taire operaties voor­rang krijgt. Bijv. de ex­pressie a^b^c betekent a^(b^c), waar de sub­expressie b^c eerst wordt uit­gewerkt (tot exponent).

Onze logaritme functie log is een inverse van machts­verheffing, en nog wat weetjes over operaties met machten.

  • m^p*m^q = m^pq (m^p)^q = m^(p*q) n^-*n = 1
  • m^log(m,n) = n log(m,p*q) = log(m,p)+log(m,q) log(m,n)*log(k,m) = log(k,n)

Ster operaties *.. evalueren we strikt `= van links. Daarbij zijn geen haakjes nodig, noch verge­lijkende prece­dentie regels.
Alleen een rechter operatie zónder plus die direkt volgt ?= op een type operatie mét plus wordt met voor­rang geholpen. En naast­gelegen getallen ab tellen we natuurlijk op.

Onze l-r definitie voor machten met ** twee sterren.

  • a**1 `= a (eliminatie)
  • a**b1 `= a*+a**b (stap)
  • c*+a ?= a*c (popschuiven)

We gebruiken een popster om een macht af te schermen van zijn uit­werking, die links plaats vindt. Het plus teken in *+ is tijdelijk en wordt opgelost, als deze operatie op­schuift voor een nieuwe pop­ster.

Experiment 2.1

Ontwerp een Superplus systeem. Pas de regels in volgorde toe, zodat c>1 voor de eind iter­ator en b>0 en c>0 in de recursie.

  • a+b = ab
  • a+{c}1 = a
  • a+{c1}b1 = a+{c}a+{c1}b

Als we hierbij prioriteit tegelijk met subexpressies overboord gooien, en +.. opera­toren puur l-r evalueren, werkt dat dan?
Ja en snel, twee plussen ++ herhaalt de verdubbeling van a.

a++b2 = a+a++b1
  = aa++b1 = aaaa++b
 == a.*2..++1 :b1
  = a*2^b1

Een post operatie \^ plaatst na uitwerking van de vooraf­gaande operatie een extra expo­nent bovenop de hoogste sub­operant daarvan. Post operatie \* vermenig­vuldigt deze hoogste exponent dan wel super­exponent (met prio­riteit zodra deze er is).
We plaatsen de post backslash rechts en draaien de operanten niet om, zoals bij de pop plus links van de operatie.

We vergelijken superplussen met ^.. supermachten, die pas in §2.2 worden uit­gelegd met een histo­risch overzicht.
De expressie links van ≈> is insignificant groter dan die rechts.

  • a1+++b3 = a1++a1+++b2 = a1*2^a+++b2 ≈> 2^(a*2^a)+++b1 ≈> 2^2^2^a1+++b ≈≈ 2^..a1+++1 :b2 = 2^^b2\^a1 ≈ 2^^b3 ≈ a1^^b3\*log(a1,2)
  • a+{c2}b2 = a+{c1}a+{c2}b1 ≈> 2^{c}a+{c2}b1 ≈> 2^{c}2^{c}a+{c2}b ≈≈ 2^{c1}b1\^{c}a+{c2}1 = 2^{c1}b1\^{c}a <≈ a^{c1}b2

Door twee tekens, de 1 en + plus, te gebruiken krijgen we al super­grote getallen. Ook al laten we de enkele tekens domweg vallen, in de initiële regels.
Bijv. 11+++++111 2^^^^3 = 2^^65536.

Omdat a+{c}b <≈ a*{c}b zijn de recursies in de functies van super­plussen D(a,b1,c1) = D(D(a,a,c),b,c1) en van super­machten F(a,b1,c1) = F(a,F(a,b,c1),c) die we ver­klaren in het volgende blog, onge­veer even snel.

Ontwerp nu een hybride functie met meervoudige recursie op twee posities. Noem dit de Excalibur functie, het twee­snijdend zwaard.

  • E(a,b,1) = E(a,b) = ab
  • E(a,1,c) = a
  • E(a,b1,c1) = E(E(a,a,c),E(a,b,c1),c)

Rozsa Péter stelt 1 dat recursie in meerdere variabelen tegelijk niet signi­ficant sneller gaat, en dit willen we testen.

  • E(a,b1,2) = E(aa,E(a,b,2)) == E(aa,..a..) :b = a*2*b+a
  • E(a1,b1,3) ≈> E(a^2*2,E(a,b,3),2) ≈> aa^2*E(a,b,3) == aa^2*..a :b = aa^bb*a
  • E(a1,b1,4) ≈> E(aa^aa,E(a1,b,4),3) ≈> aa^(a*3*E(a1,b,4)) ≈≈> a1^..(a*a*3) :b>0 ≈> a1^^b1\^2
  • E(a,b1,5) ≈> E(a^^a,E(a,b,5),4) ≈> a^^(a+E(a,b,5)-) ≈≈> a^^..aa- :b>0 <≈ a^^^b1\*2
  • a^{c}b < E(a,b,c2) <≈ a^{c}b\*2 < aa^{c}b

We verwachten dat hogere expressies E als de bij c=5 berekende zullen ver­lopen, en niet verder zakken richting F.
In ieder geval voegt de extra recursie hier weinig toe, al is argument a onge­veer ver­dubbeld. Misschien als we de extra stap E in stap F nesten, dat dat hoger­op groter uitpakt?

  • G(a,b,1) = G(a,b) = ab
  • G(a,1,c) = a
  • G(a,b1,c1) = G(a,G(G(a,a,c),b,c1),c)

Werken we onze dubbele Griffioen functie uit. Dan neemt super­macht c meteen 1 toe, verge­leken met E of super­plussen. In het vervolg telt het tweede argument bijna als b*2, wat te ver­wachten viel door het dubbele nesten in de recursie stap.

  • G(a,b2,2) = a+G(aa,b1,2) = a*3+G(a*4,b,2) == a*(2^b2)- ≈> 2^b2
  • G(a,b2,3) ≈> 2^G(2^a,b1,3) = 2^2^G(2^2^a,b,3) == 2^^b1\^2^^b1\^a = 2^^bb2\^a ≈ 2^^bb4
  • G(a,b1,4) ≈ 2^^G(2^^aa,b,4) == 2^^..2^^..aa :b :b = 2^^^bb\^^aa ≈ 2^^^bb2
  • G(a,b1,c1) ≈ 2^{c}bb\^{c-}aa ≈ aa^{c}bb1 ≈ 2^{c}bb2

Omdat argument c ongemoeid blijft, draagt het nesten van meerdere sub­expressies niet wezenlijk bij aan het maken van grotere getallen, als die recursies op zich al super­machten op­leveren.

Een serie dezelfde operaties komt in de reductie­trein van een ster operatie nooit voor. Dat geldt voor enkele operaties. Zet een tweede pop links vóór de macht en deze zal opereren op de eerste factor.

  • 1+2**3 = 1+2*+2**2 = 3*+2**2 = 3*+2*+2**1 = 2*3*+2**1 == 6*+2**1 = 6*+2 = 2*6 == 12.
  • 2**3*2 == 6*+2**1*2 = 6*+2*2 = 6*+2+2*1 = 2*6+2*1 == 12+2*1 = 12+2 = 14.

Een operatie die volgt geeft nog vreemdere resultaten, omdat deze voor­tijdig in stelling wordt gebracht. Wie wil rekenen met sterren, zal haakjes moeten toe­passen. Maar hier gaat het erom één ster operatie met één hulp­teken, de pop + plus, in stappen uit te werken.

Pop­sterren *{c}+ stellen die operatie niet alleen uit, maar draait de operanten daarna ook om. Dit is pop­schuiven. Dit blijft gelijk met *+ want vermenig­vuldigen is commu­tatief, maar bij super­machten maakt het om­draaien groot verschil.

Pop­schuiven is nodig vanaf **+ bij dubbele machten. Die ont­staan bij het uit­werken van tetraties *** in enkele stappen = zoals we dat hier­onder doen, tot de her­haling == ervan duidelijk is.

3***3 = 3**+3***2
      = 3**+3**+3***1
      = 3**3**+3***1
 3**3 = 3*+3**2
      = 3*+3*+3**1
      = 3*3*+3**1
  3*3 = 3+3*2
      = 3+3+3*1
      = 6+3*1
      = 6+3
 3**3 = 6+3*+3**1
      = 9*+3**1
      = 9*+3
3***3 = 9*+3**+3***1
      = 3*9**+3***1
     == 24+3**+3***1
      = 27**+3***1
      = 27**+3
      = 3**27 (popschuiven)
      = 3*+3**26
     == 9*+3**25
     == 27*+3**24
     == 7625597484987.

Stel dat u de regel voor pop­schuiven vervangt door pop­ruimen, dat is plus + elim­inatie zonder dat er operanten ver­wisseld worden. Dan blijven uw hek­machten #.. ver achter op onze *.. super­sterren.
Hierboven zou 27##3 omdat (3^3)^3 = 3^(3*3) = 3^9 al een factor 3^18 schelen. Hoe klein is dan uw 4####4 en hoe laat evenaart u de onze…?

X

§2.2 Supermachten

Nadat eeuwenlang machtsverheffen de hoogste operatie was, kwam in 1976 de algo­ritme kenner Donald Knuth 2 met telbare opera­toren {c} voor wat we in het algemeen super­machten noemen.
De algemene regel voor Knuth's pijlen.

a{c1}b1 =
  (a{c}..a..) :b:

Dus a{c}1 = a geeft voor b=0 de eerste stap.
De enkele pijl is de gewone ^ macht operator, die Knuth uit­legt als her­haling van her­haald op­tellen, hier wel bekend.

Het was de verbeelding van de wiskundige Ronald Graham, expert in de grafen­theorie, die popula­risator Martin Gardner 3 aan­spoorde om een buite­nissig aantal van Knuth's pijlen te gebruiken om Graham's getal mee aan te duiden. Graham's getal is een boven­grens voor een reken­kundig probleem met bi­chromatische hyper­machten, zoals het Neder­landse Guinness record boek 4 dat noemde. Hoewel Gardner de schatting, die Graham eerder publi­ceerde 5, danig overdreef.

Het mooie van het bewijs dat Graham gaf, is dat de oplossing zeker bestaat, hoewel dit getal wel eens onbe­rekenbaar ver weg zou kunnen liggen. Maar het is voor de hand liggend dat het klein is.
Zoals ook het 9e priemgetal dichterbij ligt p8+4 = 23 dan de boven­grens 1+1.*pi.. :8 die het bestaan ervan bewijst.
Tegenwoordig zoekt men de oplossing voor het probleem van Graham trouwens vanaf 13 en zijn boven­grens is tot 2↑↑↑6 terug­gebracht.

Graham's record getal is een hyper­macht, die nochtans te bepalen is met recursie over super­macht pijlen.

3{..4..}3  :43:

Knuth's operaties werden eerder al uitgedrukt in een functie, die we voor het eerst in 1925 bij David Hilbert 6 tegen­komen. Hilbert begint om op­tellen, vermenig­vuldigen en machten te her­halen, om daarmee de operatie van tetratie aan te duiden.
De hogere supermachten pakt Hilbert in in zijn twee­ledige recur­sieve functies Hc die we aldus her­schreven.

  • H1(a,b) = a+b = ab
  • Hc1(a,1) = (Hc,a,1) = a
  • Hc1(a,b1) = (Hc,a,b1) = Hc(a,(Hc,a,b)) == Hc(a,..(Hc,a,1)..) :b: = Hc(a,..a..) :b:

Hilbert gaf zijn voorzet Ha(a,a) en Wilhelm Ackermann schoot die er in 1928 in, met een stroef bewijs 7 dat deze functie niet primitief recursief is te formuleren.
Zijn Ackermann functie F(a,a,a) werkt volgens deze regels uit.

  • F(a,b,0) = a+b = ab
  • F(a,0,1) = a*0 = 0 F(a,0,2) = 1 F(a,0,c>2) = a (vervroegd)
  • F(a,b1,c1) = F(a,F(a,b,c1),c) == F(a,..F(a,0,c1)..,c) :b1:

Het is mogelijk om in één regel, vanuit unair optellen, met Hilbert's en Knuth's repetitie van operaties in haakjes, een complete definitie te geven van super­machten.

a^{c}b1 = a*{c1}b1
  = (a*{c}..a..) :b:

Knuth's pijl operaties, onze super­sterren en de eerdere recursieve functies hebben allen het­zelfde bereik. Wij noemen het super­machten, of dubbele recursie, want er spelen twee recursies: een grote met index c over een kleine met index b en een constante a>1.

De Hongaarse wiskundige Rozsa Péter had in haar boek 8 uit 1950 slechts twee argu­menten nodig in een dubbel recur­sieve functie.
Definieer Péter's P met naam en positie van variabelen omge­zet. a De functie begint met op­tellen van een constante a=1.

  • P(b,0) = b+1 = b1
  • P(0,c1) = P(1,c)
  • P(b1,c1) = P(P(b,c1),c) == P(..P(0,c1)..,c) :b1: = P(..P(1,c)..,c) :b1:

Om systemen voor grote getallen te vergelijken, volstaan we met het uit­rekenen van de belang­rijke iteraties. Zodoende, als de voort­zetting inzich­telijk is, levert dit een bewijs door demonstratie.

Demonstratie 2.2

Péter's P(b,c1)+3 = 2*{c}b3 uitgedrukt in super­machten.

  • P(b,1) = P(..2..,0) :b: == 2.+1.. :b = b+2
  • P(b,2) = P(..3..,1) :b: == 3.+2.. :b = b*2+3
  • P(b,3) = P(..5..,2) :b: == (..5..*2+3) :b: = 2^(b+3)-3.
  • P(b,4) = P(..13..,3) :b: == 2^(..16..).-3 :b: = 2^^(b+3)-3.
  • P(b,5) = P(..2^^4-3..,4) :b: == 2^^(..2^^^3..).-3 :b: = 2^^^(b+3)-3.
  • P(b,c+3) = P(P(b,c3),c2) == P(..P(1,c2)..,c2) :b: = P(..2^{c}4-3..,c2) :b: == 2^{c}..2^{c1}3-3 :b = 2^{c+1}(b+3)-3.

Péter's P is een speciaal geval van functies Pa waar a=1. Alleen de initiële regel voor c=0 is in Pa algemener.

  • Pa(b,0) = a+b = ab
  • Pa(b,c1) = Pa(..1..,c) :b1:

Na P0(b,0) = b reduceert P0 steevast tot 1.

  • P0(b,1) = P0(..1..,0) :b: == 1
  • P0(b,2) = P0(..1..,1) :b: == 1
  • P0(b,c2) = P0(b,c1) = 1

Dat P2(b,c)+3 = 2*{c}b3 volgt uit P2(1,0) = 3 en eerdere demon­stratie van Péter's P1 omdat ook P1(1,1) = 3 en daarna is P2 op dezelfde wijze recursief bepaald.

  • P2(b,0) = b2 = P1(b,1) = 2+b3-3.
  • P2(b,1) = P2(..3..,0) :b: == 3.+2.. :b = b*2+3 = 2*b3-3.
  • P2(b,c) = P1(b,c1) = 2*{c}b3-3.

Ook de vergelijking van P3 met super­sterren is merkwaardig exact.

  • P3(b,0) = b3 = 3+b2-2.
  • P3(b,1) = P3(..4..,0) :b: == 4.+3.. :b = b*3+4 = 3*b2-2.
  • P3(b,2) = P3(..7..,1) :b: == (..1..*3+4) :b1: = 3.*3..-2. :b1: = 3^b2-2.
  • P3(b,3) = P3(..25..,2) :b: == 3.^3..-2. :b1: = 3^^b2-2.
  • P3(b,c2) = P3(.. 3^{c}3-2..,2) :b: == 3^{c}..3^{c1}2-2 :b = 3^{c1}b2-2.

Hierna komen de details bij supermachten niet meer overeen. Er is geen vast getal q voor de optel aftel routine en dit is niet te repareren.

  • P4(b,1) = P4(..5..,0) :b: == 5.+4.. :b = b*4+5 = 4*(b+q)-q. & q=5/3
  • P4(b,2) = P4(..9..,1) :b: == (..1..*4+5) :b1: = 4^b1*(1+q)-q.4^(b+qr)-qr. r.041
  • P4(b,3) = P4(..41..,2) :b: ≈≈ 4^..(1+qr)-qr. :b1: ≈ 4^^bqrs-qrs. s<.001
  • P4(b,c) ≈ 4*{c}(b+qr)

De twee systemen zijn aleen bij benadering te vergelijken. In feite zijn er geen op­lossingen voor varia­belen qr, qrs, etc. We noemen dit surro­gaat variabelen.

  • P5(b,1) = P5(..6..,0) :b: == 6.+5.. :b = b1*5+1 = 5*bq-q. & q=3/2
  • P5(b,2) = P5(..1..,1) :b1: = 5^b1*q1-q. = 5^bqr-q.5^bqr-qr. & qr = log(5,q1)+1 ≈ 1.569
  • P5(b,c) ≈ 5*{c}bqr

Voltooi de benadering van de dubbele recursie Pa met super­macht opera­toren. Voor grote a dalen de optel aftel surro­gaten tot limiet 1.

  • Pa(b,1) = Pa(..1..,0) :b1: == a1.+a.. :b = b1*a+1 = a*bq-q. & q=a1/a-
  • Pa(b,2) = Pa(..1..,1) :b1: = a^b1*q1-q. = a^bqr-q. qr ≈ 1+log(a,2) ≈ 1
  • Pa(b,c) ≈ a*{c}b1

Het is aardig om te weten dat de limiet van Pa een stap in b verder is dan bij super­sterren, maar het zet geen zoden aan de dijk. Geteld vanaf c produ­ceren beide systemen onge­veer even grote getallen.

Omzetting van Rozsa Péter's dubbel recursieve functie P() naar een links asso­ciatieve `= versie met oparator teken is eenvoudig.

  • b1 `= b11
  • 1c1 `= 1cc
  • b1c1 `= bc1c == 1.c.. :b2

Zo vermijden we de 0 en subexpressie haakjes. En we werken bc1 stap na stap uit tot een reeks van b van zulke c recursies.

Supersterren *.. regelen we ook liever met enkele stappen. Maar om deze l-r te evalueren, zonder haakjes of prece­dentie, is lastiger. We intro­duceren pop opera­toren om super­machten te scheiden.
In deze definitie van supersterren is c0 zodat *{0} unair optelt.

  • a*{c1}1 `= a
  • a*{c1}b1 `= a*{c}+a*{c1}b
  • b*{c}+a ?= a*{c}b (popschuiven)

Hogere superster operaties worden van de uitwerking van de lagere apart gehouden door er tijdelijk pop­sterren *..+ tussenin te plaatsen. Als er ?= een pop­ster volgt, dan valt de linker pop + van de sterren weg, terwijl de operanten om­keren of pop­schuiven.

Van dit pop­schuiven zagen we al een voorbeeld bij dubbele machten in blog §2.1. We gaven plus elim­inatie of pop­ruimen als alter­natief, en zulke opera­toren #.. noemden we hek­machten.

Vul de regel a#{c}+b ?= a#{c}b voor pop­ruimen in in het schema voor super­sterren. En ver­vang in de andere regels de ster * door een hekje # om hek­machten te definiëren. Ook hier telt #{0} een­voudig direkt op, zodat de initiële regel voor c=0 over­bodig is.

De regels voor een hek­macht functie.

  • #(a,1,c1) = a
  • #(a,b1,1) = #(a,b,1)a
  • #(a,b1,c1) = #(#(a,b,c1),a,c) == #(..a..,a,c) :b:

Hek­machten lossen we steeds links associatief op.
Bereken de snelheid van onze #.. hek­macht operaties ten opzichte van Knuth's ^.. super­machten.

  • a##a##a = (a^a)^a = a^(a*a)
  • a###b1 = a###b^a = a^(1.*a..) :b = a^a^b
  • a1###a###a ≈ a1^a1^a^a
  • a####b ≈ a^^b^a^^b ≈ a^^b1
  • a#{4}a#{4}a ≈ (a^^a1)^^a1 ≈ a^..a^^a1 :a = a^^aa1
  • a#{5}b2 ≈ a#{5}b1^^a1 ≈ a^..a^^a{b}1 :a ≈ a^^(a*b1)
  • a#{5}a1#{5}a ≈ a^^a^^(a*a)
  • a#{6}b ≈ a^^^b\*a
  • a#{cc1}b ≈ a^{c}(a*b)
  • a#{cc}b ≈ a^{c}b

Vanaf c=2 machten wordt het aantal hekken #.. verdubbeld ten op­zichte van *.. sterren. Een halve super­macht tilt het grondtal a de super­exponent in (eerst als macht, dan als factor) en de andere helft ont­wikkelt de super­toren van exponenten.

In de Grzegorczyk hierarchie 9 is er geen aparte klasse recur­sieve functies tussen de super­machten in. Toch slaagden we erin c op te delen: in functies die op halve super­snelheid gaan en op hele. Wie weet is zo rationele ver­deling van supers c mogelijk…?

Toch denken we dat een fijnere algoritmische verdeling buiten iteratie over operant b van super­machten niet bestaat. En dat alle algo­ritmen die primitieve recursie over­treffen dit doen door te itereren over c.
Dit is ons dubbele vermoeden. Dubbele recursie kan dus niet 3 keer of 1/3 keer zo snel gaan als super­sterren bij­voorbeeld.

In de volgende blogs speelt deze kwestie bij geneste arrays. Als we elke positie in array functies indexeren, moeten geneste arrays dubbel zo diep zijn om het­zelfde uit te drukken. We kunnen aan­tonen, dat een dubbele nest­diepte een betere uit­komst geeft.
Enkel of dubbel zijn in structuren voor algo­ritmes blijkbaar de enige natuur­lijke alter­natieven…

X

§2.3 Aasblazer

Aas [ace] is hoe we de linker operant a noemen, die constant blijft. In de primitief recur­sieve stap van onze blazer [blazer] functies telt a op bij varia­bele b, de bel [bubble]. Deze wordt gedurende de evaluatie steeds groter, tot de bel op het laatst de uit­komst [output] produ­ceert, als een lange reeks 1.. enen.

Initieer Aas­blazer, met getal selectie en optellen met omkeren.

  • a[1] = 1
  • a[,1] = a[a,] = a[a] = a
  • a[b,1] = a[ba,] = a[ba] = ab = a+b

Passage 2 telt aas a bij niets. Passage 3 telt ba intern direkt op. We classi­ficeren dit met nul sterren *{0} als tellen tot getal.

Het kan handig zijn om het groeiende subtotaal alvast rechts buiten de array te presen­teren in een reken­kundig format. Zet dan wel een plus teken + tussen de Aas­blazer array en de a.2. extern ge­plaatste bel.

In de eerste iteratie herhaalt c het optellen van a.

  • a[b,2] = a[ba,1] = a[baa] = aab = a*2+b
  • a[b,1c] = a[ba,c] := a[,c]+ab == a[,1]+a*c+b = a*1c+b
  • a[,c] = a*c

Dit * is vermenigvuldigen en herhaalt de optel structuur *{0} en zo begint met factor c de klasse *{1} van para­meters of iter­atoren. In Aas­blazer fungeren alle iter­aties als vermenig­vuldiging.

Volgt de definitie van Aas­blazer's voorste rij, of wat de lineaire array wordt genoemd. De voorste rij para­meters is eigenlijk niet de eerste rij, maar de nulde, omdat elke positie met een enkele index gegeven is, die zelf weer op begin­positie [0] staat.
De azen rij werken we hieronder uit, en azen nesten in blog §2.4. Volgens regels uit de definitie, of met de eruit afge­leide hulp­regels.

Regels met equivalentie zijn universeel (overal, altijd) toe­pasbaar. Dus zonder richting van evaluatie in de ex­pressie. Hoewel we normaal l-r vanaf links regels toe­passen in tekst.
De variabelen a en b reserveren we voor aas en bel links buiten de top array en links erbinnen. Alle varia­belen zijn natuur­lijke getallen, meest vanaf 1, niet leeg, maar cijfer 0 kan ook (en valt weg).

Aas­blazer A.I voor de klasse *{1} array rij.

  • A.0. a[bp] = pb
  • A.1. a[b,[]1 ≡ a[b1
  • A.2a. ,[n]]] A.2b. ,[n],,
  • A.3. ,[1n]1,[n]a,[1n]

De nul index ,[0] die in regel A.1. wegvalt, telt getallen direkt op in de bel. Die serie wordt pas bij uit­lezing met A.0. omge­draaid, wat optelt zoals de pop plus in blog §2.0, maar dan achteraf.
Een verdwaald nul element ,[]p in het midden laten we met rust, tot voor­gaande indexen zijn ver­dwenen en de lege array bij [b aan­komt. Pas dan popt de nulde komma weg, zodat para­meter p rechts bijtelt.

De eerste komma ,[1] kunnen we (zoals in de voor­beelden) noteren , zonder index. Deze om­zetting behoort niet strikt tot de definitie, en staat met a.1. in de lijst met hulp­regels.

Overbodige komma indexen worden met regel A.2b. opgeruimd. Wat wij blazen noemen, is dat het systeem deze dode elementen weer nieuw leven inblaast. Dat gebeurt in regel A.3. door de index array te her­stellen en aas a op te laden naar de nieuwe iterator.
Meestal volgt in een expressie achter de 1 nog een getal 1p, maar de regels ver­melden alleen tekens die nodig zijn voor de match.

Googologie 2.3

Een array is een reeks variabele getallen, met separatoren of seps ertussen. Blazer arrays zijn omvat met vier­kante haken [T] en van links­buiten gekoppeld aan (de laatste 1 in) het aas­getal a. Deze top array bevindt zich op niveau 0.
Ons sep teken is een , komma, maar niet precies als in functies. In blazer arrays hebben seps een index array [X] die de positie van iter­aties bepaalt en daar­mee ook hun functie.
Het type array blijkt uit het teken links van het opener [ haakje. Index arrays ,[X] koppelen we links aan een komma. Deze arrays kunnen zelf ook indexen bevatten, tot op elke ver­dieping of niveau. Functies met indexen genest op meerdere niveau's, zijn geneste arrays.

Een iterator of iter is een variabele in een recursieve functie. Die telt zijn iters af met een regel, die tegelijk een expansie toepast op een eerder deel van de ex­pressie (bij ons links van de iter).
Iters op rij zouden we net als in functies kunnen scheiden met enkele komma's. Blazer struc­turen slaan die tussen­stap in de notatie over. Onze solo komma , is een af­korting van de eerste sep, links in arrays. Van de para­meter ervoor op positie [0] vervalt de sep. Andere array posities houden op de voorste rij index [n] en in verdere rijen [n,T] index arrays, die (afge­zien van oneigen­lijke input) uniek zijn.

We vergelijken herhaalbare met unieke seps in googologie box 2.4. Googo­logie is de fenomeno­logie van feno­menaal grote getallen.

Aas­blazer heeft vloeibare arrays, bestaande uit suboperaties die vrij door elkaar kunnen bewegen, terwijl ze op evaluatie wachten. Zoals de elementen in een set, of zoals simpele eiwitten drijven in het medium van een bio­logische cel.
Ieder eindig iter getal met index array kan vrij worden verplaatst binnen de array die dit paar nest. Staps­gewijs, door wisselen a.6. slim te her­halen, ver­schuiven we deze paren. Die vrijheid bestaat, omdat we elke serie elementen ook apart zouden kunnen uit­werken en op­tellen. En op­tellen van eindige getallen is commutatief.

Daarentegen staan in vaste arrays de variabelen in volgorde op rij. Zoals de para­meters van een functie, of zoals genetische infor­matie om eiwitten te bouwen in een cel.
Het nadeel van variabelen die voor hun waarde afhankelijk zijn van de posities ervoor, is dat die structuur intact moet blijven, ook al zijn er iteraties afge­teld tot 0 (of 1). Maar in blazer systemen zijn posities ver­taald naar index arrays. We kunnen deze indexen samen met hun afge­telde iters wegblazen, om deze later te her­stellen, zonder dat dat effect heeft op de rest van de rij.

Gebruik is om de aftelling en verwijdering van iter 1 als geheel te zien en apart te definiëren. We lassen een einde getal ! lees­teken in met regel a.0. om die routine ineens a.3. te kunnen afsluiten.
Variabelen v zijn altijd v! gretig [regex: greedy] naar enen.

Hulpregels a.II bij evaluatie in Aas­blazer.

  • a.0. vv!x
  • a.1. ,c,[1]c
  • a.2. a[bp,Z] := a[,Z]+pb
  • a.3. ,[1X]1! ,[X]a
  • a.4. ,[X],[1X]1 ,[X]a,[1X]
  • a.5. ,[X]p,[X]q ,[X]pq
  • a.6. ,[X]p,[Y]q ,[Y]q,[X]p

We kunnen index arrays ook houden tot ze definitief onbruikbaar zijn. Vandaar de hulp­regel a.4. voor her­laden, zodat we index arrays maar een­malig hoeven in te voegen en daarna her­gebruiken.
Afgetelde iters wachten dan tot we er opnieuw a substi­tueren, zodat op­ruimen A.2b. over­bodig is. En dan hoeven we regel A.2a. alleen toe te passen op het einde van de top array.

Het herladen met a.4. van uit­gewerkte ex­pressies kan vanwege de diepe match van array [X] met array [1X] moeilijk worden. Maar in de praktijk mogen we ervan uit­gaan, dat een nieuw gevormde array sequentie X links en de array sequentie X rechts van de lege plaats gelijk zijn, zolang we geen elementen met a.6. ver­plaatst hebben.
Array functies die van grootschalige vergelijkingen afhangen ver­mijden we liever. Maar dat is van later zorg.

Er ontwikkelt zich een radix stelsel, zie blog §2.0, over de voorste rij met als basis aas a. Aantal en grootte van factoren c,d,e,f,.. is voor­alsnog onbe­perkt, maar we zouden ze ook naar gelang de basis 0<fi<a kunnen be­cijferen.

  • a[b,[2]1] = a[b,[1]a,[2]] = a[b,a] = a*a+b = a^2+b
  • a[,[2]1d] = a[,a,[2]d] := a[,[2]d]+a^2 == a^2*d1
  • a[b,[1]c,[2]d] := a[,[2]d]+a*c+b = a^2*d+a*c+b
  • a[,[3]1e] = a[,[2]a,[3]e] := a[,[3]e]+a^3 == a^3*e1
  • a[,[m]f] = a^m*f
  • a[b.,[mi]fi..] :n = a^mi*fi..+b :n

Een element ,[n]1 telt a^n bij de output op. Zodoende opent de telbare index de con­structie klasse *{2} voor nesten van arrays.

De structuren van de functie klassen *{k} in Aas­blazer her­gebruiken we als sjablonen voor de con­structie van grote getallen functies. Daar zijn dit con­structie types *{k} of con­structen.
In box 2.3 zagen we dat Aas­blazer bestaat uit vloeibare arrays met vrij te bewegen cijfers. Ook de recursies, vanaf regel A.3. verder, willen we universeel toe­pasbaar houden. Welke recur­sieve stap in wat voor array we wanneer zetten, het zou niet uit moeten maken.

Onze array functie Bellen­blazer krijgt vaste structuren, en blaast daar groei­bel b in omhoog, niet constante a, wat maximaal uit zal pakken. Hoewel Bellen­blazer's afge­telde elementen A.2. ver­wijderd worden, zijn indexen er niet zoals a.5. samen te voegen of a.6. vloeibaar. Recursies moeten we strikt l-r evalueren, anders wijkt de output af.
Lijkt of snelheid (A. laag, B. hoog) en vrijheid (A. hoog, B. laag) in array functies twee kanten zijn van dezelfde googo­logische munt…?!

X

§2.4 Aasnesten

We kunnen Aas­blazer gebruiken als super radix systeem, zodat ieder geheel getal een unieke input ex­pressie heeft. In radix ex­pressies zijn alle para­meters en indexen kleiner dan het basis getal a.
De Aas­blazer reductie­trein rijdt met aas a ver naar rechts de array in, vult station na station de voor­gaande elementen, tot getal a bij bel b aan­komt en uit­eindelijk optelt tot een groot output getal.

Aas­blazer A.II klasse *{2} geneste arrays.

  • A.0. a[bp] = pb
  • A.1. ,[]1 `= 1
  • A.2. ,[X]!!
  • A.3. ,[1X]1,[X]a,[1X]

De laatste regel is de recursie stap, daarvoor de eliminatie regels.
We nesten rood in blauw ,[X] als een situatie op elk niveau voor kan komen, groen in blauw ,[X] op top niveau.

In regel A.1. valt de nulde komma ,[] weg, ook als er links geen getal staat: aan het begin van een sub­array. Nul index elim is de enige aan l-r richting gebonden regel van Aas­blazer (hopelijk blijft dat zo). En dat komt alleen, omdat onze notatie mis­plaatste nul indexen toe­laat in de input, en output zoals altijd uniek bepaald moet zijn.
Universele regel A.2. verwijdert de sep van een afgetelde iter 0 aan een array einde of middenin, op elk nest niveau.

Hulpregels a.II blijven bij aas­nesten van kracht.
We zullen Aas­blazer index arrays nu dieper nesten, vanaf de tweede rij iters ,[d,1]c wat ook het tweede nest niveau ,[1] opent.

Tel met de 1e index e het aantal azen a*e in de exponent, en daar met de 0e index d enen bij op.

  • a[,[,[1]1]1] = a[,[,1]1] = a[,[a]1] = a^a
  • a[b,[,1]c] = a[b,[a]c] = a^a*c+b
  • a[,[1,1]1] = a[,[,1]a] = a^a*a = a^a1
  • a[,[1,1]c] = a^a1*c
  • a[,[2,1]1] = a^a2
  • a[,[d,1]1] = a^ad
  • a[,[,2]1] = a^(a*2)
  • a[,[,e]1] = a^(a*e)
  • a[b,[d,e]c] = a^(a*e+d)*c+b

Door deze super radix een index dieper te nesten, gebruiken we al een dubbele expo­nent, zoals in expo­nentiële notatie.
Zo is 10[,[3,1]2] = 2E13 een recent schulden­plafond van de Ameri­kaanse over­heid, namelijk twintig biljoen dollar [US$ 20 trillion].

In Aas­blazer is elk element een machts­factor: de index array vormt een macht van a met rechts zijn factor of cijfer. Als we de machts­factoren binnen een geneste array met regel A.3. uit­werken, zetten we die array om naar een index. Dit getal fungeert dan weer als expo­nent, ergens in de brede boom van expo­nenten van grondtal a.

Druk de dubbele exponent uit over de index rij in het 1e nest, waarvan de nulde index in het 2e nest de posities aangeeft.

  • a[,[,[2]1]c] = a^a^2*c
  • a[,[d,[2]1]1] = a^a^2*a^d = a^(a^2+d)
  • a[,[,[1]e,[2]1]1] = a^(a^2+a*e)
  • a[,[,[2]2]1] = a^(a^2*2)
  • a[,[,[2]f]1] = a^(a^2*f)
  • a[,[,[3]1]1] = a^a^3
  • a[,[,[3]g]1] = a^(a^3*g)
  • a[,[,[n]1]1] = a^a^n

Als we een groot getal in een radix noteren, verschilt de expressie lengte 10 niet signi­ficant van de unaire vorm. Zonder index­ering, in een radix systeem waar machten gegeven zijn door hun plaats, scheelt dit slechts de eerste expo­nent in de machts­toren. Dus radix ex­pressie lengte is nauwe­lijks kleiner dan het grote getal zelf.
De recursie in regel A.3. definieert Aas­blazer als radix, en de rest is index­ering. Daarom is Aas­blazer een minimaal algoritme.

De input expressies van non-random grote getallen blijven in de Aas­blazer super radix leesbaar, omdat er geen reeks nullen toe­gevoegd hoeft te worden. Ons systeem heeft het cijfer 0 niet nodig. Ook lege plaatsen hoeven niet voor te komen, als we elementen bij hun laatste iteratie meteen via regel a.3. opruimen.
Toch is in de uitwerking van grote getallen de structuur van de super radix verre van beperkt. Het aantal elementen dat Aas­blazer voor de evaluatie van a^a^n in gebruik neemt is a^n. Tijdens onze super radix passages wordt de ex­pressie lengte vanzelf groter dan bij een tradi­tionele radix, maar blijft nog kleiner dan bij unaire notatie.

Googologie 2.4

Als we telbare of meervoudige separatoren ,[S].. hadden gebruikt (wel met het­zelfde array), dan zou zo'n systeem de begin positie van elke index rij uitsparen.
Hierboven representeert d dat meervoud. De index rij in S zou daarop met Aas­blazer's e beginnen, waar die meer­voudige e moet itereren over aan­tallen {d} via een aparte regel.

Om meer expansie uit onze seps te halen, kunnen we deze beter met iter en al her­halen. Zo'n array systeem (dat o.a. Bird toepast) heeft ook bewerke­lijker regels, om rij lengte en de maten van dimensies te vergroten.
Een paar van sep en iter vormt een element, dat zich in een rij in rij structuur op een bepaald nest niveau bevindt.
Doordat de exacte positie, die een iter betekenis geeft, afhangt van voor­gaande index arrays, staan alle elementen vast in de file, binnen lagen van array dimensies. Afge­telde elementen tussen­in mogen niet ver­vallen. Wij zouden het cijfer 0 kunnen in­lassen, of (zoals bij Bird) iter­atoren af­tellen tot 1, en deze alleen rechts uit arrays verwijderen.

Vergelijk de indexering van Aas­blazer met een systeem dat meer­voudige komma's her­haalt. Dit schetst via gelijk­heid van separa­toren het dimen­sionale karakter van onze dubbel geneste [n] index.

  • ,[d] = , (sep in rij 1)
  • ,[,1] = ,, (open rij 2)
  • ,[d,1] = , (sep in rij 2)
  • ,[,e] = ,, (rij sep in vlak 1)
  • ,[,[2]1] = ,,, (open vlak 2)
  • ,[,e,[2]1] = ,, (rij in vlak 2)
  • ,[,[2]f] = ,,, (vlak in kubus)
  • ,[,[3]g] = ,{4} (3e in 4e dim)
  • ,[,[n]m] = ,{n1} (dim seps)

Als dezelfde index arrays herhaald worden binnen hun dimensie, lijkt zo'n structuur op een matrix. Deze matrix notatie loopt per nest een niveau op onze notatie uit. Het meer­voudige aspect scheelt daarbij maar één index, dat gaan we nu achter­wege laten.

Dan blijkt hoe het tweede niveau [n] bij unieke seps overeen komt met het eerste niveau [n1] van her­haalde seps. Binnen sub­arrays zal weer het­zelfde structuur ver­schil gelden.
De vertaling van het ene naar het andere systeem is daarmee gegeven. De unieke indexen in onze blazer systemen zijn twee keer zo diep genest als met her­haalbare indexen het geval zou zijn.

In Aas­blazer kan elke array tot een getal herleid worden, dat voor de array erboven een nieuwe expo­nent uit­drukt. Een her­halende matrix structuur zou per geneste array twee expo­nenten aan die machts­toren toevoegen.
Als we dieper nesten, blijkt dat de super­exponent a^^n van tetratie precies bereikt wordt op nest niveau n in Aas­blazer. Als we dus onze super radix zouden matrix her­halen tot diepte n, dan zou de super­exponent a^^nn ver­dubbeld worden. Dat is minder schoon.
De esthetiek gebiedt, dat uniek indexeren de natuurlijke notatie voor array functies is.

De overeenkomst tussen nest niveau's en de uitgedrukte expo­nenten blijkt gaandeweg: een volgende ver­dieping van de index voegt een expo­nent toe aan de machts­toren van de output.

Een array niveau dieper, voegen we de derde exponent toe aan onze super radix, met de index in het 3e nest.

  • a[,[,[,[1]1]1]1] = a^a^a = a^^3
  • a[,[,[,1]1]c] = a^^3*c
  • a[,[,[,1]e]1] = a^^3^e = a^(a^a*e)
  • a[,[d,[,1]e]1] = a^(a^a*e+d)
  • a[,[,[1,1]1]1] = a^(a^a*a) = a^a^a1
  • a[,[,[,2]1]1] = a^(a^a*a^a) = a^a^aa
  • a[,[,[f,g]1]1] = a^a^(a*g+f)
  • a[,[,[,[2]1]1]1] = a^a^a^2
  • a[,[,[,[2]h]1]1] = a^a^(a^2*h)
  • a[,[,[,[n]1]1]1] = a^a^a^n

In theorie zijn alle gehele getallen in dit domein uniek uit te drukken met cijfers 0<ci<a in deze super radix. Maar prak­tisch kunnen we slechts enkele markante grote getallen schrijven.
De lengte van random getallen 11 input in Aas­blazer is vanaf tetratie vrijwel gelijk aan de lengte als enen output. Zelfs in het domein tot 10^^4 ont­snappen de meeste getallen aan al onze fysisch mogelijke notatie systemen, willen we wedden…?!

Geneste arrays in Aas­blazer werken algemeen uit tot aan tetratie.

  • a[,[,[,[,[1]1]1]1]1] = a[,[,[,[a]1]1]1] = a^a^a^a = a^^4
  • a[.,[..1].1] :n: = a^..1 :n = a^^n
  • a.[pi,..qi] :n>0: = a^(..1..)*qi+pi :n:

Neem een Aas­blazer expressie met geneste index op niveau 5 gelijk aan tetratie 2^^6. Tijdens de reductie daarvan tot een reeks enen, zal de top array een aantal van 2^^5 factoren bevatten met elk hun eigen index array.
Voor de fysische uit­werking van zulke getallen zijn er in het hele heelal niet genoeg quantum bits. De quantum bit radix van de kosmos kan random getallen schrijven tot 2^10^120 of daar­omtrent (kleiner waar­schijnlijk omdat de natuur­wetten deze infor­matie comprimeren).

Dat Aas­blazer een minimaal systeem is, maakt het geschikt voor het opmeten van systemen voor grotere getallen. Op een expo­nent na telt onze super radix de elementen in array systemen, die hun iteraties inbedden in dezelfde structuren.
We ontwikkelen Aas­blazer verder als super radix, terwijl we aas a blijven substi­tueren, en nieuwe regels afpassen op de super­machten. Zo zullen we auto­matische sjablonen vormen voor de struc­turen van Bellen­blazer, die bel b op­laadt, maar geen rare andere regels toepast. En wat compu­teerbaar is, is in hogere zin weer recursief…!
Maar voorlopig gaan we met behulp van (de maximale structuren van) onze minimale functie een maximale getallen­blaas­machine ijken.

Lastig is nu nog om de overgang tussen types recursie te faci­literen. Een hogere index n in Aas­blazer zal a^^n tellen bij het output getal. Con­struct *{2} bestaat uit geneste rijen. Een nieuwe regel zal dus de nest diepte ex­panderen, met één ver­dieping per stap, waarmee we naar con­struct *{3} uitbreiden.
Is de vraag wat die simpele regel in Aas­blazer is, waarvan de limiet naar de volgende super­macht a^^^ω gaat…?

X

§2.5 Bellenblazer

We bouwen een record getallen functie met simpele, natuurlijke regels. Bellen­blazer plaatst bel b buiten de functie array, als tweede operant: de aas links, de bel rechts, en a[X]b de iteraties in het midden.

Door aas a op te tellen groeit bel b, waarmee we afge­telde iter­atoren nieuw leven in­blazen. Het idee van dit bellen­blazen is, dat op­laden van elke soort iter met sub­totaal b maximaal zal zijn.
We hervullen de bel positie meteen met a, wat niet echt lang­zamer is dan een regel die b laat staan (en een kopie oplaadt).

Begin met algoritmisch verantwoord optellen in Bellen­blazer.
Enkele , komma's staan voor een positie met index [1].

  • a[,[1]2]b = a[,[]b,[1]1]a = a[b,1]a = a[,1]ba = a[]ba = ab

Net als in Aas­blazer A.I zorgen we, dat de nulde sep aan het array begin wegvalt, zodat getallen b+a op­tellen. In blazer arrays wordt bij iedere iteratie de nieuw bij­getelde serie a.. veel langer dan de reeds in b inbe­grepen reeksen, en naar iters op­geladen bellen worden van de linker zijde weer afgeteld.
Bij oneindige getallen luistert de aflezing van de uitkomst nauw. Cantor telde getallen 1.. en ω on­eindige reeksen 1... standaard aan de rechter kant op bij reeksen die hoger on­eindig waren.
In arrays met oneindige azen zijn onze nieuwe reeksen a... hoger on­eindig dan vorige bij b getelde. Die tellen we dus van rechts bij, om van links weer af te tellen. Maar bij de presen­tatie moeten we bel b omge­keerd uit­lezen, om het standaard on­eindige recht te doen.

De elementaire iteraties: iter c met index [1] telt aas a herhaald op, iter d op positie 2 repeteert *a deze factoren, en de 3e iter e stapelt dat weer als ^a machten, te berekenen vanaf de hoogste exponent.

  • a[,[1]1c]b = a[,c]ba == a[,1]ba{c} = a[](b+a*c) = a*c+b
  • a[,[2]1d]b = a[,[1]b,[2]d]a = a[,[2]d](a*b) == a[,[2]1](.a*..b) :d = a^d*b
  • a[,[3]1e]b = a[,[2]b,[3]e]a = a[,[3]e](a^b) == a[](..a^.b) e: = a^^e\^b

We construeren de rij in Bellen­blazer als de array operatie voor super­sterren. Ex­pressies worden steeds l-r vanaf links opgelost.
Om de voorste rij iteraties in Bellen­blazer kloppend te krijgen, tellen we iters op rij tot 1 af en ruimen ze dan op. Alleen de indexen aan het begin van arrays vallen bij waarde nul weg.

Evaluatie van Bellen­blazer expressies passeert (na een stroef begin) sneller dan super­ster operaties. Regels in beide systemen ver­schillen een beetje.
Twee passages uit de evaluatie naar a^^^f3 enen. Wat super­pop­sterren doen in stap 2 en 3, vat Bellen­blazer samen met de 4e stap.

  • a*{4}f3 = a*{3}+a*{4}f2 = a*{3}a*{3}+a*{4}f1 = a*{2}+a*{3}a-*{3}+a*{4}f1 == a^^a*{3}+a*{4}f1 = a^^a*{3}+a*{3}+a*{4}f = a*{3}a^^a*{3}+a*{4}f == a^^^3*{3}+a*{4}f
  • a[,[4]4f]0 = a[,[3]0,[4]4f]a := a,[3],[4]3f = a,[4]3f = a,[3]a,[4]2f == a^^a,[4]2f = a,[3]a^^a,[4]1f == a^^a^^a,[4]1f = a,[3]a^^^3,[4]f == a^^^4,[4]f

Elke volgende iteratie levert een hogere super­macht op. Bellen­blazer's iters lopen steeds 1 achter bij de super­exponent.
Formuleren we de voorste rij van Bellen­blazer, zijn lineaire array, in termen van super­macht operaties.

  • a[,[2n]2f]1 := a,[2n]1f = a,[1n]a,[2n]f = a^{n}a,[2n]f == ..a^{n}.a f: = a^{n1}f1 = a*{n2}f1
  • a[.,[1ni]1fi..]b :r {b>0} = ..a^{ni}fi\*{ni}.b r: = b.*{ni}+a*{1ni}fi.. :r
Onze evaluatie tekens, met voor­waarden om de linker (sub)ex­pressie door de rechter (sub)ex­pressie te ver­vangen:
 = Past één of enkele regels toe, of een bekende substi­tutie.
== Grote iteratie over de voor­gaande evaluatie.
:= Omzetten van ex­pressies naar simpeler format.
°= Woord ver­vangen aan het ex­pressie begin, of aan het eind. Bedoeld als tweede helft van een regel.
`= Woord dat het eerst matched aan­passen, terwijl we l-r (naar rechts) door de ex­pressie scannen.
 ≡ Equivalent woord dat we op enig moment in de evaluatie kunnen ver­vangen, maar eerst l-r is dit ver­plicht.

Bellen­blazer B.I. construct *{1} array rij.

  • B.0. a[]bp = pb
  • B.1a. a[b,Z]p = a[,Z]bp B.1b. ,[]1 `= 1
  • B.2a. ,[n]!! B.2b. ,[n]1!!
  • B.3. ,[1n]1 `= ,[n]b,[1n] && a[X]b = a[X]a

Na een uitroepteken ! volgt rechts ervan geen getal meer, maar bijv. een komma , of array ] eind. Nul verdere enen dus, aan­gezien we met unaire getallen 1.. werken.
Binaire code kan aan getallen een 0 vooraf laten gaan, en andere ex­pressie tekens coderen als 001{n} prefix met nummer.

Regel B.3. itereert over de *{1} rij structuur, waarmee Bellen­blazer super­machten uit­drukt. De primitieve stap bij n=0 met de lege sep die wegvalt in regel B.1. betreft op­tellen *{0} met aas a.
Klassieke functie recursie met nesten van subexpressies is on­nodig, want het op­laden naar rechts van bel b wordt toch wel maximaal.

Hulpregels b.I voor Bellen­blazer.

  • b.0. vv!x
  • b.1. ,1,[1]1
  • b.2. a[,Z]a := a,Z
  • b.3. a[,1Z]b = a[,Z]ba

Voor het opladen van index arrays hebben we een nieuwe regel nodig. Want op het moment dat een geneste index leeg komt, is een grote b juist geladen in de iter. De nieuwe index moet dus van rechts buiten de array komen. Zie de definitie voor geneste arrays in blog §2.6.
Hier demonstreren we alleen Bellen­blazer's eerste index, verge­leken met Conway's pijl­ketens.

Conway's pijlketen 12 [chained arrows] is een recur­sieve functie van John H. Conway, om grote getallen ver voorbij de Ackermann functie te kunnen noteren.
Definitie van de rij met Conway's pijl separatoren.

  • ab = a^b
  • X1 = X
  • X1z = X
  • Xy1z1 = X(Xyz1)z

Voorbij de supermachten abc betreden we het domein van de hyper­machten en de snel groeiende hierarchie. Vage aan­duidingen voor getallen, waar we concrete grenzen zullen moeten vinden.
Steeds zetten een paar iteratoren z in y een dubbele recursie in over de keten. Afgeteld vallen deze rechts van de rij af, zonder te worden her­laden. Conway's pijl­keten is dus een tripel recursie.

We benaderen Graham's getal uit blog §2.2 met recursie over super­sterren door 3[,[1,2]65]5 in de tweede passage hier­onder.
Het Bellen­blazer getal is minimaal kleiner <≈ dan Graham's getal, de­zelfde ex­pressie met a=4 is al veel groter. Meestal nemen we het niet zo aas nauw met onze minimaal groter ≈> benaderingen.

  • a[,[,[1]2]c]b = a[,[,[]c,1]b]a = a[,[c]b]a := a,[c]b = a*{c}b = abc-
  • a[,[1,2]2c]b := a,[,2]b,[1,2]1c = a,[b]a,[1,2]1c = a*{b}a,[1,2]1c = a*{a*{b}a}a,[1,2]c == a*{..b..}a :c1: ≈> aac12 {a>2 b>2} = aa(aac2) == aa(..a^a..) :c:
  • a[,[2,2]1c]1b := a,[1,2]1b,[2,2]c = a*{..a..}a.,[2,2]c :b: ≈> aab2,[2,2]c {a>2} ≈> aa(aab2)2,[2,2]c- ≈> aa(..b..)2 :c: ≈> aac3
  • a[,[1d,2]1c]1b := a,[d,2]1b,[1d,2]c ≈> aabd1,[1d,2]c ≈> aa(..b..)d1 :c: ≈> aacd2

Op zichzelf drukt Bellen­blazer's 0e index super­machten uit, net als een pijl­keten met 3 para­meters. Deze ronde houdt die 0e index d gelijke tred met Conway's 4e parameter.
Volgende rondes loopt index d ongeveer gelijk met de para­meters van heel Conway's pijl­keten. En gelijker nog met een pijl­keten variant, die zijn laatste para­meter zou af­tellen tot z=0 in plaats van 1.

  • a[,[,3]c]1b := a,[c,2]1b ≈> aabc1
  • a[,[1,3]1c]b := a,[b,2]a,[1,3]c ≈> aaab,[1,3]c ≈> aaa22,[1,3]c- ≈> aaac2
  • a[,[1d,3]1c]1b := a,[d,3]1b,[1d,3]c ≈> aaabd1,[1d,3]c ≈> aaa2d2,[1d,3]c- ≈> aaacd2
  • a[,[,4]c]1b := a,[c,3]1b ≈> aaabc1 ≈> aaaac1
  • a[,[d,4]1c]a ≈> aaaacd1
  • a[,[d,e]1c]a ≈> a..cd1 :e>1

Met index e maken we in Bellen­blazer de sprong van super­machten over de hele lengte van Conway's pijl­keten. Onze 1e index is dus even snel als Bird's 4e ingang [entry], gegeven het bewijs 13 dat zijn 5e ingang voorbij Conway's pijl­ketens gaat.

{a,b1,c,d} ≈>
  a..bc1 :d
  ≈ a[,[c,d]1b]a
  := a,[c,d]b1

Na een langzame start produceert Bellen­blazer getallen van maximale grootte. Vanaf hier zal elke (on­even geneste) array onge­veer gelijk aan Bird's arrays zijn. Dat moeten we steeds bewijzen, door onze output te verge­lijken met de getallen in de PDFs 13 die Chris Bird bij MRob deponeerde.
Wie er precies voorloopt nu? Misschien wil iemand onze demon­stratie over­doen, ten op­zichte van Bird's lineaire array functie…?

X

§2.6 Belnesten

We stellen ons voor dat een structuur omvat door gelijke stucturen in de diepte is genest, niet in de hoogte. 14 Dieper geneste ex­pressies be­schrijven grotere getallen, zoals een ver­haal dat groeit, als we meer letters naar rechts lezen en zinnen naar onder.
Op nest niveau 0 bevindt zich de top array. Met iteratoren, die Bellen­blazer aftelt als in definitie B.I voor con­struct *{1}. De posities van iters noteren we met indexen: rijen dik, rijen diep. Binnen deze index arrays is iedere index ook weer een iter met een index array.

Bellen­blazer B.II con­struct *{2} geneste arrays.

  • B.0. a[]bp = pb
  • B.1a. a[b,Z]p = a[,Z]bp B.1b. ,[]1 `= 1
  • B.2. ,[1V]1!!
  • B.3. [,[1V]1T]c `= [,[V]c,[1V]T]b && a[X]b = a[X]a

Deze definitie nest de bel en telt de begin iter in sub­arrays af tot 0 en de erop volgende iters tot 1.
Als we regel B.3. op top niveau toepassen geldt in aanvang c=b en nadat de regel die nest als index, vervangt b=a de bel. Dat werkt net aan. Bij toe­passing op geneste arrays zal zojuist in de stap ervoor c zijn op­geladen met de bel, en deze al vervangen door a. Dat komt gek genoeg op het­zelfde neer.

De array functies van Bowers & Bird rollen steeds series van gelijke separa­toren uit, waar elementen binnen hun ruimte her­haald worden. Dat ver­dubbelt de ex­pressieve kracht van elk nest niveau ten op­zichte van ons bellen nesten.
We hebben dit al eens eerder bewezen. Eerst demonstreerden we dat ons index her­halende Btrix systeem, dat dimensies telt versus b een rij voor B&B, qua nesten niet verder uit­loopt c.
Bij de vloeibare arrays van Alexa d ontdekten we een dubbele nest diepte, verge­leken met her­haalde index arrays. Dat noemden we toen half geneste arrays e, aan­gezien elk nest op halve kracht werkt.
De output van een systeem dat unieke index arrays 2*n keer nest, is het­zelfde als bij her­haalde index­ering over n niveau's (bij gelijke regels). Het gaat er puur om hoeveel infor­matie struc­turen bevatten.

Ga dit rustig na voor hun (herhaalde separa­toren, elim 1, van B&B) versus uw (unieke seps, elim 0).
Hun rij komma's is uw 0e index,
hun 0e index 2 is uw 1e index,
hun 0e index is uw rij met diepe 0e index,
hun 1e index 2 is uw diepe 1e index 1,
hun 1e index is uw diepe 1e index,
hun index rij is uw diepe index rij.

Evenwel, die factor 2 snellere nesting is insignificant vergeleken met de getallen die beide functies produ­ceren. Als we nest­diepte zelf op­blazen binnen een volgende structuur, valt dit ver­schil in het niet.

a. Keer de richting van de para­meters om, zodat de laatste para­meters de grotere getallen maken, gg: Péter's recursion in "Number operations" voor bigPsi (concept 2011).
b. Bird's lineaire array lengte is gelijk aan Btrix' multi­dimensionale index, gg: Cubic and Dimensional in "Bea's dimensions" voor Beatrix matrix (web 2014).
c. Btrix dim-rij wisseling is even snel als Bird's rij-dim wisseling, verder nesten ver­andert deze struc­turele afstand niet, gg: Nesting depth in "Beat nested arrays" voor Beatrix matrix (web 2014).
d. Als alle sub­structuren uniek zijn, ver­dubbelt dit het aantal geneste niveau's, gg: Sentry to row format in "Alexa 2nd - Fluid Structures" voor Iteror's Brobding­nagians (blog feb 2015).
e. Onze arrays zijn half genest, gg: Arrays at any depth in "Half nested arrays" voor Iteror's Big number systems (blog okt 2015).
1. Recursie met k variabelen leidt niet buiten de klasse van de primitief recursieve functies, p.75 in Rozsa Péter "Recursive Functions" 1967, 1950.
2. Het is belangrijk om te begrijpen dat eindige getallen extreem groot kunnen zijn, in Donald Knuth "Coping with Finiteness" 1976.
3. Een vergaande generalisatie van Ramsey theorie [grafen theorie], Martin Gardner over Graham's number, in "Mathe­matical Games" Scientific American, Nov. 1977.
4. Het hoogste getal dat ooit in een rekenkundige proef werd gebruikt, Guinness over Graham's number, p.59 in "Het groot Guinness record boek" 1989.
5. Deze bovengrenzen zijn meestal enorm, Ron Graham over Graham's number, in R.L. Graham & B.L. Rothschild "Ramsey's theorem for n-parameter sets" 1971.
6. Deze recursies [over c] zijn geen normale, staps­gewijze, in David Hilbert "On the infinite" 1925, p.388 in "From Frege to Gödel" 1967.
7. De functie F(a,a,a) neemt sneller toe dan elke type 1 functie in Wilhelm Ackermann "On Hilbert's con­struction of the reals" 1928, p.495 in "From Frege to Gödel".
8. Het is voldoende om een tweetallige 'majorant' ψ(m,n) te definiëren, p.106 in Rozsa Péter "Recursive Functions" 1967.
9. Elke klasse En van recursieve functies is gesloten onder de operaties van substi­tutie en beperkte recursie, in Andrzej Grzegorczyk "Some classes of recursive functions" 1953.
10. Hoe codeer­systemen, codes en unieke descripties relateren aan waarschijn­lijkheid, ch.4 in Peter D. Grünwald "The minimum description length principle" 2007.
11. Het begrip random bij getallen heeft vele lagen, p.124 in Gregory Chaitlin "Meta maths, the quest for omega" 2005.
12. Onze eigen pijlketen notatie benoemt nog veel grotere getallen, p.61 in Conway & Guy "The Book of Numbers" 1996.
13. Een systeem voor snel groeiende recursieve functies, dat de functies van Jonathan Bowers en anderen ver te boven gaat, in Chris Bird's Super Huge Numbers, een serie van 9 PDFs over Bird's arrays + 3 bijlagen, 2014.
14. Shàng betekent zowel boven als eerder, xià betekent onder en volgend, p.137 in James Gleick "Time Travel, a history" 2016.
Gulliver redt de vloot van Lilliput

Blogboek  index

  1. Tellen
  2. Rijen
    1. Herhalen
    2. Machten
    3. Supermachten
    4. Aasblazer
    5. Aasnesten
    6. Bellenblazer
    7. Belnesten

© 2017
Giga Gerard