Reuzen Getallen Bouwerij

bij Giga Gerard

“Kom mee naar buiten allemaal,
Dan zoeken wij de wielewaal.
En horen wij die muzikant
Dan is zomer weer in 't land!”

Canon

X

§3. Diepen

In het vorige hoofdstuk §2 ontwikkelden we een plan voor het maken van grote getallen. De komende serie blogs bouwen we weer van de grond af op, tot we uitkomen bij de diepen, die voorbij geneste arrays liggen, in Giga Gerard's:
„Reuzen Getallen Bouwerij”.

Aan elkaar gebouwde arrays [Xi].. noemen we diepen. Iedere geneste array kan uitgebreid worden tot een diep.
Als een index array is uitgeteld [][1Xn] en in de volgende array tellen we de eerste index af, dan blazen we daarmee het aantal nest niveau's met diepen in de eerste recursief op.
Met diepen na de top array geven we een ander type indexen aan, met name voor groter eindige ψi limieten of hoger oneindige ωi.

Vogel arrays vormen onze simplistische benadering van de arrays van Chris Bird.0 Doordat het Vogel systeem gelijk op vliegt met Bird, en ons Wielewaal telraam te vergelijken is met Vogels, zullen we toch uiteindelijk een elegant wereldrecord getal voorbij zien fladderen.
Al zulke arrays geven als uitkomst reusachtig grote getallen. Zo groot, dat de complete evaluatie van expressies alleen in theorie, maar praktisch niet uitvoerbaar is.

Lectori salutem Dudeldjo en anders niet.

X

§3.0 Supertrio

