Friday, 18 May 2018

Toprij

Link naar dit blog:
allergrootste.blogspot.nl/2018/05/toprij.html
edit jan.2019.

§3.1 Toprij

In dit blog vergelijken we ons Vogel algoritme met de lineaire array van Chris Bird.1 In dezelfde rij structuur loopt Vogel volledig parallel aan Bird en produceert maximale (bij benadering grootst mogelijke) getallen. Daarom heet dit de toprij.
Bird's systeem is tamelijk uitgebreid, maar we hebben het in appendix U enigszins versimpeld. Ons Uil systeem voor de lineaire array U.I voegt twee van Bird's dominante regels samen. Exact dezelfde input expressies en output getallen blijven geldig.

We vergelijken Bird via systemen U en dan V met W. Het vorige blog §3.0 behandelde drie parameters: het supertrio van U.O > V.O met de supermachten a^{c}b versus a*{c}b, waar in W.I ondanks de snelle opstart een hele rij voor nodig was.
Bird als Uil substitueert $ subexpressies ook in hogere tellers op zijn array rijen. Dat is overbodig, we zullen in ons Vogel telraam deze expressie met 1 stap minder $ alleen nog in bel b nesten.

Vogel rij definitie V.I.

  • V.0. (a) = a
  • V.1. (a,1b) = a(a,b)
  • V.2. (R,1) = (R)
  • V.3. (a,1,R) = a
  • V.4. (a,1b,1R) = (a,(a,b,1R),R)
  • V.5. (a,b.,1..R) :k2 = (a,a.,1..b,R) :k1 == (a,a,1.a,..b,R) :k

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

De Vogel toprij volgt Bird's lineaire array, alleen Vogel's super teller c loopt consequent - achter.

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

Door bij superexponent c een 1 op te tellen, ondervangen we in Vogel zowel de begin * versus ^ achterstand, als de functie substitutie rechts bij Bird. Zodoende nest regel V.4. in b een extra subexpressie, die regel V.5. oplaadt. En komen we gelijk op de rij.

  • V(a,b,2,3) = {a,b,1,3}
  • (a,2,c1,3) = (a,a,c,3) = {a,2,c,3}
  • V(a,b,c1,d) = {a,b,c,d}
  • (a,2,2,1,2) = (a,a,a1,a) = {a,2,1,1,2}
  • (a,b,c1,1,2) = {a,b,c,1,2}
  • (a,2,2,1,1,2) = (a,a,a1,a,a) = {a,a,a,a,a}
  • (a,2,2.,1..1) :k = {a,2.,1..1} :k+1 <!-->

Om voorbeelden uit te werken, klik op de <!--> borden. Blijkt dat expressies in Vogel met de aanpassing c+1 steeds exact gelijk zijn aan die van Bird over de eerste rij.

  • V(a,b,1R) = {a,b,R}

Uitwerking == van regel V.5. geeft derde teller c er 1 bij, zodat rechts opladen van b1 in Vogel de functie substitutie van Bird daar vervangt. Dit bewijst dat beide lineaire arrays gelijk op gaan.


Nu Bird's lineaire array naar de Vogel toprij is omgezet, vergelijken we deze met ons Wielewaal systeem.
Weliswaar startte Wiel in §3.0 sterk met verdubbeling in bel a, maar daarna viel de functie snelheid terug. Zonder expressie $ nesten kost het een hele rij om supermachten uit te drukken.
Hierna zal onze a tellerij meerdere dimensies gebruiken, om even grote getallen te maken als een telraam met $ in zijn rij dimensie.

We positioneren tellers met behulp van indexen en itereren daarover in geneste arrays. Onze superradix indexering pakt natuurlijker uit dan Bird's herhaalde separatoren, hoewel onze structuur twee keer zo diep genest zal zijn, zie box 2.6.
Afgetelde iteraties herladen we met een kopie van bel a, maar anders dan in Bellenblazer blijft onze verdubbel bel op zijn plaats staan. Zo garanderen we, dat het getal a bij substitutie maximaal blijft. Dit is niet triviaal, gezien de bewerkelijke cascade van het herladen van Bellenblazer's index arrays.

De Buizerd varianten op bellenblazer, die we in box 3.0 zagen, zijn slechts insignificant trager dan Wielewaal. Met Buizerd schrijven we net als het Vogel trio *{c} supermachten.
De exacte supermacht getallen noemen we natuurlijk. In die zin is Wiel met verdubbelen al vanaf het begin onnatuurlijk, hoewel de functie definitie daardoor makkelijker is.

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

Definitie Wielewaal nest functie W.II.

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

Bij regel W.3. staat variabele a voor het actuele subtotaal. Dit wordt binnen de array [a,R] verzameld, of erbuiten a[,R] als hulpregel W.a. voorrang krijgt.

