Monday 26 February 2018

Bellnesten

Link naar dit blog:
allergrootste.blogspot.nl/2018/02/bellnesten.html
edit jan.2019.

§2.7 Belnesten · dims

De matrix of multi­dimensionale array van Bellen­blazer bestaat uit twee rij niveau's met iteraties. Sub­indexen op het derde niveau geven dimensies of dims aan, die het onder­scheid maken tussen indexen.
Vorig blog beperkte zich tot B.II het array vlak, de 2e dimensie. De volledige definitie van geneste arrays B.IV komt in volgend blog. En hier geven we de speci­fieke regels om Bellen­blazer expressies uit te werken tot het tweede niveau van geneste arrays.

De linker term bij evaluaties `= en =` in de lijst zoeken we l-r in de expressie. We ver­vangen dat deel door de rechter term. Bij teken `= voeren we de regel uit, die het eerste links in de expressie een match geeft: als in een regex19 scan.
Met onze rij regex [rowex™] scan selecteren we =` een term die het eerst eindigt in de tekst. Van de match met de meest linkse eind positie voeren we de regel met voorrang uit. Wanneer de match arrays over­lappen, krijgt het binnenste element dus de beurt.

Definitie Bellen­blazer B.III voor multi­dimensionale arrays.

  • B.0. B.1. B.2.
  • B.3a. [,[1S]1Z]a =` [a,[1S]Z]a
  • B.3b. [,[1n]1S]b [b,[1n]S]a
  • B.4a. [b,[2m]1 =` [,[1m]b,[2m]
  • B.4b. [b,[1n,1S]1 `= [,[n,1S]b,[1n,1S]

Variabelen zijn altijd gretig naar enen, zodat rechts van een geslaagde match Yp geen getal meer voor­komt in de expressie XYpZ. Sec in woorden in regels kloppen alle haakjes, met name in S hier.
Vertaal de eerste index sep ,[1]1S := ,1S met hulpregel b.1.
In regel B.3a. staat S>0 òf voor de rij lengte 1n óf voor een deel 1n,1R met de rechter lengtes van de dimensies. Het geval S=0 valt onder optel­regel B.1. uit de definitie van de eerste rij.

Regel B.4a. ver­plaatst b in de top array of over de index rij.
In een expressie [,[1b,[2]1]a]a ver­liest regel B.3a. zijn match aan regels B.4a. en B.3b. die voorrang =` krijgen. Zo vullen we de binnenste array eerst [,[a,b]a]a en wordt a inge­laden (en niet a- na aftelling).
Tot nog toe kwam het goed uit door bij elke regel `= de eerste term links te nemen. Bij de dimen­sionale arrays begint dat al te wringen, maar bij geneste arrays is een definitie zonder linkse =` eind match proble­matisch, om­dat een getal (zo groot als) bel b niet (zo makkelijk) genest kan worden in diepere sub­arrays.

Tegelijk bouwen we een natuurlijk ver­volg voor Conway's en Knuth's pijlen. Dat kan ergo in de soepp draaien, dus voor­zichtig!
Hier herhaalt de extra super­pijl de voor­gaande operatie net als bij Knuth rechts associa­tief. Op deze super­operator volgt weer een rij met para­meters, die we eva­lueren als in Conway's pijl­functie.

  • x1! ≡ x
  • xy1 =! xxy == x..x :y
  • Xy1z1 = X(Xyz1)z == X(..X..)z :y:

Met 1! in de eerste regel schieten we op X1Z = X en tegelijk op X1 = X die beide met para­meters 1 matchen.
De tweede regel voegt vanaf rechts =! de Conway schakel x in en laat de ope­ratie xy aan het einde staan. Her­haling ervan == smeedt die schakels aan elkaar tot een nieuwe pijlketen.

Hier is deel X nog alleen de para­meter a, terwijl we Conway schakels zi toevoegen. Elke zi voert een nieuwe dubbele recursie uit, eerst z1 dus over de lengte van Conway's pijl­keten zelf.
De eerste Bellen­blazer index staat voor de laatste dubbele recur­sie van Knuth en de tweede index voor de tripele recur­sie van Conway. Refereer voor deze twee indexen naar de dim 2 formule.

  • [b,[1,[1]1,[2]1]1]a 4b 2 := [,[,1,[2]1]b]a 3b 2 = [,[b,[2]1]a]a 4a 2 =` [,[,b]a]a 3b 3a := a,[a,b-]a- ≈> a..a-a1 :b ≈> ab2
  • [b,[1,1,[2]1]1c]a := ,[b,[2]1]a,["]c ≈> ab2,["]c ≈> a(..b2..) :c1: ≈> ac22 {a=b}
  • [b,[2,1,[2]1]1c]a := a,[1,1,[2]1]b-,["]c ≈> ab2,["]c ≈> a(..b..)2 :c1: = ac23 {a=b}
  • [b,[d,1,[2]1]1c]a := a,[-"]b-,["]c ≈> abd,["]c ≈> ac2d1 {a=b}

Het is handig om eerder genoemde sub­arrays niet te hoeven noteren in de verdere uit­werking. We kunnen index arrays aangeven met een quote ["] om een array [1X] uit de vorige lijn aan te halen. En een minus [-"] links om die [X] af te tellen. Zoals altijd moet ook zonder kleuring duidelijk zijn welke array is bedoeld.

Bouw een nieuwe Conway keten met dubbele recursies (type 2). Tel daar de lengte van met de volgende tripel recursie (type 3).

  • [b,[1,[1]2,[2]1]1c]a := [,[,2,[2]1]b,["]c]a := a,[b,1,[2]1]a-,["]c ≈> aab1,["]c ≈> aa(..b1..) :c1: ≈> abc12
  • [1b,[d,2,[2]1]1c]a := a,[-"]b,["]c ≈> aabd,["]c ≈> aa(..b..)d :c1: ≈> ab1c1d1
  • [b,[1,3,[2]1]1c]a := ,[,3,[2]1]b,["]c = a,[b,2,[2]1]a-,["]c ≈> aaa-b1,["]c ≈> aaa(..b..) :c1: ≈> aabc12
  • [b,[d,3,[2]1]1c]a := ,[-"]b,["]c ≈> aaab-d,["]c ≈> aabc1d1
  • [b,[1,1e,[2]1]c]a ≈> a.ab..c2 :e
  • [b,[d,1e,[2]1]c]a ≈> a.ab..cd1 :e ≈> aae2 {a=b=c=d1}

Bij gelijke para­meters a..a zetten we de hele serie precies naar de volgende recursie a om. Anders is de Conway super­exponent rechts domi­nant en kan die de eerdere para­meters repre­senteren.

Met de 2e index in Bellen­blazer bouwden we een Conway keten. Dan zal de 3e index een serie tripel recursies a.. vormen. Laat deze index ,[2]f verder toe­nemen, functie rij na functie rij. Tot we ook daar weer over kunnen ↑↑ itereren.

  • [1b,[1,[1]1,[2]2]1]a := ,[1b,[2]2]a = a,[a,b,[2]1]a- ≈> a.a..a :b = aab1
  • [1b,[2,1,[2]2]1]a := a,[1,1,[2]2]b ≈> aaa,["]b- ≈> aa(..a..) :b: ≈> aab2
  • [b,[1,2,[2]2]1]a := a,[b,1,[2]2]a- ≈> aaa-b1
  • [1b,[1,1,[2]3]1]a := ,[a,b,[2]2]a =: a,[1a,b,[2]2]1 ≈> aa.a..a :b = aaab1
  • [1b,[1,1,[3]1]1]a := ,[1b,[3]1]a = ,[a,[2]b]a =: a,[1a,a-,[2]b-]1 ≈> a..a :b = a↑↑b1

Zo definieert de super­schakel ↑↑ een type 4 recursie. Dit verhoudt zich tot Conway's pijl­keten, zoals diens lengte staat tot super­machten. Of zoals de Acker­mann functie staat tot vermenig­vuldigen. Kortom, zulke getallen zijn ver!

In het algemeen geven operaties {n} het recursie type aan, van een functie die bestaat uit een rij vorige re­cursies. De ope­rator heeft een Conway schakel met een aantal .. Knuth pijlen erop.
Dat aantal n bepaalt het type n2 van de recursie, waar­mee we een rij groot­machten van het type n1 stapelen.

Evalueer de Conway-Knuth super­pijlen strikt =! rechts associatief.

  • x{n}1 =! x
  • x{n1}y1 =! x{n}x{n1}y == x{n}..x :y

We maken hieraan steeds ketens Xyz vast, die we gewoon met de definitie C.I van Conway's pijlen eva­lueren. Ver­volgens drukken we ketens uit met super­schakels… Dit alles blijkt wonder­lijk precies te passen bij de matrix expansie van Bellen­blazer…!

  • [1b,[1,[1]1,[2]1,[3]1]1]a := ,[1b,[2]1,[3]1]a =: a,[1a,b,[3]1]1 ≈> a↑↑.a..a :b = a↑↑ab1
  • [1b,[1,1,[2]2,[3]1]1]a := ,[a,b,[2]1,[3]1]a ≈> a↑↑aa.a.. :b = a↑↑aab1
  • [1b,[1,1,[3]2]1]a := ,[1b,[3]2]a = ,[a,[2]b,[3]1]a ≈> a↑↑a.a.. :b = a↑↑a↑↑b1
  • [1b,[1,1,[4]1]1]a := ,[1b,[4]1]a = ,[a,[2]a-,[3]b-]a ≈> a↑↑..a :b = a↑↑↑b1
  • [b,[1,1,[1n]1]1]a := ,[,[n]b]a ≈> a{n-}..1 :b = a{n}b

De eerste rij op het 2e niveau van Bellen­blazer arrays, loopt gelijk met de recur­sieve super­pijlen. Dit vol­tooit de multi­dimensionale ruimte van Bellen­blazer arrays, waarin elke positie een unieke index heeft. De grootte van de getallen die we hier­mee schrijven, is gelijk aan die van Bird's lineaire arrays.18
Dat concludeerden we uit de matrix van Btrix in box 2.6 en zullen we later in blog §3.1 nog eens demon­streren door onze Wielewaal tel­lerij (denk Bellen­blazer) met het Vogel tel­raam (denk Bird) te vergelijken.

Bellen­blazer expressie [,[,[n]b]a]a met dim n1 is een type n2 recursie. Net als de {n} super­pijlen, die we uit­werken tot een rij van type n1 recursies met b parameters.
Hogere functies blazen het aantal dimensies direkt op en over­stijgen het huidige recursie plafond. Een tweede recursie type index is nodig, daarna een 3e index, index rij type recursies, vlak type, etcetera.
Uiteindelijk loopt zo'n typering van recursies nog maar weinig achter bij die van arrays. Want dit verschil zal bij dieper nesten insigni­ficanter worden. We houden op om hogere recursies of dimensies te index­eren en laten geneste Bellen­blazer arrays verder voor zich spreken.


Conway's recursie voegt de in y afge­telde expressie steeds op de voor­laatste positie in. We kunnen een hyper­pijl a→→b tot de super­pijl reduceren die Conway's pijl­keten is.
Maar kunnen we zo ook super­pijlen a{c}b maken…?

  • a→→b1 = a→→b = ab == a..1 :b
  • a→→1c = a
  • a→→22 = a→→a = aa =: aa↑↑1 =: a↑↑2

Stel dat X→→22 gelijk is aan X(X) dan is dat voor ketens X>x groter dan X↑↑2 en loopt dit voorstel in de soep.
Conway's substitutie in de voor­laatste para­meter, die na onze extensie met Knuth pijlen {m} zo goed werkt, laat het hier afweten. Want stel dat a→→32 reduceert tot a→→(a→→a) en a(aa) dan is dat kleiner dan de aaa die we uit a↑↑3 herleiden.

Nog wat frutsels in dit verband, die de lezer een idee moeten geven, hoe dit soort natuurlijke systemen na rijp beraad tot stand komen…

  • ab12 = aab2 == a..a12 :b = a..a :b = a↑↑b1
  • ab12 = aab11 = aab1 = a(aab) == a(..aa1..) :b = a(..a..) :b1 = a↑↑b1
  • ab2 = ab1 = ab = a↑↑b

En wie X→→y→→z tot X{z}y reduceert, die gebruikt twee hyper operaties in plaats van één.
Dus hoe krijgen we a→→b2 =! a↑↑b wèl voor elkaar, mooi zuinig en staps­gewijs, met een regel voor hyper­pijlen…? Of zal deze formule in de (rechts associa­tieve) context van Conway-Knuth pijlen altijd ergens mis lopen en moeten we hyper opera­toren indexeren…?

o. Extensie van Knuth-Conway stijl pijlen, om array functies mee te vergelijken, gg: Big Arrows Compass voor Brobdingnagians (blog dec 2012).
p. Pijlen naar het noordwesten schieten, gg: Big Arrows Compass I en II met een anekdote van prof. Gill, hoe prof. Conway het schoolbord van ωω naar εε draaide ! op xs4all en Brobdingnagians blog (concept jan 2013).
18. Een systeem voor snel groeiende recursieve functies, dat de functies van Jonathan Bowers en anderen ver te boven gaat, in Christopher M. Bird's Super Huge Numbers, een serie van 9 PDFs over Bird's arrays + 3 bijlagen, 2017.
19. Vindt de eerste positie in de string waar een match mogelijk is, §11.1.3.1 Nongreedy repetition, in David Flanagan "JavaScript" 2006. [bijv. ook lui patroon a*?b matst aaab geheel].
Gulliver redt de vloot van Lilliput