Dit blog introduceert een telraam of array systeem, dat een groeiende variabele a substitueert in de structuur van de radix Aasblazer.
We spreken hier van een telraam als we alleen getallen kopiëren en verschuiven. Voorbij de rij structuur kopiëren we indexen om posities aan te geven en die groeien uit tot geneste arrays en diepen.
Ook tellen we iteraties tot 0 stappen af, zodat tellers of iteratoren leeg komen te staan ,, tussen aangrenzende separatoren (komma's of index arrays).

Natuurlijke getallen schrijven we met het teken 1 als een serie enen 1.. en zulke variabelen a en b tellen direkt op als ab.
Als 1 de positieve eenheid is, is het minus teken - de negatieve eenheid. Zo is 1-=0 leeg en een getal n1 telt - af tot n.
Deze basis voor getallen heet unair. Daar staat 2 voor 11, een 3 voor 111 en zo voort. Getallen in het tientallig stelsel schrijven we liever 108. met decimale punt.

Reeksen binnen expressies noteren we eenvoudig zo:
In ^{n} herhalen we het ^ macht teken n keer. Dat is trouwens hetzelfde als *{n1} met repetitie van supersterren.
Met punten selecteren we een woord .groep.. en met de rep herhalen we deze :n aantal keer op die plaats.
Indexen i of j incrementeren we tijdens een repetitie vanaf 1. Ook zijn er dubbelzijdige :n: reps. Het wijst zichzelf.

De primitieve functies van ons Wielewaal telraam zijn optellen en kopiëren. Tel een kopie op en een getal a verdubbelt aa. Herhaal dit c keer en het totaal a*2^c groeit exponentieel.
Na deze machtige start noteren de tellers in het telraam nog hogere recursies of vormen van herhaling. En we schuiven een kopie van subtotaal a' door naar rechts om lege tellers opnieuw op te laden.

Het kan veel sneller, met Knuth's pijl operaties a^{c}b bijvoorbeeld. Deze supermachten worden ook bij Bird met slechts drie parameters {a,b,c} genoteerd. Samen vormen de constante a, recursie teller b en super teller c het zogenaamde supertrio.
De beperkte functie input geeft super output, omdat elke superstap een subexpressie nest op de plaats van de recursie stappenteller. Deze subexpressie $ is een minimaal kleinere kopie van de expressie, die maar één stap minder bevat.

Bird substitueert subexpressies $ bij elke hoge recursie in zijn arrays. Dat is overbodig. Het is voldoende als we in onze Vogel benadering van Bird de subexpressie enkel nesten in parameter b.
Ook vinden we het jammer dat Bird in navolging van Knuth en Conway met ^ machtsverheffen begint. Natuurlijk is de eerste herhaling een * vermenigvuldiging, zodat met drie tellers V(a,b,c) de supersterren a*{c}b worden weergegeven.

Vogel trio definitie V.O.

  • V.0. (a) = a
  • V.1. (a,b1) = (a,b)a
  • V.2a. (a,1) = a V.2b. (a,b,1) = (a,b)
  • V.3. (a,1,c) = a
  • V.4. (a,b1,c1) = (a,(a,b,c),c1)

Alle variabelen zijn natuurlijke getallen v>0, dus in Vogel expressies tellen we posities nooit leeg. Het is deze voorwaarde, die duidelijk maakt welke regel(s) van toepassing (kunnen) zijn.

Hieronder op het demonstratiebord herleiden we het Vogel trio precies tot supermacht operaties, waarmee ook Bird's array begint.
Klik op het dynamische bord <!--> om extra voorbeelden te tonen, of toets Ctrl-U en bekijk deze in de pagina bron.

  • V(a,2) = (a,1)a = aa
  • V(a,b) == a.. :b = a*b
  • V(a,2,2) = (a,(a,1,2)) = (a,a) = a*a = a^2
  • V(a,b1,2) = (a,(a,b,2)) == (a,..a..) :b: = a*..a :b = a^b1 = {a,b+1}
  • V(a,b1,c1) = (a,(a,b,c1),c) == (a,..a..,c) :b: = a*{c}(..a..) :b: = a^{c}b1 = {a,b+1,c} <!-->

Bird's arrays zijn omgeven door krulhaken {X} en hij telt er schools in op +1 en af -1.
We zullen Vogel en Bird vergelijken met een nieuwe array functie, die we vernoemen naar de toverachtige trekvogel uit een zomerse canon.

Hilbert dacht in 1925 misschien nog functie indexen nodig te hebben om hoger recursieve functies uit te drukken. In het bewijs uit 1928 van Ackermann werd de voorganger expressie zonder omweg genest.
Wij definiëren deze functies nu door getallen te dupliceren en te verschuiven over de parameter rij. De lengte van de eerste rij geeft dan de superexponent ^{r} van de uitkomst ervan.

Wielewaal is dus wat langzamer, omdat de herschrijf methode op de rij zo eenvoudig is. Later voorzien we posities van een kopie (min 1) van de volgende index array. Dat is even sterk als subexpressie nesten (allebei rij in rij), maar dan overal tegelijk.
Nadat we een vlak hebben gevuld, haalt onze derde index Conway's pijlketens in. Met Vogel en Bird's arrays komen we later gelijk, door over de diepte van geneste index arrays te itereren.

Definitie Wielewaal rij functie W.I.

  • W.0. a[] = a
  • W.1. a[1R] = a1[R]
  • W.2. a[R,] = a[R]
  • W.3. a[,{n1}1R] {n0} = a[,{n}a,R]

Elke iteratie stap telt 1 af, en we gaan door tot de teller 0 is. Zolang posities van tellers of parameters pi0 geen index krijgen, moeten de komma's ,, voor de lege plek blijven staan.

Onderaan bij Beo laten we andere functies zien die bellen omhoog blazen. Deze telramen lezen vrijwel gelijke getallen uit, want alleen hun beginregel verschilt. Het aantal super ^.. operatoren toont wel een glimp van de onvoorstelbare grootte ervan, maar Vogel functie V.I vordert significant sneller op de top rij.

Onze Wielewaal functie gaat snel van start door ab (tegelijk aas en bel) te verdubbelen en op te laden. Maar zonder subexpressie nesten blijft bellen b blazen relatief achter lopen in de volgende tellers op rij.

Tel b op bij a buiten de top array. Kopieer deze som in de stap van teller c en laadt die kopie in beller b. Dit geeft een recursie, waar de macht en factor 2^c de uitkomst domineert.
Klik op de borden <!--> voor uitwerkingen met getallen.

  • a[1b] = a1[b] == ab1[] = ab1
  • a[b,1] = ab[,1] = ab[ab] = ab*2 = V(ab,2)
  • a[b,1c] = ab*2[,c] = ab.*2.. :c1 = ab*2^c1 = V(ab,(2,c1,2))
  • a[b,c,1] = ab*2^c[,,1] ≈> 2^c[,ab*2^c] ≈> 2^(ab*2^c) ≈> V(ab,(2,c,2),2) <!-->

Een linker expressie is ongeveer groter ≈> dan de rechter expressie, als dit een vrij goede benadering is en de linker grotere output geeft voor bijna alle input waarden.
Voor a=b=c=1 in de eerste vergelijking gaat dat niet op, maar dat geeft niet. Bij waardes 2 is deze al over het kantelpunt heen.

  • a[b,c,2] ≈> 2^(ab*2^c)[,,1] ≈> 2^(ab*2^(ab*2^c)) ≈> abc^abc^2^c ≈> V(abc,3,3)
  • a[b,c,3] ≈> ab*2^(..c..) :3: ≈> abc^^4 = V(abc,4,3)
  • a[b,c,d] ≈> abc^^d1 = V(abc,d1,3)
  • a[b,c,d,1] ≈> abc^^d1[,,,1] ≈> abc^^abc^^d1 ≈> V(abcd,2,4) <!-->

Met drie tellers bouwt Wielewaal een toren van d exponenten. Dit is na + * ^ de vierde operatie ^^d en heet tetratie.

We passen expressies aan, door te stellen dat ab=b. Het missen van de begin a maakt op de huidige schaal bijna niets uit.

  • [b,c,d,e] ≈> bc^^..d1 :e1 ≈> bc^^^e1\^^d ≈> V(bcd,e1,4)
  • [b,c,d,e,f] ≈> bcd^^^^f1\^^^e ≈> V(bcde,f1,5)
  • [.pi,..q] :r ≈> pi..^{r}q1 :r > V(pr,q1,1r) > pqr ≈ {q,2,r+1} <!-->

Zo drukt dit blazer systeem W.I over de hele eerste rij supermachten uit, waar bij Vogel en Bird drie parameters volstaan.

Als we in deze structuur getal a constant houden en opladen, vormt zich over de top array een radix functie. In het laatste item, op de rij, blijven getallen dan onder de q1*a^r steken.
Uitgebreid tot superradix noemen we dit algoritme de Aasgier. Het verschilt in naam met onze Aasblazer en in format, omdat tellers op eerste geneste array rijen in komma's kunnen worden ingebed.

De Aasgier rij regels A.I lijken op die van W.I.

  • A.0. a[b] = b
  • A.1. a[b,1R] = a[ab,R]
  • A.2 = W.2.
  • A.3. a[b,{n1}1R] = a[b,{n}a,R]

Aas a is een constante: een radix 10 naar keuze.
Om dit als superradix te laten werken, moeten ook alle lengtes en tellers p<a zijn, tenminste in de input. Daarmee krijgen alle natuurlijke getallen een unieke expressie.
Het radix maximum is op de rij a[,{a}1]- en in basis a=10 het getal 9999999999.

Bij deze lineaire array met komma's is regel A.1. een speciaal geval {n=0} van regel A.3. voor commutatief optellen. Met oneindige getallen als Cantor's a=ω is omkeren nog altijd nodig.

Om tellers compleet p=0 af te tellen in Bellenblazer en toch dezelfde input waardes te schrijven, zullen we de oplaadregel aanpassen.
Ook nu telt de primitieve recursie de aas a op bij een bel b. Over de lengte van de rij worden de gewone supermachten uitgedrukt.

Definitie Beo rij functie B.I met komma's.

Op opladen in Beo zijn allerlei variaties mogelijk: groot, groter, grootst en toch zo goed als gelijk…

  • a[b,{n1}1R] <≈ a[a,{n}b,R]
  • <≈ a[b,{n>0}b,R]
  • <≈ a[ab,{n>0}b,R]

Zo produceren de oplaadregels steeds minder natuurlijke output, die ondanks minieme versnellingen ongeveer een supermacht ^ achter blijft bij onze snelstarter Wielewaal. Waar precies de verschillen insignificant worden mag u zelf uitvogelen…!

X

§3.1 Toprij

In dit blog komen we gelijk met de lineaire array van Chris Bird.1 Dit noemen we de Toprij: de eerste rij in de Vogel array op top niveau (niet de subexpressie, geen index array) met een maximaal algoritme.

Omdat Bird's array regels nogal gecompliceerd zijn, hebben we deze in de appendix versimpeld tot de definities U. In deze Uil systemen zijn sommige regels samengevoegd en de notatie is uniform, maar exact dezelfde expressies en getallen als bij Bird blijven bedoeld.

We vergelijken systemen U via V met W. In het blog §3.0 bestreken we drie parameters, het supertrio U.O ~ V.O waar we in Wielewaal W.I een hele rij voor nodig hadden.

Vogel rij definitie V.I.

  • V.0. (a) = a
  • V.1. (a,b1) = a(a,b)
  • V.2. (R,1) = (R)
  • V.3. (a,1,R) = a
  • V.4. (a,b1,1R) = (a,(a,b,1R),R)
  • V.5. (a,b,.1,..1R) :n1 = (a,a,.1,..b,R) :n0

Als een eerdere regel uit de lijst een match vormt met de expressie (of subexpressie), krijgt deze = voorrang in de evaluatie.
De afkorting R staat voor de rest van de array, hier een rij van recursie tellers of parameters pi>0. Woord R begint dus met een 1.. getal.

De Vogel toprij is goed te vergelijken met Bird's lineaire array U.I.

  • V(a,2,2,2) = (a,a,a) ≈> {a-1,2,1,2}
  • (a,3,2,2) = (a,a,(a,2,2,2)) ≈> {a-1,3,1,2}
  • (a,b1,2,2) = (a,a,(a,b,2,2)) ≈> {a-1,b+1,1,2}
  • (a,2,3,2) = (a,a,2,2) ≈> {a-1,2,2,2}
  • (a,3,3,2) = (a,(a,2,3,2),2,2) ≈> {a-1,3,2,2}
  • (a,b,3,2) ≈> {a-1,b,2,2} <!-->

Door bij superexponent c een 1 op te tellen, ondervangt Vogel zowel zijn begin achterstand als het hogerop nesten van subexpressies bij Bird. Regel V.4. nest voordien in b een extra subexpressie, die we en simpel opladen met regel V.5. om bijna gelijk uit te komen op de rij.
Bij b=2 verschuift de begin a naar plek c, daar moet dus a1 wat bij. Dankzij deze voorzieningen zijn Vogel expressies ≈> iets groter.

  • V(a1,b,c1,2) ≈> {a,b,c,2}
  • (a1,2,2,3) = (a1,a1,a1,2) ≈> {a,2,1,3}
  • (a1,b,c1,d) ≈> {a,b,c,d}
  • (a1,2,2,1,2) ≈> {a,2,1,1,2}
  • (a1,3,2,1,1,2) ≈> {a,3,1,1,1,2}
  • (a1,b,2.,1..,p) :n ≈> {a,b.,1..,p} :n1 <!-->

Voor uitwerking van de voorbeelden, klik het <!--> bord. Dan blijkt dat onze Vogel toprij met de aanpassingen a+1 en c+1 een verrassend goede benadering geeft over Bird's gehele lineaire array.

  • V(a1,b,1R) ≈> {a,b,R}

Ons eerste telraam, de Wielewaal rij, begon weliswaar sterk met verdubbeling, maar daarna viel de functie snelheid terug. In dit blog moeten we meerdere dimensies gebruiken, om hetzelfde te bereiken als Chris Bird0 met zijn eerste dimensie, de lineaire array.
We positioneren alle tellers met indexen en itereren daar weer over met een geneste array. In een superradix pakt complete indexering natuurlijker uit dan Bird's repeterende array ruimtes, hoewel onze arrays twee keer zo diep genest worden, zie box 2.6.

We herladen afgetelde iteraties met een kopie van bel a, maar anders dan in de geneste arrays van Bellenblazer blijft de originele bel op zijn plaats. Zo kunnen we garanderen, dat het getal wat we substitueren maximaal blijft. En dat is niet triviaal, gezien de nogal bewerkelijke cascade bij het herladen van geneste index arrays.
Bellenblazer en zijn Beo varianten, die we eind §3.0 zagen, zijn maar een beetje (insignificant) trager. De standaard expressies van Beo en Bellenblazer beginnen exact met de *{c} supermachten, net als de Vogel rij. Dat is wat we natuurlijk noemen in dit gebied.
Hier wijken we daarvan af. Voor onze recordpoging maken we het formuleren van nieuwe regels liever wat makkelijker.

Onze scanner zoekt bij een regel A`=B vanaf links in de expressie een match voor woord A om dit te vervangen door woord B. Regels die de hele expressie = evalueren gaan voor. Bij equivalentie kan een woord overal in de expressie worden vervangen.
Er is dus geen precedentie vanwege de volgorde van de regels, zoals bij Bird. De meest linkse match wordt het eerst verwerkt.

Definitie Wielewaal nest functie W.II.

  • W.0. a[] = a
  • W.1. a[1R] = a1[R]
  • W.2. ,[S]00
  • W.3. ,[]0
  • W.4. ,[1S]1 `= ,[S]a,[1S]

Bij regel W.4. staat variabele a voor het actuele subtotaal, dat buiten a[,R] de array verzameld is. Daarbij is b=0, omdat we regel W.1. eerder l-r toepassen.

Met twee hulpregels om de eerste rij van iedere array in het lineaire format te kunnen := noteren. Geval n=0 zou niet werken.

  • W.a. [,{n}1 := [,[n]1 {n>0}
  • W.b. ,[m]1p,{n}1 := ,[m]1p,[mn]1

Uiteindelijk willen deze arrays vergelijken met de geneste arrays van Bird4. Drie Vogel parameters drukten de Wielewaal rij van W.I uit, dus eerst moeten we de lineaire array van Vogel V.I nog inhalen.

  • [a,[,1]1] = a[,[a]1] = a[,[a-]a] := [a,{a-}a] ≈> a*{a}a1 ≈> V(a,a,a)
  • [a,[1,1]1] = a[,[a]a] ≈> a^{a}a1 ≈> (a,a1,1,2)
  • [a,[2,1]1] = a[,[1,1]a] = a[,[a]a,[1,1]a-] ≈> a^{a}a1[,[1,1]a-] ≈> a^{..a..}a1 :a: ≈> (a,a,..a1..) :a: ≈> (a,a1,2,2)
  • [a,[3,1]1] = a[,[2,1]a] = a[,[']a,["]a-] ≈> (a,a1,2,2)[,["]a-] ≈> (a,..a1..,2,2) :a: ≈> (a,a1,3,2)
  • [a,[,2]1] = a[,[a-,1]a] = a[,[']a,["]a-] ≈> (a,a1,a-,2)[,["]a-] ≈> V(a,a1,a,2) > {a,2,a,2} ≈ aaaa

De vergelijking van geneste arrays met Conway's pijlen, onder de definitie in §2.6, toont meer detail.
Nu breiden we vier schakels vlug uit naar de hele a..1 pijlketen en dan naar de extensie van Conway's notatie met {a} superpijlen.

  • [a,[1,2]1] = a[,[a,1]a] := [a,[a1,1]1] ≈> V(a,a1,a1,2) ≈> (a,a1,1,3)
  • [a,[2,2]1] = a[,[1,2]a] = a[,[a,1]a,["]a-] ≈> (a,a1,1,3)[,["]a-] ≈> (a,..a1..,1,3) :a: ≈> (a,a1,2,3)
  • [a,[,3]1] = a[,[a,2]1] ≈> (a,a1,a,3)
  • [a,[1,3]1] := [a,[a1,2]1] ≈> (a,a1,1,4)
  • [a,[2,3]1] = a[,[1,3]a] = a[,[a,2]a,["]a-] ≈> (a,a1,1,4)[,["]a-] ≈> (a,a1,2,4)
  • [a,[,,1]1] = a[,[a,a-]1] ≈> V(a,a1,a,a) > {a,2,a,a} ≈ a..a :a1

De tweede index (in een systeem met indexen voor alle tellers) deelt een matrix van twee dimensies in. Dit is het Wielewaal vlak, terwijl Bird of Vogel pas de vierde parameter gebruiken.

Nu opent zich het tweede vlak in de derde dimensie. We maken hier vooruitgang als het groeiend subtotaal a herhaald kan worden verschoven naar de dominante lege teller.
Klik op het dynamische <!--> bord om speciaal die expressies te tonen, die belangrijk zijn in de overgang naar dat recursief opladen van de 2e index in Wielewaal en de 4e teller van Vogel.

  • [a,[1,,1]1] = a[,[,a]a] ≈> V(a,a1,1,1,2)
  • [a,[,1,1]1] = a[,[a,,1]1] ≈> (a,a1,a,1,2)
  • [a,[1,1,1]1] = a[,[a,,1]a] ≈> (a,a1,1,2,2)
  • [a,[,2,1]1] = a[,[a,1,1]1] ≈> (a,a1,a,2,2)
  • [a,[,[2]2]1] = a[,[,a,1]1] ≈> (a,a1,a,a,2)
  • [a,[,[3]1]1] = a[,[,,a]1] = a[,[a,a-,a-]1] ≈> (a,a1,a,a,a) > {a,2,a,a,a}
  • [a,[,[4]1]1] ≈> (a,a1,a,a,a,a)
  • [a,[,[,1]1]1] = [a,[,[a]1]1] ≈> V(a,a1.,a..) :a ≈ a{a}2 <!-->

De dubbele recursie die subexpressies nest lijkt oppermachtig. Maar door onze telraam rij te generaliseren naar Wielewaal dimensies komen we gelijk met de volledige Vogel rij.

Dit is de multidimensionale array van het Bellenblazer systeem uit §2.7, waar we zagen hoe elke dimensie een nieuw type functie recursie toevoegt. Van de dubbele recursie die Knuth's pijlen telt, naar de triple recursie over Conway's pijlketen, en dan per dimensie {n} een superpijl erbij, die de lengte van de voorgaande recursieve rij opblaast.

Ook Bellenblazer heeft arrays die compleet zijn geïndexeerd en substitueert steeds subtotalen. Dezelfde methode van hernieuwd opladen is dominant en bij gelijke expressies zal de output ongeveer gelijk lopen met Wielewaal.
Aanvankelijke verschillen worden almaar insignificanter. Zo ook met onze Beo matrix na B.I en varianten, die tot 0 aftellen, maar verder gelijk blijven, zodat we deze systemen niet verder uit zullen werken.

Daarentegen wordt er in de superradix structuur van Aasblazer in §2.4, en de (alleen qua notatie afwijkende) Aasgier matrix na A.I, een constante opgeladen: de aas a die als radix fungeert.
Met geneste arrays tot a[,[,[,1]1]1] schrijven we dan een getal tot de 10^10^10 in decimalen. Astronomisch groot, maar ordes kleiner dan systemen die bellen blazen of subexpressies nesten.
En toch, bedenk eens hoe weinig van zulke getallen ooit fysiek onder ogen gezien worden…!

X

§3.2 Maxtrix

Een matrix is een multidimensionale ruimte, met op iedere punt positie een getal. Maxtrix betitelt hier een maximale matrix.
Zo vormt een rij tellers de eerste dimensie. Het sterkste algoritme daar is Bird's lineaire array, die we in §3.1 in de Vogel rij omzetten. Het is de substitutie van de hele expressie (dubbele recursie) en het opladen ervan naar afgetelde iteratoren, wat maximaal grote getallen oplevert.

De grootte van die getallen is te vergelijken met de output van ons Wielewaal telraam in meerdere dimensies:
Supermachten op de 1e rij in Wielewaal met de 3e teller bij Vogel. Meerdere rijen in onze 2e dimensie met Vogel's 4e teller, waarmee Bird de rij van Conway's pijlketens benadert. Etcetera…
Dimensie n in Wielewaal met teller n2 op de eerste rij van Vogel.

In dit blog willen we met het vlak en de verdere dimensies in Vogel de multi-dimensionale array van Chris Bird2 evenaren. Deze matrix algoritmes zijn ongeveer maximaal, met getallen op maxtrix level. Significant grotere output is alleen haalbaar uit een hogere structuur.
Om met de primitieve recursie van Wielewaal het maxtrix level te bereiken, zullen we de hyperdimensies in moeten. In die nestruimte leven expressies, waarvan de positie indexen zelf matrixen zijn.

Vogel regels zijn simpel vergeleken met de massieve evaluatie bij Bird. Hij meet vorige structuren exact af (met lengtes b) en vult ze compleet in (met tellers a). Vogel voegt de nodige elementen stap voor stap toe.
Bird's systeem lijkt krachtiger, maar door aan het begin van de meest rechtse rij een enkele teller 1, in te voegen, doen Vogel expressies nooit voor Bird onder, zal nog blijken.

Vogel matrix definitie V.II.

  • V.0. (a) = a
  • V.1. (a,b1) = a(a,b)
  • V.a. ,[1]1 := ,1
  • V.2. ,[n]1) ≡ )
  • V.3. (a,1,R) = a
  • V.4. (a,b1,2R) = (a,(a,b,2R),1R)
  • V.5. (a,b ,[n]1,2 `= (a,a ,[n]b,1
  • V.6. (a,b ,[1n]2 `= (a,a ,[n]b,[1n]1

Als we aannemen dat ,[] ≡ - dan volgt regel V.5. uit regel V.6. na de reductie van ,[1] die enkel komma , is. Woord 1,[0] vervalt en de juist opgeladen b blijft over.
Of stel dat de initiële separator ,[0] tot nul 0 vervalt, dan telt regel V.6. in die gevallen tot 1b op, zodat getallen wat groter worden.

We doen dit nu niet. Het volstaat als Vogel een bruikbare versie van Bird's arrays vormt en beide systemen bewijsbaar gelijk lopen.
Soms keren we in dat bewijs met := de evaluatie richting om. Klik op de gescripte borden 0'>!< om meer detail te tonen of toets Ctrl-U en bekijk deze verborgen items in de pagina bron.

  • V(a,b,[2]2) = (a,a,b,[2]1) = (a,a,b) := (a,b,1,2) = {a,a,b-1}
  • (a,b.,1..,[2]2) :n = (a,a,.,1..,b) :n := (a,b,.,1..,2) :n1 > {a+b,n+2[2]2}
  • (a,b1,2,[2]2) = (a,(a,b,2,[2]2),1,[2]2) == (a,..a..,1,[2]2) :b: := (a,..a..,1,1,2) :b: := (a,b1,2,1,2)
  • (a,b1,3,[2]2) == (a,..a..,2,[2]2) :b: := (a,..a..,2,1,2) :b: := (a,b1,3,1,2)
  • (a,b1,c1,[2]2) == (a,..a..,c,[2]2) :b: := (a,b1,c1,1,2) > {a,b,c,1,2}
  • (a,b1,2,1,[2]2) == (a,..a..,1,1,[2]2) :b: == (a,a,1,1,..a..) :b: := (a,b1,2,1,1,2)
  • (a,b1,3,1,[2]2) == (a,..a..,2,1,[2]2) :b: := (a,b1,3,1,1,2)
  • (a,b,1,2,[2]2) = (a,a,b,1,[2]2) := (a,a,b,1,1,2) := (a,b,1,2,1,2)
  • (a,b,c,2,[2]2) := (a,b,c,2,1,2)
  • (a,b,c,d,[2]2) := (a,b,c,d,1,2)
  • V(a.,pi..,[2]2) :n>0 := (a,.,pi..,1,2) :n > {a,n+2[2]2} {pa} 0'>!<

Noteren we in Vogel ,[2]2 na de eerste rij, dan werkt dat hetzelfde uit als wanneer er ,1,2 stond om later met regel V.5. een b naar op te laden. De tweede rij index wordt immers pas afgeteld, als de eerste rij is gereduceerd tot dezelfde b met de ,1.. enen nog op hun plek. Regel V.6. voegt dan die teller b toe aan het eind.

  • V(a,b,[2]3) = (a,a,b,[2]2) = (a,a,b,1,2) = (a,b,1,2,2)
  • V(a,b.,1..,[2]3) :n0 = (a,a,.,1..,b,[2]2) :n := (a,a,.,1..,b,1,2) :n := (a,b,.,1..,2,2) :n1 > {a+b,n+4[2]2}
  • (a,b1,2,[2]3) == (a,..a..,1,[2]3) :b: := (a,a,1,..a..,1,2) :b: := (a,b1,2,1,2,2) > {a,b,1,1,2,2}
  • (a,b1,3,[2]3) == (a,..a..,2,[2]3) :b: := (a,b1,3,1,2,2)
  • (a,b1,c1,[2]3) == (a,..a..,c,[2]3) :b: := (a,b1,c1,1,2,2) > {a,b,c,1,2,2}
  • (a,b1,2,1,[2]3) == (a,..a..,1,1,[2]3) :b: := (a,a,1,1,..a..,1,2) :b: := (a,b1,2,1,1,2,2)
  • (a,b,c,d,[2]3) := (a,b,c,d,1,2,2)
  • (a,b.,1..,[2]4) :n0 = (a,a,.,1..,b,[2]3) :n := (a,b,.,1..,2,2,2) :n1
  • (a,b1,2,[2]4) == (a,..a..,1,[2]4) :b: := (a,..a..,1,1,2,2,2) :b: := (a,b1,2,1,2,2,2)
  • (a,b,c,[2]4) := (a,b,c,1,2,2,2)
  • (a,b.,1..,[2]q1) :n0 = (a,a,.,1..,b,[2]q) :n := (a,b,.,1..,2..) :n1 :q
  • V(a.,pi..,[2]q1) :n>0 := (a,.,pi..,1.,2..) :n :q > {a,n+q+1[2]2} {pa} 0'>!<

Voorbij de eerste rij in Vogel verlengt de teller van ,[2]q1 die rij met q1 kleine tellers (of na opladen q grote tellers). Die lineaire aanwas volgt uit regel V.6. en het terughoudend met V.2. opruimen.
Bij Bird speelt bel b de rol van het opblazen van de lineaire array onder element [2]2 en dat is een enkele hogere tel.

Vogel staat op dit punt dus bijna een teller achter. Hierna zal opladen met regel V.5. de oude rij lengte n1 en de hele expressie domineren.
Op de tweede rij geeft onze tweede teller een benadering voor Bird's eerste. Verder moet Vogel's achterstand beperkt blijven tot 1 teller, omdat na verlenging de dominante regels dezelfde zijn.

  • V(a,b,[2]1,2) = (a,a,[2]b) = (a,a,1.,2..) :b-
  • V(a,b1.,1..,[2]1,2) :n0 = (a,a,.,1..,[2]b1) :n := (a,a,.,1..,2..) :n1 :b ≈> (a,a,[2]bn) > {a,b+n+1[2]2}
  • (a,b1,2,[2]1,2) == (a,..a..,1,[2]1,2) :b: ≈> (a,a,[2]..a..) :b: > {a,b+1,2[2]2}
  • (a,b,c,[2]1,2) > {a,b,c[2]2}
  • (a,b1,[2]3,2) = (a,a,b1,[2]2,2) == (a,..1..,b,[2]2,2) :a: %= (a,a,1,[2]b%)
  • (a,b,[2]1,3) = (a,a,[2]b,2) ≈> (a.,2..,[2]1,2) :b > {a,b[2]3}
  • V(a,b,[2]1,q) > {a,b[2]q} 0'>!<

Voor aankomst bij regel V.6. zijn expressies in de evaluatie trein %= uitgewerkt tot een serie elementen ,[n]1 met vele kleinere afgetelde elementen ertussen. Uitgaande van een hogere teller 2p zal die serie :p elementen tellen. De bel ,[n]b% die daarop volgt, overtreft de eerdere b. Toch is dit insignificant, minder dan 1 tel extra lengte.

  • (a,b,[1n]2p,R) %= (a,a,Sj=0.,[n]1,Sj.. ,[n]b%,[1n]1,R) :p Sj = ,[mi,j]1.. {mi,j<n}
  • < (a,a.,[n]1.. ,[n]b,[1n]1,R) :p1

Stel dat teller p2=b juist ervoor werd opgeladen. Laatste bel b% zal door regel V.4. ... ...
... ... meteen over een serie ,[n]1.. naar rechts schuift. die weer 1 wordt. De hoge ,[n]a tellen we af tot 1, zodat de nieuwe dimensie n een lengte van b ruimtes overhoudt. Dezelfde verdeling als bij Bird. Maar ondergeschikte lengtes worden gevormd met bel a en zijn kleiner dan bij Bird.
Dus is b1 opladen naar de eerst hogere positie afdoende om Bird te overtreffen in dit kleinere Vogel algoritme. Maar de werkelijke Vogel bel b% komt tot stand via vele subexpressies, die zelf de verste teller bevatten, en is veel groter. Alle lagere lengtes van Bird worden ruim overtroffen.
Dat kost ons wel de eerste teller p, want Bird telt lengtes met b. Maar als we eenmaal opladen naar de eerste teller, is Vogel duidelijk groter. We geven de teller die rechts volgt op p gewoon 1 extra.

Regel V.6. vult de vorige dimensie n1 element na element aan, tot lengte p2 door de evaluatie trein wordt bereikt. Maar dat werkt alleen als regel V.2. de afgetelde ,[n]1 elementen op hun plek laat staan.
Omdat we geen elementen tussentijds opruimen, groeit het aantal indexen mi,j<n in kleinere dimensies, en zijn die lengtes niet meer praktisch te bepalen. Toch blijven deze cumulatieve lengtes slechts insignificant groter, omdat de laatst opgeladen bel b domineert.

Zo vallen alle problemen weg met de implementatie van regel V.2. voor afgetelde elementen bij Bird. Dit wordt lastiger, wanneer hij er de grootte van complexe index arrays voor moet vergelijken.

We moeten dus tonen dat b% significant kleiner is dan het effect op b van een tel van p op dit punt bij Bird. Zodat zo'n stap groter is dan b opladen naar p in Vogel maar kleiner dan b% opladen.
Ook zullen we bewijzen, dat de lengtes van kleinere dimensies nooit groter worden dan bij een extra tel van p in Vogel het geval zou zijn, zonder dat het cumulatieve effect mee zou spelen.
Als dit uit de eerste vergelijkingen hieronder blijkt, dan zal dat voor latere expressies ook moeten gelden.


Bird's Universum

Deze systemen zijn gelijk aan die van Chris Bird, maar we hebben de array notatie uniform versimpeld, met unaire variabelen. De definities krijgen de letter U van Uil en een eigen Romeins nummer.

Machten zijn de opmaat voor de supermacht functie U.O, uitgedrukt met drie tellers (getal, iterator en supers) op Bird's array rij.

  • 0.0. {a} = a
  • 0.1. {a,b1} = a^b1 = {a,b}.. :a
  • 0.2. {X,1} = {X}
  • 0.3. {a,1,c} = a
  • 0.4. {a,b1,c1} = {a,{a,b,c1},c}

Bird's lineaire array functie U.I voor de hele eerste rij.

  • 1.0. 1.1. 1.2.
  • 1.3. {a,1,Z} = a
  • 1.4. {a,b.,1..Z} :k>0 = {.a,..$,Z} :k

Omdat alle variabelen v>0 gevuld moeten blijven, leidt evaluatie volgens de Uil regels tot eenzelfde unieke uitkomst.
Subexpressie $ staat voor de linker expressie `$ waarin iterator b>1 met 1 is verminderd. De komma , is de separator tussen tellers.

  • 1.a. `$ = {a,1Z} => $ = {a,Z}
  • 2.b. , ≡ [1]

Bird laat zijn {a[n]Z} expressies ongebruikt (hij reduceert ze tot a). Bij ons vervangt een stel van zulke arrays Bird's punthaak ketens. Deze secondaire regels vullen array ruimtes stapsgewijs of in serie.

  • 2.c. {a[2]m1} ≡ {a[2]m},a ≡ a,..a :m
  • 2.d. {a[n1]b} ≡ {a[n]b,b} ≡ €n..1 :b
  • 2.e. €n ≡ {a[n]b}[n]
  • 2.f. {a[n]1,b} ≡ {a[n]b}
  • 2.g. {a[n]m1,b} ≡ {a[n]m,b}[n]{a[n]b}

Bird's multi-dimensionale array functie U.II.

  • 2.0. 2.1. 2.4.
  • 2.2a. [m]1} ≡ } 2.2b. [m]1[n][n] {m<n}
  • 2.3. {a,1[n]Z} = a
  • 2.5. {a,b.[ni]1..Z} :m>0 = {.€ni..Z} :m
  • 2.6. {a,b.[ni]1..,1..Z} :m>0 :k1 = {.€ni..a,..$,Z} :m :k0

Pas de regels in volgorde toe, dan is ni>ni+1>1 verzekerd in de laatste regels.

0. Een systeem voor snel groeiende recursieve functies, dat de functies van Jonathan Bowers en anderen ver te boven gaat, in Christopher M. Bird Super Huge Numbers, een serie van 9 PDFs over Bird's arrays + 3 bijlagen, 2017.
1. Chris Bird, Linear Array Notation, 2012.
2. Chris Bird, Multi-Dimensional Array Notation, 2012.
3. Chris Bird, Hyper-Dimensional Array Notation, 2017.
4. Chris Bird, Nested Array Notation, 2012.

Bouwwerken van de Lilliputters die Gulliver zijn maaltijd serveren
CALL pC.App.show( UL, className[] )
SET tC.App.Tags

Blogboek  index

  1. Tellen
  2. Rijen
  3. Diepen
    1. V supertrio = W rij
    2. V toprij = W matrix
    3. V maxtrix = W hyper

© 2018
Giga Gerard