Hulpregels W.ii voor geneste arrays in Wielewaal.

  • W.a. a[1T] = a1[T]
  • W.b. [,{n}1 := [,[n]1
  • W.c. ,[m]p1,{n}1 := ,[m]p1,[mn]1

Zo kunnen we de eerste rij van een subarray met gewone komma's vertalen := naar complete indexering.
Voeg aan het begin van array [p,T] met hulpregel W.b. of door omkering =: van regel W.2. een lege sep [,[]p,T] in. Dan kan hulpregel W.c. de komma bereiken [,[]p,[1]T] en neemt regel W.2. de eerste stap terug voor het beoogde [p,[1]T] resultaat.

Uiteindelijk willen we onze arrays vergelijken met de geneste arrays van Bird4. Met de Wielewaal rij van W.I benaderden we drie Vogel tellers, dus eerst moeten we de toprij van Vogel V.I nog inhalen.

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

Klik op de dynamische <!--> borden om expressies te tonen met meerdere variabelen.
We kunnen naar een gegeven array (of expressie) verwijzen met een dubbele quote ["] of voor de variatie ['] met een enkele quote. En tellen ze links [-"] of soms rechts ["-] af.

De vergelijking van geneste arrays met Conway's pijlen in §2.6 toont meer detail. Onder breiden we de vier schakels van Conway's notatie uit naar de hele a..1 pijlketen en later naar onze extensie {a} met superpijlen.

Wielewaal maakt voortgang door subtotaal a herhaald te substitueren in de dominante lengte teller. Dit is recursie over de eerste index van een rij parameters, wat die rij lengte expandeert.

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

Opent het tweede vlak in de derde dimensie. Overgang naar nieuwe recursies vraagt altijd extra aandacht, maar evaluatie van de verdere index array in Wiel zal voorspelbaar verlopen.
Klik het bord om vergelijkingen te tonen tot de 3e index in Wiel en de 5e parameter in Vogel. Aan de hand van vlak en nu dan Wielewaal kubus wordt de generalisatie tot matrix dimensies duidelijk.

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

Per Wielewaal dimensie [n] komt er een superpijl bij, die de lengte van de voorgaande {n} opblaast. Zie de Bellenblazer matrix van §2.7 waar elke dimensie een nieuwe recursieve functie toevoegt. Van de dubbele recursie van Knuth's pijlen, over Conway's pijlketen, naar de verschillende superpijl recursies.

De tellers op de Vogel rij vinden stuk voor stuk hun gelijke in de indexen van Wielewaal dimensies op het tweede array niveau.

  • [a,[c.,[i]di..]b] :n := a[,[c.,di..]b] :n V(a,1b,1c.,1di..) :n

Wiel separator index c is het aantal tellers, dat in de rij direkt links van deze sep komt te staan. Zo geeft index d1 het aantal voorgaande rijen in de 2e dimensie, het vlak links. Index di telt in het algemeen de i dimensionale ruimtes links erboven in dimensie i+1.
In alle ruimtes krijgen tellers eerst de waarde a. Ook de rij lengtes en maten van dimensies verder naar links worden a tot aan de basis toe. Terwijl we deze voorgevoegde ruimtes evalueren, groeien de tellers en maten die we daarin opladen recursief. Zodat, wanneer b- opnieuw moet worden - afgeteld, de groeibel a' gigantisch is.

Substitutie met $ subexpressies is aanvankelijk oppermachtig, maar Wiel rijdt met multidimensionale arrays pal naast Bird's lineaire array.
We zijn dan wel twee niveau's dieper genest:
1. Enkele index arrays door de langzame start met optellen versus subexpressies in de bel. Wiel rij Bird's drietal.
2. Een even index niveau (oneven array niveau) door de structuur van unieke seps versus sep herhaling in ruimtes. Wiel matrix Bird's rij.

Wezenlijk is het functie algoritme van Wielewaal even snel als dat van Vogel en Bird, alleen de structuur verschilt. Door alle posities apart te indexeren worden Wiel arrays dubbel genest.
Vogel en Bird herhalen separatoren binnen hun array ruimtes, zodat er lengte ontstaat. Dit aantal kunnen we noteren met een index. Tellers krijgen in de Wiel per definitie een eigen index, maar we mogen ook komma's op de eerste en binnenste rijen gebruiken.

Aasblazer in §2.4 breiden we met rijen komma's uit tot Aasgier geneste arrays. Omdat we de constante aas a opladen, wat bij benadering minimaal is, gelden deze expressies als maat voor de structuur van Wielewaal.
Aasgier arrays tot a[,[,[,1]1]1] schrijven in radix a=10 getallen tot 10^10^10. Astronomisch groot, maar ordes kleiner dan als we bellen b blazen. En toch, bedenk eens hoe weinig van deze getallen ooit fysiek onder ogen gezien (kunnen) worden…!

Bird's Universum

Input expressies en daarmee uitgedrukte getallen zijn exact gelijk aan die van Chris Bird.0 Maar onze array regels, die expressies stap na stap herschrijven, zijn bondiger dan in de originele systemen.
Sommige regels voegen we samen en de overbodige vervallen. De lijst volgorde bepaalt weer welke regel we toepassen, maar is anders dan bij de regels van Bird.

Onze definities krijgen de letter U van Uil en een romeins nummer. Variabelen zijn unair, met optellen van buren, dus b1=b+1.
Daarbij maken hulp regels en afkortingen de notatie leesbaarder.

Rij functie U.I voor Bird's lineaire arrays.1

  • 0.0. 0.1.
  • 1.2. {Y,1} = {Y}
  • 1.3. {a,1,X} = a
  • 1.4. {a,b.,1..Z} :k>0 = {.a,..$,Z} :k

De expressie voor de volgende stap $ is gegeven door bel b met 1 te verminderen (dit telt unit - op).
Gebruik komma's , als separator tussen tellers in rijen.

  • 1.$ {a,1Z} => $ = {a,Z}
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.
4. Chris Bird, Nested Array Notation, 2012.
Bouwwerken van de Lilliputters die Gulliver zijn maaltijd serveren
CALL App.show(UL, className[])
SET tC.App.Tags

No comments:

Post a Comment