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 niveau's met diepen in de eerdere array 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 dit Vogel systeem gelijk op gaat met Bird, en ons Wielewaal telraam te vergelijken is met Vogels, kunnen we uiteindelijk een elegant wereldrecord getal voorbij zien vliegen.
Al zulke arrays geven als uitkomst reusachtig grote getallen. Zo groot, dat de complete evaluatie van expressies alleen in theorie, maar in de praktijk 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 functie van Wielewaal is kopiëren en optellen. Tel een kopie op en het getal a verdubbelt tot aa. Herhaal dit c keer en het totaal a*2^c groeit exponentieel.
Na deze machtige start noteren de tellers rechts nog hogere recursie of vormen van herhaling. En we schuiven de kopie van subtotalen a' door naar rechts om de lege tellers in dit telraam 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, aan de basis.
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.

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.


We zullen Vogel en Bird nu vergelijken binnen een nieuw systeem, vernoemd naar de toverachtige trekvogel uit een zomerse canon.
In ons Wielewaal telraam dupliceren we getallen en verschuiven ze. Aanvankelijk over een serie parameters of tellers. De lengte van die eerste rij geeft de superexponent ^{r} van de uitkomst ervan. Zo drukken we dezelfde functies en getallen als in de vorige sectie uit.

Ons telraam begint wat langzamer, omdat de herschrijf methode voor rijen zo eenvoudig is. Hogerop voorzien we posities van een kopie (minus 1) van de volgende index array. Dat is even sterk als het nesten van subexpressies (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.

De 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
  • a[,,1] = a[,a] = a*2^a > V(2,a,2)
  • a[b,c,1] = ab*2^c[,,1] ≈> 2^c[,ab*2^c] ≈> 2^(ab*2^c) > V(2,abc,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)) ≈> ab^ab^2^c > V(abc,2,3)
  • a[b,c,d] ≈> ab*2^(..c..) :d: ≈> ab^^d\^2^c > V(abc,d,3)
  • a[,,,1] = a[,,a] = a*2^a[,,a-] ≈> aa^^a > V(a,2,4)
  • a[b,c,d,1] ≈> abc^^d[,,,1] ≈> abc^^abc^^d ≈> 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^^..d :e1 ≈> bc^^^e1\^^d ≈> V(bcd,e1,4)
  • [b,c,d,e,f] ≈> bcd^^^^f1\^^^e ≈> V(bcde,f1,5)
  • [a,{r1}1] = a[,{r}a] ≈> a^{r}a1 ≈> V(a,2,r2)
  • [.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) :k1 = (a,a,.1,..b,R) :k0

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) :k ≈> {a,b.,1..,p} :k1 <!-->

Voor uitwerking van de voorbeelden, klik het <!--> bord. Dan blijkt dat de eerste rij in Vogel met de aanpassingen a+1 en c+1 een verrassend goede benadering geeft van Bird over zijn eerste rij.

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

Deze Vogel toprij versie van Bird's lineaire array gebruiken we in de vergelijking met ons eigen telraam, dat werkt zonder substitutie van expressies, in de volgende sectie.


Weliswaar startte in §3.0 onze Wielewaal rij sterk met verdubbeling, daarna viel de functie snelheid terug. Over de hele rij drukken we de supermachten uit. We zullen meerdere dimensies moeten gebruiken om dezelfde grote getallen te noteren als Chris Bird0 doet in zijn eerste dimensie: de lineaire array.

We positioneren alle tellers met behulp van indexen en itereren daar over in een geneste array. De complete superradix indexering pakt natuurlijker uit dan Bird's repeterende array ruimtes, hoewel onze arrays twee keer zo diep genest moeten worden, zie box 2.6.
Afgetelde iteraties herladen we 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[1T] = a1[T]
  • 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 terug := te vertalen. 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 we onze 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. Die vergelijkingen werken we hieronder precies uit.
