§2.7 Belnesten · dims
De matrix of multidimensionale array
van Bellenblazer bestaat uit twee rij niveau's met iteraties.
Subindexen op het derde niveau geven dimensies of dims
aan,
die het onderscheid 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 specifieke regels om Bellenblazer 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 vervangen 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 overlappen,
krijgt het binnenste element dus de beurt.
Definitie Bellenblazer B.III voor multidimensionale 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 voorkomt 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 optelregel
B.1.
uit de definitie van de eerste rij.
Regel
B.4a.
verplaatst b
in de top array of over de index rij.
In een expressie
[,[1b,[2]1]a]a
verliest 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
ingeladen
(en niet a-
na aftelling).
Tot nog toe kwam het goed uit door bij elke regel
`=
de eerste term links te nemen.
Bij de dimensionale arrays begint dat al te wringen,
maar bij geneste arrays is een definitie zonder linkse
=`
eind match problematisch,
omdat een getal (zo groot als) bel b
niet (zo makkelijk) genest kan worden in diepere subarrays.
Tegelijk bouwen we een natuurlijk vervolg voor
Conway's en
Knuth's
pijlen.
Dat kan ergo
in de soepp
draaien, dus voorzichtig!
Hier herhaalt de extra superpijl
↑
de voorgaande operatie net als bij Knuth
rechts associatief.
Op deze superoperator volgt weer een rij met
→
parameters,
die we evalueren als in Conway's pijlfunctie.
- x→↑1! ≡ x
- x→↑y1 =! x→x→↑y == x→..x :y
- X→↑y1→z1 = X→↑(X→↑y→z1)→z == X→↑(..X..)→z :y:
Met 1!
in de eerste regel schieten we op
X→↑1→Z
=
X
en tegelijk op
X→↑1
=
X
die beide met parameters 1
matchen.
De tweede regel voegt vanaf rechts =!
de Conway schakel
x→
in en laat de operatie
x→↑y
aan het einde staan. Herhaling ervan ==
smeedt die schakels aan elkaar tot een nieuwe pijlketen.
Hier is deel X
nog alleen de parameter a
,
terwijl we Conway schakels
→zi
toevoegen.
Elke zi
voert een nieuwe dubbele recursie uit,
eerst →z1
dus over de lengte van Conway's pijlketen zelf.
De eerste Bellenblazer index staat voor de laatste
dubbele recursie van Knuth en de tweede index
voor de tripele recursie 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 ≈> a→↑b2
- [b,[1,1,[2]1]1c]a := ,[b,[2]1]a,["]c ≈> a→↑b2,["]c ≈> a→↑(..b2..) :c1: ≈> a→↑c2→2 {a=b}
- [b,[2,1,[2]1]1c]a := a,[1,1,[2]1]b-,["]c ≈> a→↑b→2,["]c ≈> a→↑(..b..)→2 :c1: = a→↑c2→3 {a=b}
- [b,[d,1,[2]1]1c]a := a,[-"]b-,["]c ≈> a→↑b→d,["]c ≈> a→↑c2→d1 {a=b}
Het is handig om eerder genoemde subarrays
niet te hoeven noteren in de verdere uitwerking.
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 ≈> a→↑a→b1,["]c ≈> a→↑a→(..b1..) :c1: ≈> a→↑b→c1→2
- [1b,[d,2,[2]1]1c]a := a,[-"]b,["]c ≈> a→↑a→b→d,["]c ≈> a→↑a→(..b..)→d :c1: ≈> a→↑b1→c1→d1
- [b,[1,3,[2]1]1c]a := ,[,3,[2]1]b,["]c = a,[b,2,[2]1]a-,["]c ≈> a→↑a→a-→b1,["]c ≈> a→↑a→a→(..b..) :c1: ≈> a→↑a→b→c1→2
- [b,[d,3,[2]1]1c]a := ,[-"]b,["]c ≈> a→↑a→a→b-→d,["]c ≈> a→↑a→b→c1→d1
- [b,[1,1e,[2]1]c]a ≈> a→↑.ab→..c→2 :e
- [b,[d,1e,[2]1]c]a ≈> a→↑.ab→..c→d1 :e ≈> a→↑a→↑e2 {a=b=c=d1}
Bij gelijke parameters
a→..a
zetten we de hele serie precies naar de volgende recursie
a→↑
om. Anders is de Conway superexponent
rechts dominant en kan die de eerdere parameters
≈
representeren.
Met de 2e index
in Bellenblazer bouwden we een Conway keten.
Dan zal de 3e index
een serie tripel recursies
a→↑..
vormen. Laat deze index
,[2]f
verder toenemen, 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 = a→↑a→↑b1
- [1b,[2,1,[2]2]1]a := a,[1,1,[2]2]b ≈> a→↑a→↑a,["]b- ≈> a→↑a→↑(..a..) :b: ≈> a→↑a→↑b→2
- [b,[1,2,[2]2]1]a := a,[b,1,[2]2]a- ≈> a→↑a→↑a-→b1
- [1b,[1,1,[2]3]1]a := ,[a,b,[2]2]a =: a,[1a,b,[2]2]1 ≈> a→↑a→↑.a→..a :b = a→↑a→↑a→↑b1
- [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 superschakel
→↑↑
een type 4
recursie.
Dit verhoudt zich tot Conway's pijlketen,
zoals diens lengte staat tot supermachten.
Of zoals de Ackermann functie
staat tot vermenigvuldigen.
Kortom, zulke getallen zijn ver!
In het algemeen geven operaties
→↑{n}
het recursie type aan,
van een functie die bestaat uit een rij vorige recursies.
De operator heeft een Conway schakel →
met een aantal ↑..
Knuth pijlen erop.
Dat aantal n
bepaalt het type n2
van de recursie,
waarmee we een rij grootmachten
van het type
n1
stapelen.
Evalueer de Conway-Knuth superpijlen
strikt =!
rechts associatief.
- x→↑{n}1 =! x
- x→↑{n1}y1 =! x→↑{n}x→↑{n1}y == x→↑{n}..x :y
We maken hieraan steeds ketens
X→y→z
vast, die we gewoon met de definitie
C.I
van Conway's pijlen evalueren.
Vervolgens drukken we ketens uit met superschakels…
Dit alles blijkt wonderlijk precies te passen
bij de matrix expansie van Bellenblazer…!
- [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→↑↑a→↑b1
- [1b,[1,1,[2]2,[3]1]1]a := ,[a,b,[2]1,[3]1]a ≈> a→↑↑a→↑a.→a.. :b = a→↑↑a→↑a→↑b1
- [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 Bellenblazer arrays, loopt gelijk met de
recursieve superpijlen. Dit voltooit de
multidimensionale ruimte van Bellenblazer arrays,
waarin elke positie een unieke index heeft.
De grootte van de getallen die we hiermee 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 demonstreren door
onze Wielewaal tellerij (denk Bellenblazer)
met het Vogel telraam (denk Bird) te vergelijken.
Bellenblazer expressie
[,[,[n]b]a]a
met dim n1
is een
type n2
recursie. Net als de
→↑{n}
superpijlen, die we uitwerken tot een rij van type
n1
recursies met b
parameters.
Hogere functies blazen het aantal dimensies direkt op
en overstijgen 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 insignificanter worden.
We houden op om hogere recursies of dimensies te indexeren
en laten geneste Bellenblazer arrays verder voor zich spreken.
Conway's recursie →
voegt de in y
afgetelde expressie steeds op de voorlaatste positie in.
We kunnen een hyperpijl
a→→b
tot de superpijl
→↑
reduceren die Conway's pijlketen is.
Maar kunnen we zo ook superpijlen
a→↑{c}b
maken…?
- a→→b→1 = a→→b = a→↑b == a→..1 :b
- a→→1→c = a
- a→→2→2 = a→→a = a→↑a =: a→↑a→↑↑1 =: a→↑↑2
Stel dat
X→→2→2
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 voorlaatste parameter,
die na onze extensie met Knuth pijlen
→↑{m}
zo goed werkt, laat het hier afweten.
Want stel dat
a→→3→2
reduceert tot
a→→(a→→a)
en
a→↑(a→↑a)
dan is dat kleiner dan de
a→↑a→↑a
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…
- a→b1→2 = a↑a→b→2 == a↑..a→1→2 :b = a↑..a :b = a↑↑b1
- a→b1→2 = a↑a→b1→1 = a↑a→b1 = a↑(a↑a→b) == a↑(..a↑a→1..) :b = a↑(..a..) :b1 = a↑↑b1
- a→b→2 = a↑→b→1 = a↑→b = 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→→b→2
=!
a→↑↑b
wèl voor elkaar, mooi zuinig en stapsgewijs,
met een regel voor hyperpijlen…?
Of zal deze formule in de (rechts associatieve) context van Conway-Knuth pijlen altijd ergens mis lopen
en moeten we hyper operatoren indexeren…?
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).
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].