Klik op de dynamische <!--> borden om expressies te tonen met meerdere variabelen.

  • [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}a = V(a,a1,1,2)
  • [a,[2,1]1] = a[,[1,1]a] = a[,[a]a,["]a-] ≈> (a,a1,1,2)[,["]a-] ≈> (a,..a1..,1,2) :a: ≈> V(a,a1,2,2)
  • [a,[3,1]1] = a[,[2,1]a] = a[,[']a,["]a-] ≈> (a,a1,2,2)[,["]a-] ≈> V(a,a1,3,2)
  • [a,[,2]1] = a[,[a-,1]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.
De vier schakels breiden al snel uit naar de hele a..1 pijlketen en dan naar de extensie van Conway's notatie met {a} superpijlen.
We maken grote vooruitgang omdat het groeiend subtotaal herhaald wordt gesubstitueerd in de dominante lengte teller. Dit is de eerste index recursie over rijen tellers.

  • [a,[1,2]1] = a[,[a,1]a] ≈> (a,a1,a1,2) ≈> V(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: ≈> V(a,a1,2,3)
  • [a,[,3]1] = a[,[a,2]1] ≈> V(a,a1,a,3)
  • [a,[1,3]1] = a[,[a,2]a] := [a,[a1,2]1] ≈> V(a,a1,1,4)
  • [a,[2,3]1] = a[,[1,3]a] = a[,[a,2]a,["]a-] ≈> (a,a1,1,4)[,["]a-] ≈> V(a,a1,2,4)
  • [a,[,,1]1] = a[,[,a]1] ≈> V(a,a1,a,a) > {a,2,a,a} ≈ a..a :a1 <!-->

In ons systeem met indexen voor alle teller posities deelt de 2e index een matrix van twee dimensies in: het Wielewaal vlak. Terwijl Bird of Vogel pas de 4e parameter in de rij gebruiken.

Nu opent zich het tweede vlak in de derde dimensie. De overgang naar nieuwe recursies vraagt wat extra aandacht, maar de evaluatie van de rest van de index array zal voorspelbaar te verlopen.
We tonen de vergelijkingen tot de 3e index en de 5e parameter in Vogel wat uitgebreider. Deze Wielewaal kubus wijst ons de weg.

  • [a,[1,,1]1] = a[,[,a]a] ≈> (a,a1,a1,a) ≈> V(a,a1,1,1,2)
  • [a,[,1,1]1] = a[,[a,,1]1] ≈> V(a,a1,a,1,2)
  • [a,[1,1,1]1] = a[,[a,,1]a] ≈> V(a,a1,1,2,2)
  • [a,[,2,1]1] = a[,[a,1,1]1] ≈> V(a,a1,a,2,2)
  • [a,[,[2]2]1] = a[,[,a,1]1] ≈> (a,a1,a,a,2) ≈> V(a,a1,1,1,3)
  • [a,[,[3]1]1] = a[,[,,a]1] = a[,[a,a-,a-]1] ≈> V(a,a1,a,a,a) > {a,2,a,a,a}
  • [a,[,[4]1]1] ≈> (a,a1,a,a,a,a) ≈> V(a,2,2,1,1,1,2)
  • [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 deze gelijk met de hele 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 {k} 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 d in Wielewaal met teller d2 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,X) = a
  • V.4. (a,b1,2X) = (a,(a,b,2X),1X)
  • 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.
Vaak keren we in dat bewijs met := de evaluatie richting om.
Klik op de gescripte borden 0'>!< om meer detail te tonen of zoek de verborgen items op 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) :k = (a,a,.,1..,b) :k := (a,b,.,1..,2) :k1 > {a+b,k+2[2]2}
  • (a,2,2,[2]2) = (a,a,1,[2]2) = (a,a,1,a) = (a,a,a,a-)
  • (a,3,2,[2]2) = (a,(a,2,2,[2]2),1,[2]2) = (a,a,a,(a,a,a,a-)-)
  • (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-1,b+1,1,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,b,1,2,1,2) > {a+b,5[2]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)
  • (a.,pi..,[2]2) :k>0 := (a,.,pi..,1,2) :k > {a,k+2[2]2} {pa} 0'>!<

Noteren we in Vogel ,[2]2 na de eerste rij, dan is dat hetzelfde als wanneer er ,1,2 stond om met regel V.5. de bel ,b te substitueren. De tweede rij wordt immers pas afgeteld, als de eerste rij is gereduceerd tot a,b met verdere posities ,1.. resterend als enen. Regel V.6. voegt het subtotaal b dan toe aan het eind.

Ook werkt lengte teller ,[2]1m over de eerste rij precies zo uit, alsof er een serie tellers ,1.,2.. :m aan die rij zit vast geplakt.

  • (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) :k0 := (a,a,.,1..,b,1,2) :k := (a,b,.,1..,2,2) :k1 > {a+b,k+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-1,b+1,1,1,2,2}
  • (a,b1,3,[2]3) == (a,..a..,2,[2]3) :b: := (a,..a..,2,1,2,2) :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)
  • (a1,b,1P,[2]3) := (a1,b,1P,1,2,2) ≈> {a,b,P,1,2,2}
  • (a,b.,1..,[2]4) :k0 = (a,a,.,1..,b,[2]3) :k := (a,b,.,1..,2,2,2) :k1
  • (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.,pi..,[2]4) :k0 := (a,b,P,1,2,2,2) > {a+b,k+5[2]2}
  • (a,b,[2]2m) = (a,a,b,[2]1m) := (a,a,b,1.,2..) :m := (a,b,1.,2..) :m1
  • (a,b.,1..,[2]1m) :k0 = (a,a,.,1..,b,[2]m) :k := (a,b,.,1..,2..) :k1 :m > {a+b,k+m+2[2]2}
  • (a,b.,pi..,[2]1m) :k0 := (a,b,P,1.,2..) :m > {a+b,k+m+2[2]2} 0'>!<

Evaluatie van element ,[2]1m voegt aan de eerste rij een aantal van :m nieuwe tellers toe, gevuld met grote getallen.
Woord ,P staat hier voor een deel van een rij en R voor een hele rij. Merk op dat de waarde van (fysiek eindige) parameters pi1 in P te verwaarlozen is ten opzichte van de rij lengte zelf.

Bij Bird speelt bel b de rol van het opblazen van de lineaire array. Van element [2]2 kost dat slechts een enkele hogere tel. Vogel V loopt op dit schakelpunt tussen dimensies dus vrijwel een teller achter.

  • V(a,b,[2]1,2) = (a,a,[2]b) := (a,a,1.,2..) :b- := (a.,2..) :b1 > {a,b+1[2]2}
  • (a,b1,2,[2]1,2) == (a,..a..,1,[2]1,2) :b: == (a,a,1,[2]..a..) :b: ≈> {a+2,b+1,2[2]2}
  • (a,b1,3,[2]1,2) == (a,..a..,2,[2]1,2) :b: ≈> {a,b+1,3[2]2}
  • (a,b,c,[2]1,2) ≈> {a,b,c[2]2}
  • (R,[2]1,2) ≈> {R[2]2}
  • (a,b1,2,[2]2,2) == (a,..a..,1,[2]2,2) :b: = (a,a,1,..a..,[2]1,2) :b: ≈> {a-1,b+1,1,1,2[2]2}
  • (a1,b,c1,[2]2,2) ≈> {a,b,c,1,2[2]2}
  • (a1,b,1P,[2]2,2) ≈> {a,b,P,1,2[2]2}
  • (a,b1,2,[2]3,2) == (a,a,1,..a..,[2]2,2) :b: ≈> {a-1,b+1,1,1,2[2]2}
  • (a1,b,c1,d,[2]3,2) ≈> {a,b,c,d,1,2,2[2]2}
  • (a1,b,1P,[2]3,2) ≈> {a,b,P,1,2,2[2]2}
  • (a1,b,1P,[2]1m,2) ≈> {a,b,P,1.,2..[2]2} :m
  • (a,b1,[2]1,3) = (a,a,a,[2]b,2) > {a,b+2[2]3}
  • (a,b,c,[2]1,3) ≈> {a,b,c[2]3}
  • (a1,b,c1,[2]2,3) ≈> {a,b,c,1,2[2]3}
  • (R,[2]1,n) ≈> {R[2]n}
  • (a,b,1.pi..[2]m,n) :k > {a+b,k+m+1[2]n+1} 0'>!<

Met matrixregel V.6. bouwen we lengtes van tellers stapsgewijs op. In Vogel blijven de lege elementen ,1 staan, omdat opruimregel V.2. de afgetelde posities tussenin niet verwijdert.
Op de tweede rij zal oplaadregel V.5. de groei van de eerste rij met een serie lengte tellers mj.. :n recursief domineren door het opladen van de volgende grote bel. Dit valt nog te bewijzen:

Optellen van de vele mj<n valt in het niet bij de grote laatste mn in de evaluatie trein van deze lengte teller. Breng de 1e rij dan terug tot bel bn1 met rechts een reeks lege elementen ,1.. van lengte :mn (dus ongeveer). Laadt deze bel op als de volgende n' teller op de 2e rij. Evaluatie daarvan vaagt de vroegere lengtes volledig weg.

  • V(a,b1,2,[2]1,1,2) = (a,a,1,[2]1,..a..) :b: ≈> {a,b+1[2]1,2}
  • (a,b1,2,[2]1,2,2) = (a,a,1,[2]..a..,1,2) :b: ≈> {a+2,b+1[2]2,2}
  • (a1,b,1P,[2]1,q0.,qi..) :n > {a,b,P[2]q0.,qi..} :n
  • (X,[n]m,Q) > {X[n]Q} 0'>!<

De accumulatie van posities in Vogel blijft in alle dimensies zonder gevolgen. Steeds omdat de rechts te laden bel b alle links liggende lengtes domineert. Dat werkt zo in het kleinste geval op de tweede Vogel rij en zal nog sterker gelden voor latere dimensies.
Vogel's stapsgewijs groeiende ruimtes mogen dan gekunsteld zijn of onnatuurlijk, in Bird's systeem kan het nog lastig worden om geneste index arrays [X]1[Y] te vergelijken voor de regel die eindposities tussenin opruimt (en daarmee lengtes aftelt).

Op de schaal van dimensies [n] verschillen de matrix expressies van Vogel en Bird vanzelf niet bijster veel.
Aan het begin van elke volgende rij of dimensie geeft Vogel's tweede teller een benadering voor Bird's eerste teller. Vogel's achterstand blijft zodoende beperkt tot een extra teller aan het begin van de hoogste rij. Voeg een lengte teller m=1 in voor de beste benadering, of m=2 en de hele Vogel array pakt zeker groter uit.
Dat verschil geldt in principe voor iedere rij in Vogel expressies, maar verschillen in eerdere dimensies X strepen makkelijk weg tegen de verlengde rij uiterst rechts.

Na het openen van de rij is Vogel's regel V.5. voor opladen dominant. Die komt praktisch overeen met Bird's multi-dimensionale regel 2.6. en daarom stellen we hun laatste rij deel Q hier gelijk.
Zo nodig compenseren we Bird's opladen van subexpressies $ door bij de derde teller c in Vogel 1 op te tellen. Andere direkte substituties van Bird, zoals zijn tellers a eerder in de rij en zijn volle ketens €n in voorliggende dimensies zijn nog minder significant.
Ga maar na, hoe de later opgeladen bellen b' links in de Vogel array steeds groter worden. Want door regel V.4. bevatten die getallen de rechts geladen bel. Zo groeit elke lengte eerst met a en ten tweede tot een getal groter dan Bird's lengte b, en dat kost Vogel maar 2 tellen.


Met de regels voor geneste arrays in W.II werken we Wielewaal expressies nu uit tot het 3e array niveau.
Binnen het 1e niveau van de [top array] iteraties, tellen we de posities en hun iteraties op het 2e niveau [index array]. Op dezelfde wijze ligt hier een 3e niveau [index rij] onder, zelf gescheiden door een reeks komma's , of een 4e niveau [index].

Klik op de <!--> borden voor expressies met meerdere variabelen. Daarin geeft het teken ~ de gebruikelijke benadering.

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

Om wat slagvaardiger te werk te gaan laten we de ≈> ordeningen (minimaal groter dan, in de gegeven array vorm) verder maar achterwege. Hogere structuren worden zo dominant, dat het precies passend maken van deze vergelijkingen vanaf de laagste niveau's er weinig toe doet. De uitkomsten van het Wielewaal [W] telraam vallen ongeveer samen (iets groter of kleiner) met de Vogel V(X) matrix functie en zo met Bird's {Y} multi-dimensionale arrays.

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

Wezenlijk is het algoritme van Wielewaal even sterk als dat van Vogel en Bird, het is alleen de structuur die anders is.
Alle teller posities in Wielewaal krijgen per definitie een lengte index (behalve optioneel in de binnenste array, waar we herhaalde komma's inlassen voor de leesbaarheid). Waar Vogel separatoren herhaalt binnen hun array dimensie, zodat we lengte zien, correspondeert dit aantal in Wielewaal met een geneste index.

Supermachten bereikten we over de lengte van de Wielewaal rij, die Bird's recursies van subexpressies in b vervangt. En subexpressie substituties naar rechts bij Bird zijn gelijk aan het opladen van bel b onder een grotere c1 in Vogel. Dit vertaald naar Wielewaal vraagt om een extra teller op de eerste rij.
De rest van de elementen in Bird's lineaire array corresponderen met de indexen van het 2e niveau in Wielewaal, die met de rij lengte teller begint. Naar al deze geneste tellers laden we bel b immers ook op. En de oplaadregel is maximaal en dus dominant in beide systemen. Dit vormde de Wielewaal matrix waarmee we de Vogel toprij uitdrukten.

Nu blijkt dat elke teller op het 3e niveau in Wielewaal correspondeert met een lengte van een dimensie bij Bird of Vogel. Rij lengte met de teller zonder index, vlakken met de teller met positie index 1, derde dimensies met de teller met index 2, enzovoort.
In het algemeen kan de lengte r van een Vogel dimensie met een teller r op het 3e array niveau in Wielewaal weer worden geven.

  • [a,[,[q.,[si]ri..]p]1] :t ≈ V(a,a.,[si1]1.. :ri ,1..p) :q ⋮t

Waarbij de diepste index si>si+1 van groot naar klein afloopt. We schrijven de reeks elementen ,[si+1]1.. in Vogel hier van boven naar onder. Elke reeks bestaat uit gelijke separatoren, hun index i die in de horizontale rep :ri terugkeert, betreft de verticale herhaling.
De witruimte rond alle reps en variabelen moeten onze beschrijving van deze systemen leesbaar maken. Input expressies zijn in feite strings van units 1, separator tekens en haakjes.

De Vogel dimensies s1 zelf kunnen we zien we door de komma's te tellen in Wielewaal op het 3e niveau, als dat de binnenste array is. Of hier lezen we deze af uit de positie index s op het 4e niveau.
Verdere tellers in Wielewaal vormen nog grotere getallen, zoals Bird die noteert met zijn hyper-dimensies, in het volgende blog.

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]
  • 2.c. €n ≡ {a[n]b}[n]

Onze afkortingen €n functioneren vanaf €2 hetzelfde als punthaken bij Bird, die elke array dimensie n vult met een serie van b kleinere ruimtes, totdat parameters a bereikt zijn in rijen (waar n=1).

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.

Bird laat zijn belloze arrays {a[n]Z} ongebruikt (reduceert ze tot a). Wij gebruiken een stel van zulke arrays om Bird's punthaak ketens te vervangen en zo zijn array ruimtes stapsgewijs te vullen.

  • 2c.1. {a[2]p1} ≡ {a[2]p},a ≡ a,..a :p
  • 2c.2. {a[n1]b} ≡ {a[n]b,b} ≡ €n..1 :b
  • 2c.3. {a[n]1,b} ≡ {a[n]b}
  • 2c.4. {a[n]p1,b} ≡ {a[n]p,b}[n]{a[n]b}

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
    4. V hypers = W nest 4

© 2018
Giga Gerard