$ 1. Getallen
Tel op tot een getal en herhaal getallen
en hun herhalingen en noteer dit in functies.
Elk object van de wiskunde is telbaar,
en zo ook de relaties tussen die objecten.
Getal relaties of functies die zichzelf herhalen
heten "recursief".
Recursie is versneld tellen,
maar de "googologie" of leer van de grote getallen,
begint gewoon met tellen op je vingers.
$ 1.1. Tellen
Neem eerst het getal 'nul' 0
dat in wezen niets is,
en stop zonder te tellen.
Een tel erbij 01
geeft het getal 1 een.
Maak vervolgens de natuurlijke getallen,
door units 'een' 1 op te tellen
tot een aantal 1.. enen is bereikt
(dat gelijk is aan het getal)
waar het tellen stopt.
Definieer dit met een repetitie of 'rep'
over de selectie 1 , die op zijn .. plaats
het aantal :n keer wordt herhaald
tot de uitkomst = het getal n geeft.
1.. :0 = 0
1.. :n = n
Maak een getal negatief door links
voor de positieve een factor - te plaatsen.
Of vorm gehele negatieve getallen
door een aantal units 'min' -..
van rechts op te tellen.
Waarbij 1- nul 0 of leeg is.
Peano's primitieve opvolger functie σ
maakt elk volgende natuurlijke getal.
σ(0) = 1
σ(n) = n1
Druk getallen n uit
door functies σ(..) :n: herhaald te nesten,
dan staat elke aanhaling van σ(.)
gelijk aan een 1 tel.
Tellen dat nooit stopt drukt per definitie
een oneindig getal uit.
1... = ω
Getal omega ω zou het eerste en kleinste
oneindige getal boven de natuurlijke getallen zijn.
Waarna het tellen σ(ω) = ω1
weer verder kan gaan.
Getallen zijn wiskundige constructies.
Gehele en oneindige getallen bestaan
uit eenheden of units
en tellen dat stopt of niet.
Operaties en functies en hun inversen
drukken nog meer getallen uit:
breuken en wortels,
transcendente en complexe getallen;
tussen de gehele getallen in en daaraan ontstegen.
Recursieve functies in dit deel blijven
in het domein van de natuurlijke getallen.
$ 1.2. Basisnotatie
Lees getallen in unaire notatie
door elke 1 erin een keer te tellen.
Stop met enen tellen bij getal tien
dat de decimale basis vormt.
Tel dan de tientallen.
Stop na tien keer tien bij een honderd.
Tel tien honderdtallen tot een duizend.
Duizend duizendtallen maakt een miljoen.
Tot zo ver zijn onze landen
het wel met elkaar eens.
De eerste natuurlijke getallen na 1
in decimale notatie met cijfers 2,3,4,..
en unair gedefinieerd.
Zet deze ook om =>
in binaire notatie in basis 'twee'.
2 = 11 => 10
3 = 111 => 11
4 = 1111 => 100
5 = 11111 => 101
6 = 111111 => 110
7 = 1111111 => 111
8 = 11111111 => 1000
9 = 111111111 => 1001
10 = 1111111111 => 1010
11 = 11111111111 => 1011
12 = 111111111111 => 1100
Systemen voor grote getallen geven als output
reeksen 1.. enen.
Maar in de input en bij voorbeelden
schrijven we getallen met cijfers en decimaal.
Voor de duidelijkheid voegen we
aan decimale getallen met meerdere cijfers
een punt toe, zoals bij 10. onze 'tien'.
In een basis notatie met radix r
hebben de gehele getallen van 0 tot r-
enkele cijfers.
Dan volgt de basis r=10
en de volgende getallen met meerdere cijfers.
De notatie lengte is door de extra tekens bekort.
Onder de r^k kunnen de natuurlijke getallen uniek
worden becijferd op k of minder plaatsen.
Een getal in basis r
met een k1 aantal cijfers d_i
is te vertalen := naar een serie
factoren d_i* van oplopende machten ^i
van r die opgeteld + wordt.
d_i.. k:0 :=
d_0.+d_i*r^i.. 1:k
Index i neemt elke volgende stap toe of af
met 1 zoals dit van links : op rechts
is aangeduid in de 'rep'.
De waarde van cijfer plaatsen neemt 'l-r' af,
van links naar rechts,
terwijl de constructie van getallen bij herhaalde
vermenigvuldiging van 10 op moet lopen.
Naast de historische herkomst van de cijfers
is dus ook de opbouw van de decimale getallen
'r-l' in de richting van het Arabische schrift.
Voordeel is dat 'l-r' lezers het belangrijkste cijfer
van de grootste macht nu vooraan zien staan.
- - - - - - - - - - - - - - - -
Vraag: In basis 6 is het getal 555
hetzelfde als 215. in basis tien.
Maar als de bases onbekenden zijn,
zijn die dan te berekenen..? Valt te bewijzen,
dat geen enkel ander basis paar voldoet..?
En als dit in het algemeen onmogelijk is,
voor welk soort getallen kan het wel..?
$ 1.3. Getalgaten
Getallen kunnen bestaan uit eenheden of units,
of verkort geschreven worden met operaties of functies
in een wiskundige expressie.
Expressies voor natuurlijke getallen
zijn met behulp van regels te evalueren
tot een uitkomst bestaande uit een aantal enen.
Om structuur toe te voegen aan de expressie
zetten we extra tekens in. En ook het algoritme,
met de definitie van de regels voor evaluatie van expressies,
zorgt voor een uitbreiding van ons wiskundig taalapparaat.
Doel van de googologie is om met een minimaal
aantal tekens en zo beperkt mogelijke regels,
zo groot mogelijke getallen te noteren.
Om hogere wiskundige structuren te herkennen
en daarover dan te itereren tot in het oneindige.
Hoe sneller de functie, hoe meer getallen
tussenin gemist worden in de notatie.
Zulke grote gaten liggen dieper verborgen
dan de grote getallen zelf, die als vuurtorens boven
hun eiland van naburige kenbare getallen uitsteken,
terwijl de random zee van getallen eromheen
onkenbaar is.
Vrij snel in dit verhaal zijn de meeste
natuurlijke getallen door geen enkel praktisch
getalsysteem meer te bevatten. Want de systemen
die in ons fysisch heelal mogelijk zijn, zijn beperkt
door het aantal te observeren quantum bits.
We kunnen stellen dat binaire getallen
met een lengte van ongeveer 10^81 (Vopson 2019)
tot wel 10^90 (Lloyd 2001)
zich nog in het zicht bewegen.
Daarboven wonen de goden.
In elk wiskundig systeem is de expressie lengte
van de meeste gehele getallen groter
dan in een radix met evenzoveel tekens.
Hoewel dit verschil niet meer dan
een luttele basismacht 10 kan bedragen in totaal,
omdat al die expressies uiteindelijk
tot 1.. evalueren in de systeem output.
Al de getallen die de mens kan gebruiken
zijn relatief "klein".
Het vervolg van dit reisverhaal in de getallen
zal bijgevolg volstrekt nutteloos zijn, hopelijk...
$ 1.4. Googols
Een beroemd groot getal is de "googol",
geschreven als 10^100 met exponent,
of in basis tien als een 1
gevolgd door 100 nullen.
De Babyloniërs zouden hier in basis 60
een reeks van 57 spijkerschrift tekens
voor nodig hebben. In de digitale radix 256
neemt dit 42 bytes in beslag.
Voor de googoloog,
die net als Google zijn naam dankt aan dit getal,
geeft een basis notatie erge rompslomp.
Cijfers zijn handig om getallen mee af te korten,
maar googologen tellen net zo goed weer enen
als onbenullen nullen.
Een "googolplex" is een 1 met googol nullen,
ofwel 10^10^100 met dubbele exponent.
Dit getal zou in de hypothetische basis "googol"
met 10^98 nullen geschreven worden.
Als elke 0 daarin de maat van een bacterie heeft
vullen die de gehele ruimte van het heelal,
een voorbeeld van de onmacht van radix systemen.
Om een random getal verborgen in de zee rondom
het googolplex uit te drukken met quantum bits,
hebben we tot wel 10^20 keer zoveel
van die deeltjes nodig dan er in dit heelal te vinden zijn.
Zelfs bij een vrije keuze om elke mogelijke
wiskundige expressie te evalueren
met elk mogelijk wiskundig systeem,
weer te geven als input (uitrekenen hoeft niet)
op onze ene universum quantum tablet,
is het nog onzeker of elk getal opgevist zou
kunnen worden. Met een hogere exponent erbij
de meeste random getallen zeker niet!
Googolplex is al een onbegrijpelijk groot getal.
Het eerste vuurtoren eiland dat we aandeden
op onze ontdekkingsreis naar het oneindige.
- - - - - - - - - - - - - - - -
Vraag:
Googol is 10^100 .
Vind een benadering voor de tetratie wortel t ,
zodat t^^t dicht in de buurt komt van googol.
Stel t is een exact reëel getal,
niet fundamenteel fuzzy of onkenbaar,
hoort t thuis in een nieuwe klasse..?
Sneller en dieper verzonken in de getallenlijn
dan de eindeloze rij breuken, waarmee we algebraïsche
en transcendente reëele getallen benaderen...?
Stel dat deze superwortels niet kunnen worden berekend.
Dan bestaan ze wel door hun wiskundige definitie,
maar blijven fundamenteel onbenaderbaar
en vallen buiten het deelbare 2^ω continuüm.
Er zijn oneindig veel hogere ^{c} operaties
en functies met *[X] superarrays.
Zijn de meeste inversen daarvan zo vaag,
dat ook hun relatieve ordening onbekend moet blijven..?
$ 2. Supermachten
Elke supermacht operatie ^{c1}
herhaalt een aantal vorige ^{c}
supermacht operaties.
Hier telt c>0 het aantal carets, en
het expressie deel links van de punten ..
wordt in totaal b keer
door de 'rep' :b herhaald.
a^{c1}b1 = a^{c}..a :b
De supermacht operaties ^{c} of *{c1}
zijn rechts associatief, dus deze expressies
worden verder 'r-l' van rechts naar links uitgewerkt.
Stapsgewijs definiëren we dit als volgt,
waarbij *{c≥0} en vermenigvuldiging *
tot een reeks directe optellingen reduceert.
a*{c1}b1 = a*{c}(a*{c1}b)
== a*{c}(..a*{c1}1..) :b:
:= a*{c}..a :b
We zullen deze supermachten evalueren met
de nieuwe "popster" operaties.
Dit sluit nauw aan bij een primitief recursieve
functie voor supermachten over een rij variabelen.
We bouwen dit popster systeem langzaam op.
$ 2.1. Rekenwerk
Met de eerste supermachten *{k<3}
is gewoon nog te rekenen.
Dit zijn de operaties van optellen *{0}
en vermenigvuldigen *{1}
en machtsverheffen *{2}
waarvan ook de inversen, als breuken
en reële en complexe getallen kenbaar zijn.
$ 2.1.1. Ster 0 optellen
Bij variabelen met natuurlijke getallen a en b
die naast elkaar staan, is meteen de som ab gegeven,
waarin alle enen 1.. bij elkaar optellen.
Plaats een 'plus' teken + tussen variabelen
om optellen uit te stellen.
- +a+b =` +ab
- a+b = ab
Door de regels • voor optellen
consequent vanaf rechts toe te passen,
komen wachtende operaties beschikbaar
en kan hun + wegvallen.
Het "is gelijk" teken = drukt gelijkheid uit
en betreft de evaluatie van hele expressies
of subexpressies (binnen haakjes).
Het "is rechts" teken =`
selecteert vanaf rechts in de expressie.
Daarmee werken we operaties 'r-l' uit,
reducerend van rechts naar links.
Zo werken we een optelling tot getal stapsgewijs uit.
1+1+1+1 = 1+1+11
= 1+111 = 1111 = 4
De actieve plus operatie is te beschouwen
als *{0} nulde superster, die leeg is.
Alle operaties rechts van een plus teken
krijgen voorrang, maar ook elke hogere operatie
die links ervan staat.
$ 2.1.2. Ster 1 vermenigvuldigen
Vermenigvuldigen is herhaald optellen
van een constant a.. getal.
Het keer of maal teken ertussen
schrijven we met een * ster.
Definitie van vermenigvuldigen voor gehele getallen.
Stel b>0 zodat de tweede regel in de laatste stap
de iteratie overneemt van de eerste regel.
- a*b1 =` a*b+a
- a*1 =` a
Vindt een match vanaf rechts =`
in de expressie voor de vorm links in de regel.
Iedere iteratie stap telt een constante a op bij de som.
Herhaal de reeks stappen ==
in combinatie met optellen, tot de laatste stap
de operator elimineert en de uitkomst levert.
a*b1 = a*b+a
== a*1+.a.. :b
= a.. :b1
De 'rep' :b herhaalt de tussen .
of terzijde van de punten ..
geselecteerde passage b maal.
Reps zijn beschrijvend bedoeld en niet regelgevend.
Een voorbeeld van vermenigvuldiging als optellen in stappen.
Neem de vertaling naar decimale getallen hier voor lief.
2*3 = 2*2+2 = 2*1+2+2
= 2*1+4 = 2+4 = 6
De iterator is hier 111
en in het algemeen een variabele b
waar elke stap 1 vanaf telt
om een kopie van a op te sommen.
De ster van vermenigvuldigen
is de eerste superster operator.
$ 2.1.3. Ster 2 machtsverheffen
Machtsverheffen ** of ^
is herhaald vermenigvuldigen.
Om machten stapsgewijs uit te werken,
met de lagere operaties eerst,
moeten we de hogere in de wacht zetten.
De 'pop' plus bij de ster *+ operatie
stelt vermenigvuldiging uit, alsof deze
tussen haakjes staat tot de ster ontpopt.
Evalueer popster machten volgens
deze speciale definitie, waar b>0 .
- +a*+b =` +a*b
- a*+b = a*b
- a**b1 =` a**b*+a
:= a*..a :b
- a**1 =` a
We hebben de regels in een volgorde gezet, die het mogelijk
maakt om deze definitie op twee manieren toe te passen:
hetzij door de bovenste toepasbare regel uit te voeren,
hetzij de regel die meest rechts in de expressie aangrijpt.
We gebruiken het toewijzingsteken := voor een vorm
van expressie, die niet via de regels te bereiken is.
Zoals hier voor een reeks factoren,
want de regels werken factor voor factor uit tot getal.
2**3 = 2**2*+2 = 2**1*+2*+2
= 2**1*+2*2 == 2**1*+4
= 2*+4 = 2*4
== 8 := 2*2*2
Hoewel dit vanzelf niet in de uitwerking kan gebeuren,
telt het popster systeem in a^b+1
één op bij een factor, maar in 1+a^b
gewoon bij het totaal.
Volgt een ster *+ met pop plus,
dan komt die gewoon als factor bij de reeks factoren.
Deze regels werken zonder precedentie
en evalueren strikt 'r-l' vanaf rechts,
wat vreemde resultaten geeft
als we ster operaties op elkaar schrijven.
2**3*2 = 2**3*1+3 = 2**3+3
= 2**2*+2+3 = 2**2*+5
= 2**1*+2*+5 = 2**1*+2*5
== 2**1*+10. = 2*+10.
= 2*10. == 20.
We kunnen het ook anders regelen:
om carets ^ met meerderheids-precedentie
op te lossen (hogere operaties met meer tekens eerst),
en daarna sterren * met minderheids-precedentie
(voorrang aan minder tekens).
Dan zou 2**3*2 = 2^6 groter zijn,
maar 2^3*2 = 8*2 kleiner.
$ 2.2. Popsterren
Popster supermachten zijn stapsgeweijs te reduceren,
enkel met een plus *+ teken en zonder haakjes.
Met meer sterren in de operator *_^[..]
worden de uitgedrukte getallen supergroot.
$ 2.2.1. Definitie
De eerste echte supermacht operatie met drie *** sterren
of twee ^^ dakjes heet "Tetratie".
Dit levert een aantal machtsverheffingen op,
een toren van exponenten die 'r-l'
van rechts naar links moet worden opgelost.
a***b1 = a**(a***b)
== a^(..a^^1..) :b:
:= a^..a :b
De macht operant b
vormt een reeks of toren van operaties met constantes a .
In het popster systeem schrijven we deze torens niet
in hun geheel, maar top operaties komen rechts apart
te staan en worden met voorrang uitgewerkt.
Definitie voor de evaluatie van 'PopSter' supermachten.
Steeds is b>0
maar de operator *{c≥0} kan leeg zijn.
-PS.1a. +a*{c}+b =` +a*{c}b
-PS.1b. a*{c}+b = a*{c}b
-PS.2. a*{c1}b1 =` a*{c1}b*{c}+a
-PS.3. a*{c1}1 =` a
We voeren die regel uit, die een match geeft
op de meest rechtse =` positie in de expressie.
Maar in de evaluatie van een supermacht blijft dit
hetzelfde als voorrang geven aan de bovenste regels.
Variabelen zijn "gretig" naar enen,
zodat elke getal a in de regels compleet is,
zonder rest deel in de expressie.
Trap '1.' elimineert de plus
uit de rechts gelegen popster.
Stap '2.' ster operatie introduceert
kleinere popster met operant.
Stap '3.' elimineert als laatste stap
de ster operatie.
De evaluatie van supermachten kan toe met vier regels.
Of zelfs drie, wanneer we regel '1a' en '1b'
regulier samenvatten.
De operatie van *{c}+ wordt actief,
als links ervan een plus komt te staan.
Het kan zonder regel '1b' door een plus teken +X
voor alle expressies te zetten,
maar dan is een nieuwe regel +x = x
nodig die de uitkomst geeft.
$ 2.2.2. Evaluatie
Als voorbeeld evalueren we de macht 2**2
en de supermacht 2****3
in stappen met de 'PopSter' regels.
We schrijven voor het gemak carets,
waarbij *{c1} en ^{c} gelijk zijn en
hier strikt rechts associatief 'r-l'
met de pop plus uitgewerkt.
2^2 = 2^1*+2
= 2*+2 = 2*2
= 2*1+2
= 2+2 = 4
De ster en pop plus eliminatie van regels 3. en 1.
volgen steeds na elkaar, dus kan dat ook = ineens.
Een reeks stappen geven we vaak wel met == aan.
2^^^3 = 2^^^2^^+2
= 2^^^1^^+2^^+2
= 2^^^1^^+2^^2
= 2^^^1^^+2^^1^+2
= 2^^^1^^+2^2
= 2^^^1^^+4
= 2^^4 = 2^^3^+2
= 2^^2^+2^2
= 2^^2^+4
= 2^^1^+2^4
= 2^^1^+2^1*+2*4
= 2^^1^+2^1*+2*1+6
= 2^^1^+2^1*+8
= 2^^1^+2*8
= 2^^1^+16.
= 2^16. == 65536.
De hogere machten in de toren werken we eerder uit,
dat is dus het principe.
Een ander voorbeeld,
de evaluatie van 3****2 of 3^^^2 met popsterren.
3****2 = 3***3
= 3***2**+3 = 3**+3**+3
= 3**+3**3 = 3**+3*+3*3
= 3**+3*+3+6 = 3**+3*9
= 3**+27. = 3**27.
== 7625597484987.
Alle supermacht expressies zijn met
twee type tekens, de 1 en * te noteren.
Tijdens de evaluatie komt daar de pop +
als solo haakje bij. Slechts drie tekens!
Dakjes ^ of carets en ^+ popcarets,
cijfers en tientallige getallen (met decimale punt)
nemen we erbij als afkortingen.
$ 2.2.3. Toepassingen
We kunnen sommige supermacht operaties
alleen ruwweg met elkaar vergelijken qua grootte.
In dit voorbeeld neemt het absolute verschil <
tussen twee ster supermachten bij grotere c toe.
Terwijl dit verschil in de context
van de hierdoor groeiende reeksen
klein begint met 1 en niet significanter zal worden.
2^{c}4 = 2*{j}..8 c:1 <
3^{c}3 = 3*{j}..9 c:1
De teller {c} geeft in krulhaakjes
het aantal tekens in de operator aan.
De repetitie c:1 noteert een reeks
waarin de indexen j naar rechts afnemen.
In de expressie a^{c}b1*{d}+e
ontpopt de iteratie van rechts als hoogste exponent
in de toren a*{c}..a*{d}e :b
wat significant kan zijn.
Deze extra resolutie vormt een aanvulling op ons rekenapparaat,
waarmee array functies nauwkeuriger zijn te schatten.
Zo helpen popsterren om de oceaan van de supermachten
en hun naburige supermachtige getallen in kaart te brengen.
In de teller kan ook een subexpressie staan,
die met voorrang wordt uitgewerkt.
En dat in serie, zoals Gardner het
Getal van Graham
aangeeft, met geneste superexponenten en Knuth's pijlen.
3↑{..3↑↑↑↑3..}3 :63:
= 3^{..4..}3 :64:
= 3*{..4..+1}3 :64:
De duorep :d: herhaalt selecties
aan beide kanten van de expressie.
Plaats elke selectie op zijn punten ..
links erna en rechts ervoor in de expressie.
En werk in stappen van binnen naar buiten,
tot de rep tot :1: is uitgeteld
en deze met de punten uit de expressie verdwijnt.
Pas in 1976 werden superoperaties uitgevonden
door Donald Knuth met carets in de vorm van
oppijlen ↑{c} in zijn essay
"Omgaan met eindigheid".
Maar dezelfde dubbele recursie φ_c(a,b)
inclusief Ackermann functie
was al te vinden bij David Hilbert in zijn artikel
"Over het oneindige" uit 1925.
$ 2.2.4. Functie vorm
Evaluatie van supermachten gaat makkelijker in een functie.
Alle operaties a*{c}b die we uitwerken volgens de
'PopSter' definitie krijgen deze vorm.
a*{c_i+1}b_i*{c_i}+..b_0 k:1
waar b>0 en c_i1>c_i≥0
Elke superster telt daarin een ster *
meer dan de erop volgende popster.
Deze sterparen nemen naar rechts af,
maar niet alle sterparen
hoeven in die reeks voor te komen.
Stel nu, dat we voor de ontbrekende supermachten
in die reeks een operant b=0 nemen
(een permanente nul), die zijn sterpaar reduceert
tot een wegvallende nul 01 = 1
(tegen de variabele erna) met een extra regel.
-PS.4. a*{c>0}0*{d}+ =` 0
Zo is de reeks van sterparen
die naar rechts toe aflopen compleet.
a*{i}b_i*{i-}+..b_0 k:1
En verloopt een uitwerking vanaf rechts
bijvoorbeeld via:
2^^^^1^^^+2^^^0^^+2^^2^+2^0*+2*0+1
= 2^^^^1^^^+2^^^0^^+2^^2^+1
== 2^^^^1^^^+2^^^0^^+4
= 2^^^^1^^^+4
= 2^^^+4 = 2^^^4
== 2^^65536. := 2^..1 :65536
Omdat alleen de operanten b
en het aantal carets ^{c} of sterren *{c1}
variabel zijn en kenmerkend, is het overbodig
om de constante a voortdurend aan te halen.
Ook komt er van ieder sterpaar nu één voor,
in rangorde 'r-l' oplopend,
met de hogere supermachten links in de wacht.
Om tijdens de uitwerking een popster expressie op te slaan,
hoeven we dus enkel de constante a
en alle variabelen b_i in volgorde te noteren.
2^^^^2^^^+ 2^^2
2^^^^2^^^+2^^^0^^+2^^2^+2^0*+2*0+1
2^^^^2 ^^^0 ^^2 ^0 *0+1
2 2 0 2 0 0 1
2, 1,0,0,2,0,2
Alle essentiële data is hier met zeven getallen gegeven.
En we draaien de rij met zes variabelen ook om,
zodat de evaluatie 'l-r' in leesrichting kan verlopen.
De achterste pop +1 is eigenlijk alleen
voor de vorm en kan in de functie
door een andere regel worden ondervangen.
Getal 0 schrijven we zonder enen.
Dan toont deze popfunctie,
dat het aantal supermachten *{k}n steeds 1
verschilt met het corresponderende aantal
komma's ,{k1}n links in de rij.
2*{6}3 = 2*****2****+2***2
11,{7}111 = 11,,,,11,,11
Zo zetten we supermacht expressies om naar
een rij structuur, met nog maar twee tekens
en een veel kortere expressie lengte.
De regels voor de evaluatie
van een dergelijke functie zijn simpeler
en zien we in het volgende hoofdstuk.
$ 3. Rij functies
De systemen in dit hoofdstuk zijn beperkt tot
een enkele rij met getal variabelen. We ontwerpen
de primitief recursieve functies Adam en Eva,
die beide in het domein van de supermachten liggen.
$ 3.1. Systeem Adam
Systeem 'A' voor "Adam" krijgt over de eerste rij
dezelfde functie vorm als de popster supermachten
uit het vorige hoofdstuk.
Thema bij de constructie van Adam is natuurlijkheid,
waarbij iteraties worden afgeteld tot 0
en structuren leeg kunnen staan.
$ 3.1.1. Primitieve recursie
Om zo zuinig mogelijk te zijn met type tekens,
gebruikt systeem Adam geen ronde haakjes.
We substitueren geen subexpressies (X)
maar steeds hetzelfde getal, een constante a kopie.
Binnen Adam staan we geen "functie recursie" toe,
waar functie variabelen worden overschreven
door de afgetelde functie expressie.
Adam rij expressies bestaan uit de tekens 1 voor getallen
en daartussen enkele komma's , als separatoren.
Als variabelen afgeteld zijn, kunnen we naar keuze een 0
teken schrijven of deze weglaten. Meerdere komma's ,..
vormen dus geen hoger dimensionale structuur.
Over de structuur van de eerste rij zal de functie snelheid
van Adam significant achterblijven bij die
van Conway's pijlketens en Bird's lineaire array.
Maar gezien de beperking van twee tekens
valt de expressieve kracht van Adam reuze mee.
Wat we "primitief" noemen aan deze recursie
is het herhaaldelijk optellen van de constante a
en het opschuiven van een subtotaal b over de rij
naar hogere iteraties ,0 rechts, wat "opladen" heet.
Dit vormt Adam's getal opbouw.
Beide regels tellen 1 af van een iterator
(of schrijven min - bij), rechts van de
in te vullen positie. Dit vormt Adam's expressie afbouw.
We herhalen de stap regels "recursief", waarbij
de uitkomst van een voorgaande reeks
het aantal volgende herhalingen bepaalt,
tot er uiteindelijk een natuurlijk getal n komt te staan
als een serie enen 1.. :n van dezelfde lengte.
Met Adam kunnen we supermacht expressies schrijven
met maar twee tekens en deze evalueren
door drie primitief recursieve regels toe te passen.
$ 3.1.2. Definitie 'A.I'
De evaluatie van expressies 'A.I' op de Adam rij
verloopt congruent aan die van de popster supermachten.
Maar Adam's algoritme telt in de lage variabelen
links op, terwijl de popster operaties op de top worden gestapeld
en rechts associatief uitgewerkt.
De rij structuur blijft bij Adam onveranderd,
terwijl onze popster trein expandeert en pulseert
(hoewel niet zo ongebreideld als in de gewone uitwerking
van supermacht operaties met hele grote reeksen).
Een uitgetelde structuur met alleen nog lege ,0 rechts
kan in Adam tot op het laatst blijven staan.
De regels voor
popsterren
wijken beduidend af van die voor Adam.
Een totaal andere verbeelding
van wat stap na stap hetzelfde recursieve patroon volgt;
zoals we nog zullen zien in sectie 3.2.
over Popster Adam hieronder.
Definitie van Adam's systeem 'A' over rij structuur 'I'
met een onbeperkt aantal variabelen.
Drie regels voor de selectie en evaluatie
van al deze supermacht expressies.
Variabele b≥0 en het aantal komma's ,{k≥0}
kan nul zijn en zonder teken. Ook de text variabele R
voor het deel rechts kan leeg zijn.
-A.I.1. a,b,1R = a,ab,R
-A.I.2. a,b1,,{k},1R = a,,1,{k}b,R
1= a,a,,{k}b,R
-A.I.3. a,b,{k} = b
Bij regels met = geven we de hele expressie weer.
Gedurende de evaluatie is steeds precies één
van de regels toepasbaar.
Regel '1.' telt de constante a op in som variabele b .
Regel '2.' verplaatst het som subtotaal uit b
om verder naar rechts een afgetelde iterator op te laden.
Daarbij laten we slim 1 achter in de eerste iteratie over c
die een a optelt in de volgende stap.
Regel '3.' neemt getal b als uitkomst
en daarmee stopt de evaluatie.
Merk op dat expressies van de vorm a,,,{k>0}1R
buiten deze regels voor systeem 'A' vallen
en derhalve niet reduceerbaar zijn.
We kunnen daar een oplossing voor geven
met de nu volgende Adam systeem varianten, waarmee
ook de lege structuren rechts eerder wegvallen.
$ 3.1.3. Variant 'Aa.I'
In de uitgebreidere definitie 'Aa.I' van Adam
worden resterende komma's van afgetelde variabelen
meteen vanaf rechts opgeruimd.
In plaats van een text variabele komt hier
het scan teken ` om de passieve tekst passage
aan de rechter kant te noteren.
Stel b≥0 voor het subtotaal.
Laat :k>0 een aantal afgetelde variabelen ,0
tussenin herhalen, wat we eerder met een
lege rij komma's ,{k} weergaven.
-Aa.I.0. a,`,0 = a,`
-Aa.I.1. a,b,c1` = a,ab,c`
-Aa.I.2a. a,b1.,0..,d1` :k>0
= a.,0..,b1,d` :k
-Aa.I.2b. a.,0..,d1` :k>0
= a,a.,0..d` :k
-Aa.I.3. a,b = b
De gesplitste regel verandert de evaluatie niet.
Na elkaar toepassen van regel '2a' en '2b' in systeem 'Aa'
werkt hetzelfde als opladen en optellen in Adam 'A'.
In systeem 'Aa' kiezen we om de expressie waarde
met b=0 onder c=0 gelijk te houden
aan die waar b=1 zou staan.
In het strikte systeem 'A' viel dat gewoon niet onder
de regels, maar hier kunnen we deze expressie vorm
gebruiken om de parallel lopende supermachten uit te drukken.
a*{c>0}b = a,{c1}b
Dan blijkt dat een type +{c>1} superoperator
die begint te tellen vanaf de plus,
gelijk staat aan het aantal komma's
of variabele plaatsen in Adam.
$ 3.1.4. Variant 'Ab.I'
Een ander type definitie benoemt alleen die
variabelen en tekens, die voor de selectie
en wijziging nodig zijn. We scannen expressies
steeds vanaf de linker kant a, naar rechts.
Test daarbij de 'l-r' scan regels `=
in de definitie van boven naar onder, tot er een match
voor de expressie vorm gevonden wordt.
Een spatie in een regel betekent het einde
van het linker gedeelte van de vorm,
waarna we apart doorzoeken naar een match
voor het rechter gedeelte.
Over de spatie slaat onze 'l-r' scan dus
een mogelijke passieve text passage over.
De definitie van systeem 'Ab.I' past de regels
strikt in volgorde toe. We ruimen komma's pas op
als alle iteratoren op rij zijn afgeteld.
Stel b≥0 vooraf.
-Ab.I.1. a,b,1 `= a,ab,
-Ab.I.2a. a,b1, ,1 `= a,,1 b,
-Ab.I.2b. a,,, 1 `= a,1,,
-Ab.I.3a. a,b, `= a,b
-Ab.I.3b. a,b = b
De speciale expressie a,,{k>1}2d
evalueert nu tot a,a,{k}d en telt dus
een iteratie stap meer af dan in systeem 'Aa'.
Dit lijkt rekenkundig juister.
Dan moeten we een expressie van de standaard supermachten
in 'Ab' met een basiswaarde b=1 schrijven.
Beginnend met de macht ** hier.
a*{c>1}b = a,1,{c}b
Dezelfde supermacht vergelijking geldt
in Adam's compacte systeem 'A'.
$ 3.2. Popster Adam
We vergelijken de evaluatie in functie 'A.I' met de
popster
operaties. Na wat rekenen ermee volgt
de algemene vorm van zulke vergelijkingen.
$ 3.2.1. Tetratie in rij van vijf
Expressies met drie tot vijf parameters
in systeem 'A.I' zijn equivalent aan de eerste popster
supermachten * tot *** en zo komen we tot tetratie.
In volgende voorbeelden tonen we Adam's
functie regel nummers links van het evaluatie teken
en bij popster operaties staan de toegepaste regels rechts.
Hoe optellen en vermenigvuldigen verloopt,
parallel in beide systemen.
a,b,1c = a*c1+b
1= a,ab,c =2,1 a*c+ab
1== a,a*c+b,1 == a*1+a{c}b
1= a,a*c1+b, =3,1 a{c1}b
3= a*c1+b
Evaluatie van een macht met vier parameters in Adam
en met popster operaties.
a,1,,2d = a**d2*+1
2= a,,1,1d =2,1 a**d1*+a*1
1= a,a,,1d =3 a**d1*+a
2= a,,a,d =2,1 a**d*+a*a
1== a,a*a,,d == a**d*+a^2
== a,a^d1,,1 == a**1*+a^d1
2= a,,a^d1, =3,1 a*a^d1
1== a,a^d2,, 3== a^d2
Zet nu popster operaties in in Adam's variabelen
om de evaluatie te volgen.
a,b,c,d == a,a*c+b,,d
= a,,a*c+b,d-
= a,a*+a*c+b,,d-
== a,a^d*+a*c+b,,
:= a,a^d1*c1 {b=a}
= a^d2 {c1=a}
De iterator e van tetratie domineert de kleinere
operaties. Zolang met name d
niet veel groter is dan a of triviaal klein,
tellen deze variabelen ongeveer twee etages e2
bij de toren met machten op.
a,b,c,d,e = a,a*c+b,,d,e
= a,a^d1*c1,,,e {b=a}
:= a,1,,a^d2,e- {c1=a}
= a,a^a^d2,,,e-
== a^^e1^+d2
= a^^e2 {d2=a}
Precies gesteld zo. Of stel dat {d~a}
dan rondt een rij van vijf in 'A.I' zo af.
$ 3.2.1. Supermachten over de rij
Met een aantal lege komma's ,{k} op de Adam rij
drukken we direct het aantal sterren *{k}
van een supermacht uit.
a,1,{k1}f2
= a,a,{k1}f1
= a,a,{k}a-,f
== a,a*{k}a,{k1}f
== a,a.*{k}a.. :f1
= a*{k1}f2
Elke voorliggende parameter in de functie rij
is een kleinere supermacht en vormt een popster operatie
op de hoogste exponent van de supermacht rechts.
Algemene vergelijking van expressies 'A.I'
met de reeks popsterren, beide in 'rep' notatie.
En afgerond tot supermacht, waar we de hele rij met
insignificante p~a optellen bij de hoogste operant.
a.,p_i.. 0:k
= a*{i}p_i*{i-}+..p_0 k:1
~ a*{k}(p_k+1)*{k-}+p_k-
~ a*{k}(p_k+2)
Bij kleine expressies k<2
of bij relatief grote superfactoren p_k-
zal de bijtelling van p_k+2 afwijken
in de superexponent.
Lastig aan systeem 'A.I' zijn de twee oplaadregels
in serie: met de substitutie van constante a
in de lege cel b na het opladen van hogere cellen.
Ook is het zuiniger om tekenreeksen ,{k>1}
in te zetten als separatoren in multidimensionale arrays.
Het volgende systeem Eva zal dit oplossen.
$ 3.3. Systeem Eva
Systeem 'E' voor "Eva"
noteert zo groot mogelijke getallen met zo
weinig mogelijk tekens en regels.
Typerend voor Eva is dat variabelen aftellen tot rest 1
en elke komma of andere separator dus apart blijft staan.
$ 3.3.1. Definitie 'E.I'
Eva's rij systeem 'E.I' opereert net als Adam
in het gebied van de supermachten.
Uitgedrukte getallen wijken bij gelijke expressies
iets af van Adam 'A.I' en lopen er op achter,
waarbij exacte vergelijking steeds ingewikkelder wordt.
Definitie van systeem 'E' op de eerste rij 'I'.
-E.I.1. a,b1.,1..,2R :k≥0
= a,1.,1..ab,1R :k
-E.I.2. a,b.,1.. = ab
Elke expressie is op te lossen met deze twee regels. ¶
Regel '1.' laadt de som ab uit de basis
op naar de beschikbare variabele.
Dat kan op plaats b zelf zijn,
of een iterator ,1 die rechts staat te wachten.
In geval k=0 ontbreekt de afgetelde reeks
en telt de kopie van a gewoon op bij b .
Een afgetelde reeks ,1.. wordt vanaf rechts
opnieuw opgeladen, waarbij variabele b rest 1 houdt,
die voor de vorm 0 meetelt bij a1 in de regel.
Het resultaat van het vervolg is == dat de andere
plaatsen ,1 met waarde a zijn gevuld,
als de eerste som a1 alweer in b staat.
a,b.1,..2R :k1
== a,1.a,..ab,2R :k
Regel '2.' geeft de uitkomst, mits er geen
iterator groter dan 1 rechts volgt.
Dit houdt in dat de eerste regel met prioriteit
wordt toegepast tot dat onmogelijk is.
Om afgetelde variabelen van rechts op te ruimen,
is er de extra regel '2a.' die we naar wens
eerder of later toepassen.
Regel '2b.' is simpeler dan regel '2.'
en met dit stel is regel volgorde niet nodig.
-E.I.2a. a,R,1 = a,R
-E.I.2b. a,b = ab
Eva telt haar iteraties nooit volledig af,
er blijft altijd een 1 na de komma over.
Het staat ons vrij een andere betekenis
aan reeksen komma's ,.. te geven.
We zullen deze als hogere separatoren gebruiken
en de ruimtes ertussen als dimensies,
wanneer we het Eva systeem
'E.II.'
uitbreiden.
Daarmee zijn dan record grote getallen te noteren,
gegeven de beperking van twee tekens.
$ 3.3.2. Rekenen in Eva
Optellen werkt zo A(a,b,1) = A(a,ab) = ab
in systeem Adam. Ondanks dezelfde input en output,
is de evaluatie volgorde in Eva toch anders.
E(a,b,1) 2= a,b
= a+b 2= ab
Ook is de variabele b>0 in Eva,
terwijl deze in Adam leeg kan zijn.
Vermenigvuldig in Eva door regel '1.'
te herhalen == over drie parameters.
a,b1,c1 1= a,ab1,c
== a,a*c+b1,1
2= a*c1+b1
Met een cijfer in b=0 kan a,0,c
in Eva a*c vermenigvuldigen.
De match in de regel vorm zou dan - een min zijn.
Of we moeten er tevreden mee zijn, dat Eva
andere getallen dan deze makkelijker uitdrukt.
Bij het aanhalen van dezelfde regel
of van een eerdere afleiding
geven we het teken = hier geen nummer.
a,b,c1,d2 1= a,a+b,c,d2
= a,a*c+b,1,d2
= a,1,a*c1+b,d1
= a,a*(a*c1+b-)+1,1,d1
= a,1,1+a*(a*c1+b),d
2== a,1,.1+a*(..a*c1+b..) :d:
2= a*(..a*c1+b..)+1 :d1:
~> a^d2*+c2 {b=a}
~> a^d3 {c1=a}
Vergelijk Eva met systeem Adam,
waar expressies A(a,b,c,d)
exact op popmacht a^d*+a*c+b uitkomen.
E(a,1,1,d1) = a,1,a1,d
= a,a1,a,d <~ a^d*+a2
< A(a,1,1,d1) = a^d1*+a1
<~ A(a,a1,a,d)
Dit scheelt ongeveer een factor. Het valt
te verwachten dat bij gelijke expressies
de superexponent in de uitwerking bij Eva
ongeveer 1 kleiner is als in systeem Adam.
Erger is dat dit systeem dat ab optelt
en rechts oplaadt, steeds verder uit de pas loopt
bij de natuurlijke supermachten van Adam
die rechts enkel b oplaadt.
Anders kunnen we het zo regelen dat Eva 1
iteratie minder substitueert in de parameter c
voor optellen, dan zijn de twee systemen parallel
aan elkaar. Haar algoritme zou dan complexer worden,
om zijn getallen simpeler te benaderen,
wat in ons verhaal een beetje onzinnig is.
$ 3.3.3. Eva is supermachtig
Verder met Eva systeem 'E.I' met de hogere cellen
op de rij, na E(a,a,a,d) dat ongeveer ~
tot a^d1 reduceert. ¶
Eva's rij van vijf drukt een rommelige tetratie uit.
a,b,c,d,e {b~a c~a}
~ a,a^d1,1,1,e
~ a,,1,a^d1,e-
~ a,a^a^d1,1,1,e-
~ a,a^^e^+d1
~ a^^e1 {d~a}
Eva stapelt herhaaldelijk een exponent minder
dan systeem Adam, waar dezelfde expressie
tot a^^e1^+d2 uitwerkt. ¶
Maar de minimale expressie met tetratie E(a,1,1,1,e)
in Eva is vrijwel gelijk aan de exacte tetratie A(a,1,0,0,e)
in Adam, iets groter zelfs.
a,1,1,1,e1 = a,1,1,a1,e
= a,a1,a,a,e
~ a^^e^+a1 ~ a^^e1
Expressies in Eva zijn niet exact te vertalen
naar popster supermachten. De complexiteit
van een dergelijke vergelijking neemt op
fractal-achtige wijze toe.
Deze supermachtachtige getallen zouden we
"supermachtig" kunnen noemen. ¶
De dichtstbijzijnde supermachten
voor onze supermachtige Eva expressies
zijn zo ongeveer ~ of als ongeveer groter ~>
wel te bepalen.
Druk systeem 'E.I' bij benadering uit als een reeks
popster supermachten, waar elke variabele meer op de rij
een operator ster bijtelt.
a.,1..,f1 :k = a,1.a,..f :k
~> a*{k}f*{k-}+a1
~> a*{k}f1
Of in het algemeen voor een rij met lengte k2
wat in Eva begint door af_0 op te tellen
met een lege *{0} ster.
a.,f_i.. 0:k
~ a*{k}(f_k+1)
De hoogste superexponent f_k is dominant;
alle voorgaande iteraties tellen daar in Eva
maar 1 stap bij op, tegen ongeveer 2 in Adam.
De positie ervan, dat is de rij lengte,
te tellen met het aantal supermacht sterren,
is het dominantst.
Van beide primitief recursieve functies 'A.I' en 'E.I'
loopt rij lengte ongeveer gelijk met de tweede iterator
van een dubbel recursieve functie. ¶
We gaan de eerste rij recursief verlengen,
lengte op lengte, om een hogere klasse
van grote getallen te noteren.
Door subtotaal b door te laden naar de tweede rij,
kunnen de variabelen daar gelijk op lopen
met die van Bird's lineaire array, die maximaal is.
Dit zullen we bewijzen met behulp van Conway's pijlketen,
die natuurlijk volgt op Knuth's supermacht pijlen.
$ 4. Pijlfuncties
We breiden de rechtse pijlen → van Conway uit
met de oppijlen ↑ van Knuth
in een nieuw systeem met →↑ superpijlen.
De hiermee te noteren getallen zullen zeker zo groot
worden als die van Bird's lineaire array.
$ 4.1. Knuth's oppijlen
Donald Knuth's pijloperaties stonden model
voor Conway's pijlketen notatie.
Gegeven de operator ↑ van machtsverheffen
schreef Knuth de volgende operatie
van tetratie ↑↑ met twee oppijlen.
Die evalueert hij direct tot een toren van machten,
van rechts op links verder uit te werken tot getal.
We reduceren tetratie in stappen
door links ervan machten in te voegen.
a↑↑b1 = a↑a↑↑b
== a↑..a↑↑1 :b
= a↑..a :b
Door deze vergelijking operatie ↑{c1} na operatie ↑{c}
te herhalen, kunnen de supermachten worden uitgedrukt
als een reeks voorgaande pijloperaties.
Er zijn drie regels nodig voor de evaluatie
vanaf rechts =` van Knuth's oppijlen.
In meerdere stappen == volgt dan de hele reeks.
-Kn.1. a↑{c}1 =` a
-Kn.2. a↑b1 =` a*a↑b
== a*..a :b
-Kn.3. a↑{c1}b1 =` a↑{c}a↑{c1}b
== a↑{c}..a :b
De operatie van tetratie wordt al gauw onbegrijpelijk
groot, en de meeste supermacht operaties kunnen
alleen algoritmisch nog worden vergeleken.
Neem een gelijk aantal oppijlen ↑_^[..]
of carets ^_^[..] bij dezelfde operatie,
maar voor supersterren *_^[..] een ster extra.
Het getal in dit voorbeeld
is fysiek niet decimaal weer te geven.
Ook niet als elk kleinste deeltje in ons heelal
een cijfer voor zou stellen.
Toch kunnen we er een beetje mee rekenen.
4^^4 = 4^4^256
= 2^2^513 ≈ 2^2^2^2^3.17
≈ 10^10^153.9
≈ 80.59^^3
≈ (79.8^^2)^^2
≈ 2.3279574277^^5
= 4^^^2
Net als alle pijloperaties
lossen Knuth's oppijlen ↑{c>0}
strikt =` rechts associatief op.
De gewone meerderheids-precedentie
passen we bij dakjes of carets ^{c>0} toe.
Daarna volgt evaluatie van supersterren *{c1>0}
met minoriteits-precedentie,
waar de operatie met minder sterren voorrang krijgt.
Dit brengt variatie aan in het gebruik
van supermacht operatoren.
Het lege optellen *{0}
gebeurt direct bij unaire getallen,
maar plus + optellen komt als laatste.
$ 4.2. Conway's pijlketen
Conway bedacht zijn pijlketen functie
om significant grotere getallen te maken
dan met Knuth's oppijlen mogelijk is.
$ 4.2.1. Definitie
De pijlketen notatie van de Engelse wiskundige John H. Conway
zag in 1996 het licht in zijn
Book of Numbers.
Aanknopingspunt vormt de pijlketen a→b→c
die met drie parameters dezelfde supermachten a↑{c}b
uitdrukt als Donald Knuth met al zijn pijlen.
Iteratie van de derde parameter →c
telt als het ware het aantal oppijlen ↑{c} af.
Verschil is dat de rechtse pijl →
geen operator is en hier niet telbaar,
maar net als de komma separator ,
een plaats aanduidt voor een functie parameter.
Met a,b,1 kan de dubbel recursieve functie
verschillend beginnen.
Hilbert
telt zijn φ_1(a,b) op. De
Ackermann
functie φ(a,b,1) vermenigvuldigt.
Beide opties komen in aanvang natuurlijk over.
De initiële rechtse pijl van a→b
waartoe a→b→1 reduceert, staat bij Conway
voor ↑{c=1} machtsverheffen.
Stapsgewijze definitie van Conway's pijlketen.
-Co.1. a→b = a↑b
-Co.2. X→1 = X
-Co.3. X→1→z = X
-Co.4. X→y1→z1 = X→(X→y→z1)→z
== X→(..X..)→z :y:
Hier stelt de text variabele X
het linker deel a.→n_i.. :k van de keten voor,
met een k≥0 aantal variabelen n_i
maar op zijn minst de constante a .
$ 4.2.1. Evaluatie
De systeem regels 'Co.' evalueren expressies
van Conway's pijlketen tot getal.
In de voorlaatste variabele y
vindt zowel substitutie plaats
als het aftellen binnenin,
terwijl de iterator z rechts buiten aftelt.
Bij herhaling == van hoofdregel '4.'
telt de geneste y af tot 1 om te besluiten
met de dubbele eliminatie van →1→z door regel '3.'
We werkten een hele - recursieve stap van z uit.
Reduceren we de overgebleven keten X
op zijn beurt, dan zal bij herhaling van
enkele recursies - en dubbele eliminaties
de verst geneste expressie met a
of via macht a→b een getal opleveren.
Dit geeft in de keten van drie of vier
de volgende recursie van z- over y .
Na de hele dubbele recursie
valt rechts een pijl →1 weg door regel '2.'
en reduceren die geneste ketens via machten
en supermachten a→b→(..a↑b..)
tot subtotaal getal.
Zo borrelen steeds grotere y op uit de diepte
naar steeds verder naar rechts wachtende expressies.
Tot ook de top expressie X→y→z
weer uit getallen bestaat.
Bij herhaling groeit het subtotaal in y
en reduceert z .
De geneste ketens rollen heen en weer,
omlaag en omhoog, tot ook de top keten X→y→1
aan lengte verliest. Elke nieuwe y
die dan z wordt, zal de eerdere z
ver in grootte overtreffen.
Tot uiteindelijk ook de laatste macht
evalueert tot getal.
Er zijn ook triviale ketens.
De eerste begint links met te kleine ≤2 getallen.
2→2→R = 2↑{r}2 = 4
L→1→R = L→1→r = L
En komt ergens een schakel →1 voor,
dan kan de keten →R
daar ter plekke worden afgekapt.
$ 4.2.3. Recreatie
Scherp de vergelijking aan uit het
getallenboek van Conway en Guy,
waarin een recursieve superexponent
het beroemde recordgetal van Graham uitdrukt.
Gardner's getal 3↑{..3↑{4}3..}3 :63:
van Graham ligt: boven de 3→3→64→2
is 3→3→(..3↑3..) :63: in pijlketen notatie
en onder de 2→3→65→2 is 2→3→(..2→4→7..) :63:
waar de diepe supermacht een prima benadering
is van 3→3→7 (zie § 2.2.3),
zodat de 64ste iteratie van oppijlen
aan beide kanten drie ↑↑↑ verschilt.
Conway voegde aan de keten a.→x_i..
de "dubbele recursie" →y→z1 toe,
met als evaluatie stap om op plaats y
de subexpressie met →z te substitueren,
in de hele enkele "recursie" tot diepte y genest.
Over de gehele ketenlengte :k van
(in de evaluatie afwisselend recursieve en)
dubbel recursieve variabelen v_i
noemen we zo'n functie "tripel recursief".
X→y1→2 "recursie"
= X→(X→y→2)
== X→(..X..) :y:
X→y1→z1 "dubbele recursie"
= X→(..X..)→z :y:
X.→v_i.. :k>2 "tripel recursie"
Het linker deel X van de expressie
wordt tegelijk met de recursie genest,
maar verandert zelf niet.
Het zou dus elk mogelijke tekst kunnen bevatten.
In Conway's pijlketen eindigt deel X
altijd op een variabele, en voor niet-triviale
recursie met een unair getal x>1
dat aftelbaar is. Maar deze recursies
kunnen net zo goed werken als X#y→z
eindigt op een oppijl of een hogere superpijl.
$ 4.2.4. Variatie
De eerste schakel in Conway's keten had ook
een oppijl a↑b kunnen zijn,
met daarbij deze alternatieve regel
voor de pijloperatie →c die erop volgt.
- a↑b→c1 = a↑↑b→c
== a↑↑{c}b→1 = a↑{c1}b
Dit geeft als resultaat exact dezelfde supermachten
als a→b→c1 en ook als a↑
met daarop een b→c1 dubbele recursie.
a↑y1→z1 = a↑(..a..)→z :y:
Ook de pijlketen a*b→c
die met vermenigvuldigen a*b begint,
kan evalueren tot a*{c}b
met een aangepaste regel voor de rechtse → pijl.
Waar deze na bijvoegen van een oppijl ↑
de equivalentie *↑ ≡ ** in dezelfde stap toepast.
Of waar deze elke ander kleiner (zoals * hier)
operator teken ervoor herhaalt.
Simpeler kan dit weer met de rechts associatieve
dubbele recursie.
a*y→z = a*(..1..)→z- :y:
= a*{z}y
Dit voor de fijnafstemming van de eerste supermacht
in een alternatieve pijlfunctie met drie parameters,
voor de rest maakt dit weinig uit.
We nemen nu een voorschot op het volgende hoofdstuk,
waar a→↑z tot een lange pijlketen
van Conway a→..1 :z evalueert.
Stel dat de rechtse pijl →c1
een aantal ↑{c} oppijlen zou toevoegen
aan elke andere voorstaande operator.
Als we de nieuwe superatoren dan 'r-l'
uitwerken zonder ze van elkaar af te schermen,
ontspringt er een onstopbare loop.
3→↑3→2 = 3→↑↑3 <
3→↑3→↑3 = 3→↑3→3→3
Die variatie voor de → volgpijl
is wel mogelijk, maar dan moet de evaluatie stap
van oppijlen haakjes erbij noteren.
De top van de toren wordt daarmee genest.
a→↑3→2 = a→↑↑3→1 = a→↑↑3
= a→↑(a→↑↑2) = a→↑(a→↑a)
= a→..1 :a→..1 :a
Dit zou een manier kunnen zijn
om de lengte van Conway's keten
met Conway's keten uit te drukken,
wat het volgende type recursie inluidt.
a→↑b1→2 = a→↑↑b1
= a→↑(a→↑↑b)
= a→↑(..a..) :b:
De oppijlen noterende volgpijl →
lijkt zeer snel van start te gaan.
Toch blijkt dit (door de bijkomstige haakjes)
precies hetzelfde uit te werken, als gewoon
de volgende rij recursies beginnen.
En we zetten graag de ketenvorming van a→↑b
op een hoger plan door,
door onze a→↑↑b1 via regel a→↑a→↑↑b
een tweede dimensie rij a→↑..a :b
te laten vormen.
Zonder nieuwe haakjes, in het vervolg,
dat groots wordt.
Eerdere verwarde pogingen om ketens met superpijlen te bouwen: ¶
1. EN -
Conway's row of chained arrows ¶
2. EN -
Arrows quarters (draft) ¶
3. EN -
Big Arrows Compass ¶
4. EN -
Growing Numbers in all Dimensions (draft) ¶
5. EN -
Big Arrows Compass I & II (draft) ¶
6. EN -
Conway's down arrows (draft) ¶
7. EN -
Birth of the Superdeep (arrays) ¶
8. NL -
Conway-Knuth hyper-recursieve pijlen
$ 4.3. Conway-Knuth superpijlketens
Om de volgende generatie grote getallen te maken
krijgt Conway's systeem een nieuwe regel,
met een variabele die de lengte
van de pijlketen bepaalt.
De drie typen recursies over deze variabele
komen gewoon rechts daarna te staan.
De regel telt de lengte variabele af
en voegt stapsgewijs schakels →a toe,
links van de superpijl aan de op te bouwen keten.
De operatie herhalende pijl van Knuth
werkt precies zo, dus *tada*, dit →↑
is onze nieuwe superpijl operator.
Vanaf rechts =` voegt de →↑
stap na stap een y aantal parameters a
toe. Niet gescheiden met haakjes
(wat tot tetratie leidt), maar als een pijlketen.
a→↑y1 =` a→a→↑y
== a→..a→↑1 :y
= a→..a :y
Als we hier een →2 op laten volgen,
wordt de ketenlengte recursief uitgedrukt.
3→↑3→2 = 3→↑(3→↑2→2)
= 3→↑(3→↑3)
= 3→↑(3→3→↑2)
= 3→↑(3→3→3)
= 3→↑3↑↑↑3
p = 3→..1 :3^^7625597484986
En die recursie over de ketenlengte
gaat al gauw pijlketens diep.
3→↑3→3 = 3→↑(3→↑2→3)→2
= 3→↑(3→↑3→2)→2
= 3→↑p→2
= 3→↑(..1..) :p:
Dubbele recursie over de lengte van Conway's keten
opent een nieuwe generatie van grote getallen.
a→↑y1→z1 = a→↑(a→↑y→z1)→z
== a→↑(..a..)→z :y:
Nog "sneller" wordt de functie met meerdere superpijlen,
maar evaluatie van de expressie duurt onvoorstelbaar lang.
3→↑↑↑2 = 3→↑↑3 = 3→↑3→↑3
= 3→↑3→3→3
= 3→↑3→(3→↑3→2→3)→2
= 3→↑3→(3→↑3→(3→3→3)→2)→2
= 3→↑3→(3→↑3→3^^^3→2)→2
Om de supermacht 3^^^3 staan geen haakjes,
want de carets operatie heeft precedentie.
Maar pas op met oppijlen in deze rechts associatieve context.
Formule voor superatoren bestaande uit een
Conway pijl met Knuth's oppijlen.
a→↑{c1}b1 = a→↑{c}a→↑{c1}b
= a→↑{c}..a :b
Daarboven volgt dan recursie over het aantal
Knuth pijlen in de superator.
3→→3→→2→2 = 3→→3→→(3→→3)
= 3→→3→→(3→↑3)
= 3→→3→→3↑↑↑3
= 3→↑3→→3↑↑↑3
= 3→↑↑3→→(3↑↑↑3)-
= 3→↑{3^^^3}3→→1
= 3→↑{3^^^3}3
Later tonen we hoe groot de getallen
van deze rechts gestapelde recursies zijn,
vergeleken met Bird's links oplaadbare arrays.
Onze definitieve definitie
van de Conway-Knuth superpijlketens.
-CK.0. y↑z1 =` y*y↑z
== y*..y :z
-CK.1. y#↑z1 =` y#y#↑z
== y#..y :z
-CK.2a. a→b = a↑b
-CK.2b. a#→b = a#↑b
-CK.3. X#1 = X
-CK.4. X#1→z = X
-CK.5. X#y1→z1 = X#(X#y→z1)→z
== X#(..X..)→z :y:
-CK.6. ↑y#→z1 =` ↑↑y#→z
-CK.7. →y#→z =` ↑y#→z
== ↑{z}y
Hier is # een superator met elke mogelijke,
maar niet-lege combinatie van pijlen.
Teken X staat voor een deelketen
met op het eind een variabele.
Regels met = gelden voor de hele expressie.
Regels met =` zijn rechts associatief,
toe te passen op het laatste deel van de expressie.
Daarbij is variabele y compleet,
want elke variabele in de scan is gretig naar enen.
Regels '6.' en '7.'
offeren twee hogere pijlen →→y→→z
op om de superator in →↑{z}y
stapsgewijs te kwantificeren.
Zo kan het aantal oppijlen recursief worden bepaald,
rechts na de variabele z met de eerdere regels,
terwijl de expressie reduceerbaar blijft.
Reeksen van hoge pijlen zijn meest lang,
dus het verlies van 1 schakel is insignificant.
In ons systeem hebben alle superatoren →{m}↑{n}
hun rol in de constructie van getallen,
waarbij elke superoperator een keten van
vorige superator schakels achterlaat.
Hoe groot die rol eigenlijk is
zal moeten blijken uit onze vergelijking
met de arrays van Bird in het volgende hoofdstuk.
Een afwisselende reeks operator tekens →{m_i}↑{n_i}..
zou extra informatie aan het systeem kunnen toevoegen.
Hoewel dit een multidimensionale matrix mogelijk maakt,
laten we deze uitbreiding ongebruikt.
Rechts assocatieve evaluatie van regel '7.' telt
in ↑→y→→z is ↑↑y→→z
de vreemde voorliggende oppijlen op.
Het aantal superketenpijlen →{m}
is sowieso dominant.
Om die met een recursieve variabele te kunnen herhalen,
is er een nieuw pijlteken ↓ nodig.
$ 5. Lineaire arrays
Lineaire arrays zijn functies
bestaande uit een rij parameters,
met de constante a gevolgd door
een aantal recursieve variabelen ,b,c,d,e,.. ¶
Door subexpressie substitutie in b
en het daarmee opladen van afgetelde variabelen,
noteert Bird's lineaire array
maximaal grote getallen over de rij.
$ 5.1. Birdy rij
De Engelse wiskundige Christopher Bird publiceerde
een systeem met arrays voor het maken van
wereldrecord grote getallen.
De regels voor de evaluatie van Bird's arrays
worden bij uitbreiding steeds ingewikkelder,
maar we zullen een bij benadering gelijk systeem
"Birdy" van het begin af eenvoudiger opzetten.
Ga uit van de
lineaire array notatie
van Chris Bird, de eerste rij. ¶
De Birdy functie verwijdert uit Bird's Rule 4.
de overbodige substituties, die aan de grootte
van de uitkomst weinig bijdragen.
Onze versimpelde regel komt in het spel
bij de vierde parameter,
na basis paar en supermacht trio.
$ 5.1.1. Basis paar
We bouwen een systeem van regels 'B.I'
over de eerste rij parameters,
dat met licht aangepaste expressies
even grote getallen noteert als Bird's lineaire array.
Sommige regels 'B.' blijven ook in onze
latere Birdy array systemen geldig.
In de array basis werken twee eliminatie regels:
om de uitkomst op te leveren
en die om een afgetelde variabele
aan het uiteinde rechts te verwijderen. ¶
De term X links bevat hier de rij a.,p_i..
met een aantal :k≥0 iteraties.
-B.0. B(a) = a1 "successor"
-B.1. B(X,1) = B(X) "afval"
Rechtstreeks Bird(a) = a is prima,
maar de successor functie past bij optellen,
zoals Hilbert ook begon.
De voorsprong 1 is natuurlijk insignificant. ¶
Nu reduceert B(a,1) via B(a)
tot uitkomst a1 wat fraai optelt.
Regel '1.' voor afgetelde uiteindes ,1 is
geldig bij elk type array met een laatste rij deel.
Maar het principe om laatste enen in de expressie
op te ruimen blijft van kracht bij uitgebreide
separatoren ,[X]1 in hogere arrays. ¶
We zien liever af van Bird's apparaat
om leeggetelde variabelen of structuren op te lossen
in de voorliggende rijen of array ruimtes.
Bird neemt, in navolging van Conway's pijlketen,
als basis operatie B(a,b) het machtsverheffen.
Dit vooronderstelt een stap van vermenigvuldigen
die herhaald tot de reeks a*..1 :b evalueert.
Bird(a,b1) = a*(a,b)
== a*..(a,1) :b
= a^b*(a)
= a^b*a
= a^b1 "macht"
Bij David Hilbert en ook bij Jonathan Bowers,
die oorspronkelijk het idee voor de arrays van Bird ontwikkelde,
begint de functie primitief door a+b op te tellen. ¶
Het Birdy systeem telt basis paar a,b op
door enen stapsgewijs over te brengen van b naar a ,
wat ons tellen wezenlijk is.
-B.2. B(a,b1) = B(a1,b) "tellen"
== B(a.1..,1) :b
= B(ab) = ab1
Of tel in een keer op, door de komma te elimineren
en de uitkomst uit de functie te tillen.
Dan zou regel '0.' van de successor
uitkomst overbodig worden.
Beginnen met optellen kost ons Birdy systeem
twee supermachten ** ten opzichte van Bird's *{c1}
in input expressies met drie a,b,c parameters.
$ 5.1.2. Supermacht trio
De algoritmische motor van Bird's lineaire array
is de regel voor de recursieve functie stap.
Deze telt de derde parameter c af
en substitueert de tweede parameter b
voor een subexpressie die zelf vrijwel minimaal b-
is afgeteld. Aftellen van b tot 1
betreft de recursie van de functie,
en aftellen van c tot 1
heet de "dubbele recursie". ¶
Drie parameters drukken bij Bird
exact de supermachten a^{c}b uit,
maar onze Birdy benadering ervan begint
met optellen a,b,1
zodat we moeten bijtellen met c2
om dezelfde uitkomst te krijgen.
Als de recursie bodem bij b=1 is bereikt,
reduceert de subexpressie tot de constante a ,
mits daar een derde parameter c>1
op volgt in de eerste rij.
-B.I.3. B(a,1,2X) = a "bodem"
Tekst variabele X omvat hier de rij rechts
met een of meer variabelen.
Bij uitbreiding van arrays staat X
voor elke mogelijke verdere expressie.
Zo evalueert B(a,2,c1) tot B(a,a,c)
gebaseerd op deze regel.
Daarbij is c>0 vanwege regel '1.'
waarmee rechts de ,1 zou afvallen.
Zonder dat we precedentie van eerdere regels
als voorwaarde hoeven stellen. ¶
Expressies met b=1 waar deze regel met 2X
geen match voor vormt, zoals a,1,1,2 bijvoorbeeld,
komen in de evaluatietrein van systeem 'B.' niet voor
en hebben als grote getallen input geen zin,
maar zullen onder regel '5.' vallen.
- - - - - - - - - - - - - - -
De regel voor substitutie, de functie recursie stap,
is de werkmotor om getallen groot te maken op de eerste rij,
en essentieel voor snel startende arrays.
In Bird's lineaire array is dit Rule 5.
en in ons afgeleide Birdy systeem regel '4.'
-B.4. B(a,b1,2X) "substitutie"
= B(a,(a,b,2X),1X)
Deze regel waar b>0 kan steeds weer worden toegepast,
zolang c aftelbaar is.
Hier begint de tekst variabele X≥0
met de rest 1.. van het getal c≥0
en daarna geen of meer variabelen rechts.
Maar het kan ook een ander hoger array deel bevatten,
of is mogelijk leeg. ¶
We laten het functie voorschrift, de letter B
bij dit Birdy systeem, vaker weg
als dat duidelijk genoeg is.
Het trio, de rij met drie parameters,
geeft aldus de supermachten.
De recursie nest in 1 stap
van c>0 een reeks van b subexpressies
tot de constante a op de bodem.
B(a,b1,c1) = B(a,(a,b,c1),c)
== B(a,..(a,1,c1)..,c) :b:
= B(a,..a..,c) :b:
Na optellen B(a,b) vermenigvuldigen B(a,b,2)
en machtsverheffen B(a,b,3) drukt het trio B(a,b,c2)
exact de getallen uit van de a^{c}b supermachten. ¶
Het is de bedoeling dat grote getallen in systeem Birdy
ongeveer parallel blijven lopen met die van Bird's arrays,
waarbij expressies met c2 in Birdy
altijd gelijk zijn aan of anders insignificant groter zijn
dan die van Bird, nooit kleiner.
$ 5.1.3. Eerste rij
Gegeven een aftelbare expressie (a,1Z)
in de evaluatie van Bird type array functies,
dan krijgt in de volgende stap de subexpressie
de vorm (a,Z) die we afkorten
met een dollar $ teken.
Bird substitueert de $ subexpressie ook in de
afgetelde array variabele rechts met zijn Rule 4.
voor het opladen van hogere iteraties.
Bird(a,b1.,1..1R) :k>1
= Bird(.a,..$,1R) :k
De kleinere lengte van k=1 is een apart geval,
dat voor de eerste rij de substitutie Rule 5.
van Bird of onze Birdy regel '4.' zou weergeven.
We maken onze oplaadregel op de rij simpeler
en verplaatsen het subtotaal uit b
naar de links laatste afgetelde 1 .
De afgetelde variabelen ertussen blijven ongemoeid.
En we zetten voor cel b de waarde a1 in de plaats.
Oplaadregel voor afgetelde variabelen
op de eerste rij. Stel daarbij k≥0
zodat c=1 de eerste oplaadbare variabele is
(klopt met de komma's).
-B.I.5. B(a,b.1,..2X) :k2 "opladen"
= B(a,a.1,..b1,1X) :k1
Herhaalde toepassing == van deze regel
vult de hele afgetelde rij deel.
== B(a,a1,1.a,..b,1X) :k
= B(a,$,.a,..b,1X) :k
Het resultaat is net als bij Bird,
dat alle voorliggende variabelen 1 door a
zijn vervangen. Hier gebeurt dat druppelsgewijs,
tot cel c een tweede waarde a1 krijgt,
die aftelt met een substitutie stap.
Er geldt b>0 bij deze herhaling.
Dezelfde regel kan ook eerst het subtotaal uit b
verschuiven en pas daarna de lege cel b=1
met een a kopie aanvullen. ¶
Dubbele definitie van opladen,
met k>0 en alleen b>1
wordt verschoven.
-B.I.5a. B(a,1.,1..1Y) :k1 "vul"
= B(a,a1.,1..Y) :k1
-B.I.5b. B(a,b.,1..1X) :k1 "schuif"
= B(a,1.,1..b,1X) :k>0
Er blijft altijd een cijfer 1
in een lege cel achter.
De evaluatiestap als b=1 en c=1
is bij regel '5a.' en '5.' gelijk.
Varianten op onze oplaadregels zijn mogelijk,
bijvoorbeeld door a in te vullen.
De mogelijke afleiding uit primitievere regels
is wiskundig fraai.
$ 5.2. Vergelijk op de rij
Zet de grootte van getallen uit verschillende
notatie systemen tegen elkaar af,
door hun expressies bij benadering gelijk te maken.
We beperken ons in dit hoofdstuk
tot de eerste rij parameters. ¶
Van Bird is bekend hoe zijn array
met vier parameters even grote getallen uitdrukt
als Conway over de hele pijlketen lengte.
$ 5.2.1. Bird tegen Birdy
Vergelijk expressies van Bird's lineaire array
met die in ons Birdy systeem 'B.'
Bewijs dat ondanks de afwijkende regels,
de uitkomsten over de hele rij genomen
niet significant van elkaar verschillen.
Birdy begint met optellen B(a,b,1)
en ligt twee supermachten achter.
Bird(a,b,c) = a*{c1}b
= B(a,b,c2)
In het vervolg stellen we Bird's arrays
"minimaal groter" -> of "minimaal kleiner" <-
dan expressies in Birdy.
Rechts in de vergelijking met ->
heeft de Birdy expressie minimaal kleinere waarden
en na <- minimaal grotere waarden.
Dit verschil zit in de eerste parameter a
in de input expressies.
Bird(a,b1,1,2)
= Bird(a,a,(a,b,1,2))
== Bird(a,a,..a..) :b:
-> B(a1,b1,2,2)
= (a1,(a1,b,2,2),1,2)
:= (a1,a2,(a1,b,2,2))
== (a1,a2,..a1..) :b:
Hier is bij Bird de substitutie na = volgens de regels,
terwijl bij Birdy met := de subexpressie wordt opgeladen
nog voor deze tot subtotaal is uitgewerkt.
Na een b aantal substituties op dezelfde plaats,
bepaalt de laatste subexpressie de vergelijking.
Bird(a,b1,2,2)
= (a,(a,b,2,2),1,2)
== (a,..a..,1,2) :b:
-> B(a,b1,3,2)
= (a,(a,a,2,2),2,2)
== (a,..a..,2,2) :b:
Hier is de "minimaal groter" vergelijking precieser,
omdat de laatste subexpressie Bird(a,a,1,2)
meer verschilt met B(a1,a1,2,2) in Birdy,
vanwege de extra substitutie stap die er zou volgen.
In deze expressies met d1>2
compenseren we het andere opladen al minder.
Bird(a,b1,1,d1)
== (a,a,..a..,d) :b:
<- B(a1,b1,2,d1)
:= (a1,a2,(a1,b,2,d1),d)
== (a1,a2,..a1..,d) :b:
Blijf in de rij van vier parameters 1
bij c tellen voor iets kleinere Birdy.
Bird(a,b1,c1,d)
== (a,..a..,c,d) :b:
-> B(a,b1,c2,d)
== (a,..a..,c1,d) :b:
Bij het opladen naar vierde parameter d
wordt Birdy minimaal groter door 1
bij de derde c te tellen, omdat a1
zowel de nieuwe b als de nieuwe c vult.
Bird(a,b1,1,1,e1)
== (a,a,a,..a..,e) :b:
<- B(a,b1,2,1,e1)
:= (a,a1,a1,(a,b,2,e1),e)
== (a,a1,a1,..a..,e) :b:
Maar voor opladen naar de derde parameter
blijft 1 extra bij a nodig.
Bird(a,b1,1,d1,e)
== (a,a,..a..,d,e) :b:
<- B(a1,b1,2,d1,e)
:== (a1,a2,..a1..,d,e) :b:
Dit is voor vergelijkbare rijen
vanaf de vijfde parameter algemeen geldig.
Bird(a,b,c,d,R) <~ B(a1,b,c1,d,R)
Zo zijn alle expressies over de rij
ongeveer minimaal kleiner of
"bijna zo groot" <~ in Bird als in Birdy.
Het subexpressie opladende systeem van Bird
en het simpele getal opladende Birdy systeem
zijn daarmee vergeleken.
- - - - - - - - - - - - - - - -
Zowel Bird als ons Birdy systeem drukken,
gegeven een rij parameters waar
functie substitutie is toegestaan,
maximaal grote getallen uit.
Daarvoor is, na de snelle start door substitutie in b ,
vooral het opladen van subtotalen uit b
naar de hoogst afgetelde iteraties essentieel.
Of die opgeladen b ook verpakt is
in een subexpressie $ zoals bij Bird,
is van ondergeschikt belang.
Tel 1 extra bij derde parameter c in Birdy,
dan geeft dat een substitutie $ stap extra,
die het verschil bij het opladen naar de derde
parameter al bijna compenseert
en het opladen verder in de rij voldoende.
Als we het ruim nemen, geldt over de hele rij
van Birdy versus Bird dezelfde vergelijking,
waar ~ ongeveer gelijk betekent
en <≈ "iets kleiner of gelijk".
B(a,b,1R) ~ Bird(a,b,R)
<≈ B(a,b,2R)
De systemen lopen door c+2 in Birdy gelijk
bij de supermachten, maar daarna maakt dit Birdy
een recursie van b groter. Het verschil
blijft beperkt en wordt insignificant zodra
de hogere recursies vanaf d de rij domineren.
We kunnen andere systemen voor grote getallen
nu met de Birdy regels 'B.I.' vergelijken, wat handig is,
omdat die met Bird daarmee gegeven is.
$ 5.2.2. Conway tegen Birdy
Conway's pijlketen en Bird's lineaire array
zijn notaties voor getallen die zo groot zijn,
dat ze zelfs in de wiskunde vooralsnog
geen ander doel dienen dan uit te drukken
hoe groot wel niet, en zich met elkaar te meten.
We doen het
bewijs van Bird,
waar hij in vier parameters Conway's hele keten uitdrukt,
dunnetjes over met de vergelijkbare Birdy array.
Eerst noemen we nog de overeenkomsten
en verschillen van beide algoritmes
over de rij structuur.
Elke recursie stap telt een kopie van de expressie af
en substitueert deze op de plek van de afgetelde variabele.
Bij Conway gebeurt dat in de terugwijkende
variabelen y rechts, bij Bird steeds
in dezelfde variabele b links. ¶
De geneste reeks subexpressies ziet er
na een recursie zo uit.
Letters L en R staan voor de rest,
hetzij links of rechts in de keten of rij.
L→y1→z1 = L→(L→y→z1)→z
== L→(..L..)→z :y:
B(a,b1,1R) = (a,(a,b,1R),R)
== (a,..a..,R) :b:
Op de bodem reduceert Conway
met regel L→1→z = L zijn pijlketen naar links.
Maar bij Bird komt elke subexpressie recursie
uit op de constante a die klein is. ¶
In de expressie telt de dubbele recursie af
en het subtotaal in b hetzij y groeit.
Conway elimineert het einde →1→z van de keten.
Terwijl in de Birdy expressie B(a,b,1,R)
het subtotaal uit b naar rechts schuift,
uiteindelijk ook naar een hoge y=1 variabele. ¶
Elke dubbele recursie →y→1
valt na aftellen bij Conway rechts af,
maar vergelijkbare dubbele recursies worden bij c=1
in Bird of Birdy steeds opnieuw opgeladen.
We zullen zien dat dit het grote verschil
tussen de systemen maakt.
- - - - - - - - - - - - - - - -
Birdy begint B(a,b,1) = (a,b) = ab met optellen.
Conway's pijlketen springt net als Bird
snel uit de startblokken met a^b machtsverheffen. ¶
In deze systemen werkt elke stap van de dubbele recursie
over c hetzelfde, namelijk als reeks
subexpressie substituties in b .
Met drie parameters loopt systeem 'B.'
van Birdy steeds 2 van die recursies achter.
a→b→1 = a→b = a↑b = B(a,b,3)
B(a,b,c) = a→b→c2
Vergelijk de vierde parameter
in Conway's pijlketen met Birdy. ¶
Eerst met recursie over de supermacht teller.
a→a→b1→2 = a→a→(a→a→b→2)
== a→a→(..a↑a..) :b:
-> B(a,b1,2,2)
= (a,(a,b,2,2),1,2)
:= (a,a1,(a,b,2,2))
== (a,a1,..a..) :b:
Hou Conway's pijlketen -> minimaal groter,
zodanig dat de Birdy expressie meer groter zou worden
door 1 stap bij recursie parameter b op te tellen. ¶
Hoewel algoritmisch "minimaal"
zijn de verschillen hierbij natuurlijk enorm.
B(a,2,3,2) = (a,a,2,2) <-
a→a→2→3 = a→a→a↑a→2 <-
B(a^a,2,3,2) <- B(a,3,3,2)
De tweede recursie over de supermacht teller,
met het verschil op de bodem.
a→a→b1→3 = a→a→(a→a→b→3)→2
== a→a→(..a↑a..)→2 :b:
-> B(a,b1,3,2) = (a,(a,b,3,2),2,2)
== (a,..a..,2,2) :b:
Zo gaat de hele dubbele recursie over de supermacht teller.
a→a→b1→c1
== a→a→(..a↑a..)→c :b:
-> B(a,b1,c1,2)
== (a,..a..,c,2) :b:
De vierde schakel in Conway's keten komt dus overeen
met de derde parameter onder d=2 in Birdy.
- - - - - - - - - - - - - - - -
Conway's vijfde schakel begint
weer met recursie over de vorige.
a→a→a→b1→2
== a→a→a→(..a↑{a}a..) :b:
-> B(a,b1,2,3)
:= (a,a1,(a,b,2,3),2)
== (a,a1,..a..,2) :b:
Net zo werkt de volgende dubbele recursie uit.
a→a→a→b1→c1
== a→a→a→(..a↑{a}a..)→c :b:
-> B(a,b1,c1,3)
== (a,..a..,c,3) :b:
De vijfde pijlketen parameter past precies
onder d=3 in Birdy.
We zetten dit voort over de hele keten.
Vanaf de eerste recursie
over de vorige dubbel recursieve variabele,
die wordt opgeladen in Birdy,
wat een stap van d aftelt.
Conway's keten L op de bodem
tegen a in Birdy maakt het verschil.
L→b1→2 & L = a→..a :d
== L→(..L..) :b:
-> B(a,b1,2,d1)
== (a,a1,..a..,d) :b:
Schakels a→ kunnen ook verschillende waarden hebben,
als deze "normaal" zijn
(niet al te groot of triviaal klein)
blijft de pijlketen minimaal groter.
Steeds drukt de nieuwe variabele rechts
in Conway's keten een hogere dubbele recursie uit.
Terwijl Birdy onder de derde parameter c
de subexpressies nest en de vierde parameter d
de lengte van de pijlketen aangeeft.
L→b1→c1 & L = a→..a :d
== L→(..L..)→c :b:
-> B(a,b1,c1,d1)
== (a,..a..,c,d1) :b:
Getallen die Birdy 's rij met vier parameters uitdrukt,
zijn ongeveer zo groot als die met
Conway's hele pijlketen. ¶
Beiden substitueren afgetelde subexpressies,
de algoritmes verschillen omdat Birdy subtotalen
uit b oplaadt naar c=1 onder aftellen van d .
Waarna c de volgende en grotere
dubbele recursie oplevert.
Op twee manieren vindt er hier een herhaling
van dubbele recursies plaats: over de van rechts
af te wikkelen rij in Conway's pijlketen,
en met de steeds opnieuw met subtotaal b
op te laden dubbel recursieve variabele c in Birdy. ¶
Dit hogere type recursie noemen we "tripel recursie".
$ 5.3. Superpijlen tegen Birdy
Vergelijk de Conway-Knuth superpijlketens,
die we definieerden in hoofdstuk $.4.3,
met onze simpele Birdy versie
van de array notatie van Bird.
$ 5.3.1. Tweede pijlketen bij e=2
Breng de tweede pijlketen bovenop de lengte
van Conway's keten aan.
In Birdy onder vijfde parameter e=2
valt ook die tweede rij samen met variabele d .
Begin met het opladen van de lengte variabele
voor Conway's pijlketen met het subtotaal
uit b in Birdy. Dat kan enorm worden!
a1→↑b2 ->
a→..a1→a1 :b ->
B(a,b1,1,1,2) = (a,a1,a1,b)
-> a→..a1 :b1
-> a→↑b2 = a→..a :b1
Eerste recursie over pijlketen lengte,
of in Birdy's variabele b en voortijdig :=
opgeladen naar de vierde parameter
met een - aftel.
B(a,b1,2,1,2)
:= (a,a1,a1,..a..-) :b:
-> a→↑b1→2
= a→↑(..a..) :b:
Verdere stappen van c
in de dubbele recursie over pijlketen lengte.
B(a,b1,c1,1,2)
= (a,..a..,c,1,2) :b:
-> a→↑b1→c1
= a→↑(..a..)→c :b:
Volgt het opladen van de dubbele recursie in Birdy c
voor de tweede pijlketen.
B(a,b,1,2,2) = (a,a1,b,1,2)
-> a→↑a1→b
In de verdere recursies krijgt elke superpijlketen
een grotere subexpressie op de bodem dan de a bij Birdy. ¶
Nu is dit Conway's
super-Ackermann keten
met een a aantal parameters a ,
die de vergelijking bepaalt die hier
met <- van richting wisselt.
B(a,b1,2,2,2)
:= (a,a1,..a..,1,2) :b:
<- a→↑a→b1→2
= a→↑a→(..a→↑a..) :b:
De tweede dubbele recursie in de tweede pijlketen,
die door Birdy gewoon vanaf links in c wordt geteld.
B(a,b,c,2,2) <- a→↑a→b→c
De tweede pijlketen is in zijn geheel tripel recursief
over de tripel recursieve pijlketen van Conway.
Birdy gebruikt hier weer de vierde variabele d voor.
B(a,b,c,d1,2) <- a→↑.a→..b→c :d
Hierbij is d>0 omdat anders Birdy ->
minimaal groter uitkomt; zie hierboven.
En ook c>1 want in geval c=1
is de vergelijking anders na opladen.
B(a,b,1,d1,2) = (a,a1,b,d,2)
-> a→↑.a→..b :d
Dat een enkele stap in e
een tripel recursie hoger springt,
toont de kracht van Bird's lineaire array
voor het maken van grote getallen.
$ 5.3.2. Pijlketens onder e
Voeg hierna de volgende pijlketen rijen toe,
wat op details in de vergelijking na hetzelfde werkt.
Rij op rij vormt zich zo een pijlketen vlak.
Begin weer met opladen naar d in Birdy,
nu voor de tweede pijlketen lengte.
B(a,b1,1,1,3) = (a,a1,a1,b,2)
-> a→↑.a→..a1 :b
-> a→↑a→↑b1
In de eerstvolgende recursie blijft de bodem a
van Birdy meteen achter bij de bodem subexpressie
voor de pijlketen lengte.
Dat we het verschil tussen beide expressies
aangeven als minimaal kleiner <- komt,
omdat Birdy met 1 extra recursie stap in b
consequent meer verschil biedt.
B(a,b1,2,1,3)
= (a,..a..,1,1,3) :b:
<- a→↑a→↑b1→2
= a→↑a→↑(..a→↑a..) :b:
<- (a,b2,2,1,3) =
B(a,..a→↑a→↑a..,1,1,3) :b:
De rest van de vergelijkingen onder Birdy's e
verlopen op dezelfde wijze. De subexpressie op de bodem
van gelijke recursies blijft kleiner in Birdy.
Voor de verdere op voorgaande rijlengte
gestapelde pijlketens geldt algemeen.
B(a,b,c,d1,e1) <-
a→↑..a→..b→c :e :d
Met een uitzondering bij opladen naar c of d
in de richting van de vergelijking.
B(a,b,1,d1,e1) = (a,a1,b,d,e1)
-> a→↑..a→..b :e :d
B(a,b1,1,1,e2) = (a,a1,a1,b,e1)
-> a→↑..a→..a1 :e :b
-> a→↑..b1 :e1
De vaststelling of expressies
minimaal kleiner of groter zijn,
is niet significant op deze schaal.
Zelfs de waarde van de recursie teller b
in de input expressie doet er niet veel meer toe.
Waar Bird's vijfde variabele e
een aantal tripel recursies stapelt
over de lengte van de pijlketen rij,
vormt dat een groot recursief vlak van pijlen.
Een vierde type recursie
in een tweede pijlketen array dimensie!
$ 5.3.3. In de pijlkubus met f
Als separator operator tussen de pijlketen rijen
gebruikten we de eerste →↑ Conway-Knuth superpijl.
De volgende "superator" tussen de pijlvlakken
is de tweede superpijl →↑↑ en de variabele erna
bepaalt in de evaluatie het aantal rijen in het vlak ervoor.
In Birdy vertaalt dit naar het opladen
van de vijfde parameter e
met subtotaal b over constante a .
B(a,b2,1,1,1,2) = (a,a1,a1,a,b1)
-> a→↑..a→..a1 :b :a
-> a→↑..a1 :b1
-> a→↑↑b2
In de opbouw van de vergelijking tussen Birdy
en Conway-Knuth superpijlen volgt nu het recursief
uitdrukken van dit aantal pijlketen rijen met c=1
en verder als stap van c in een dubbele recursie.
B(a,b1,c1,1,1,2)
= (a,..a..,c,1,1,2) :b:
-> a→↑↑b1→c1
= a→↑↑(..a..)→c :b:
We stapelen weer allerlei recursies bovenop
deze superpijl variabele, zodat het aantal rijen
in het eerste vlak en het zo uitgedrukte getal
almaar toeneemt. ¶
Parallel in Birdy bouwen we de hogere recursie
variabelen d,e opnieuw op, apart gesteld
onder f=2 van het tweede pijlketen vlak.
B(a,b,c,d1,e1,2) <->
a→↑↑.a→↑..a→..b→c :e :d
Het teken <-> geeft aan
dat de vergelijking soms minimaal groter
en soms minimaal kleiner uitpakt.
Zoals we dat bij het eerste vlak aangaven,
waar ook al bleek dat dit verschil
op schaal insignificant is.
Voor elk volgend superpijl vlak
in de recursieve ruimte onder Birdy f geldt dit,
zodat we de sprong naar de derde superpijl dimensie
al precies kunnen maken.
B(a,b2,1,1,1,1,2) = (a,a1,a1,a,a,b1)
-> a→↑↑..a→↑..a→..a1 :b :a- :a
-> a→↑↑..a→↑..a1 :b :a
-> a→↑↑..a1 :b1
-> a→↑↑↑b2
Wat het volgende en vijfde type recursie inhoudt
over aantallen pijlketen vlakken
over aantallen van pijlketens,
onder de zevende parameter in Birdy
over f over e of net zo in Bird.
$ 5.3.4. Pijldimensies over Birdy's rij
Elke volgende variabele in de lineaire array van Bird
definieert weer een hoger type recursie, omdat het
een reeks van het voorgaande type recursief herhaalt.
Bij Conway-Knuth superpijlketens is dit duidelijker te zien,
omdat diezelfde recursies rechts zijn gestapeld.
We kunnen zo een pijldimensie k1
compleet uitrollen met een reeks van k2
type recursies en kleiner,
in Birdy en Bird met k4 parameters op de rij.
B(a,b1,.1,..2) :k2
= (a,a1,1.a,..b) :k1
-> a→↑{k}..a1 :b
-> a→↑{k1}b1
In het algemeen volgen de tellers d_i+1
van voorliggende pijldimensie i+1
elkaar dan zo op.
Herken de dubbele recursie b→c
rechts in de keten.
B(a,b,c.,1d_i..) :k>1
<-> T_i..b→c :k
& T_i = a→↑{i-}.. :d_i
Hier is k>1 want bij k=0 geldt a→b→c
voor de a↑{c}b supermachten en bij Conway's pijlketen k=1
geeft de vierde Birdy parameter d_1 een pijl meer aan,
die onder een hogere parameter 1d_i>1 ontbreekt.
B(a,b,c,d) <- a→..b→c :d
Bird's lineaire array gaat hetzelfde,
maar tel in c- een recursie minder,
omdat ons Birdy systeem niet de subexpressie
maar alleen het subtotaal b oplaadt.
In de multidimensionale array ruimte
die Knuth superpijlen →↑{c}
bovenop de pijlketen rij van Conway afzetten,
worden gewone recursies naar binnen toe genest
en hogere recursies consequent
van rechts naar links afgewikkeld.
Vereenvoudigde vergelijking van Conway-Knuth superpijlen
met de Birdy rij, met uiterste iterator b
en rij lengte c3 als dominante waarden.
Eerst een voorbeeld.
a→↑↑b1 = a→↑..a :b
<- B(a,a,a,a,b)
a→↑{c>1}b1 <-
B(.a,..b) :c2
<- a→↑{c>0}b2
Zo zijn de maximale getallen die in een
"type recursieve functie" met een rij
van links oplaadbare parameters te maken zijn,
vergelijkbaar met die van
de eerste serie Conway-Knuth superpijlen.
Ook bij andere waarden voor de parameters a hier,
mits niet op schaal te groot of triviaal klein,
blijft de vergelijking geldig.
$ 6. Multidimensionale arrays
Tussen variabelen in de functie rij staan komma's.
Deze systeem structuur kan worden uitgebreid
met nieuwe separatoren: een dimensie index,
geneste index rijen, recursie over nest diepte, etcetera.
We kunnen de capaciteit van al zulke array ruimtes
waarderen met een structuur som.
Dit hoofdstuk maakt
Bird's multidimensionale arrays
simpel in Birdy, vergelijkt deze met de dimensies
van Adam en Eva, en met het vervolg
van de Conway-Knuth superpijlketens.
$ 6.1. Structuur som N
Met het teken 1 vormen we natuurlijke getallen.
Reeksen enen 1.. geven variabelen in de expressie
een waarde, waarbij de functie van die variabele
bepaald wordt door zijn positie en het algoritme.
Een rij met natuurlijke variabelen vormt de eerste dimensie
in een array, terwijl deze eigenlijk bestaat uit rijen
van rijen van enen. Bij gelijke waarden en enkel optellen
drukt rij lengte een vermenigvuldiging uit.
Ook kunnen we natuurlijke getallen in een dimensionele
structuur plaatsen zonder deze een andere functie te geven
dan optellen.
Bouw een hyperkubus van 3 bij 3 bij 3 bij 3 met enen
en tel deze op.
111 = 3 = 3*1 = 3^1
+ 111 + 111 = 3*3 = 3^2
+ 111 111 111 = 3*3*2
+ 111 111 111 = 3*3*3 = 3^3
+ 3^3 + 3^3 = 3^4 = 81.
Voeg rij op rij toe in de tweede array dimensie.
Deze structuur van een reeks rijen noemen we een vlak,
hoewel zowel variabelen als rij lengtes in de evaluatie
van een array functie sterk variabel zijn.
Als pure structuur zonder functie geeft dit vlak
de tweede vermenigvuldiging.
Herhaling van vlakken vindt plaats in een kubieke ruimte,
de derde dimensie.
Met iedere herhaling van de voorgaande structuur
vormen we de volgende dimensie. En zonder functie telt
elke extra dimensie als een vermenigvuldiging, zodat de hele
multidimensionale structuur een macht uitdrukt.
In een array notatie plaatsen we deze ruimtes
op een lijn, door ze van elkaar te scheiden
met verschilende dimensie separatoren.
Het simpelst is om een aantal komma's ,{m}
na elkaar te gebruiken om dimensies onder te verdelen.
a,..,,..,,,.. :k_[i,j] :k_i :k_3
Constante getallen a en gelijke maten k
vermenigvuldigen onze telkubus tot a*k^3
en in het algemeen telt dit tot a*k^m
over m array dimensies.
T_i.. :m
T_i = a,{i}.. :k
Elke komma telt voor 0 in deze functieloze som context.
Ook bij gebruik van een komma teller ,{m}
uit te breiden tot index array structuur,
vervallen alle hogere separatoren tot 0
door het pure optel algoritme toe te passen.
Om de structuur te kwantificeren tellen we
variabelen n op in alle mogelijke array ruimtes,
die allen een vaste lengte of maat n hebben.
Bij n dimensies telt de structuur som n^n1
zo de hele multidimensionale array.
Een array functie laadt afgetelde iteratoren opnieuw op,
en via de lengte tellers ook de dimensie maten.
Als we daar meerdere komma's gebruiken
om dimensies te scheiden, dienen we iteraties
niet af te tellen tot lege 0 maar tot 1
om de structuur gelijk te houden.
Anders noteren we een komma index ,[m]
of in de stijl van Bird [m]
om de dimensie van de separator mee aan te geven.
Of we de separator waarden meetellen in de structuur
som blijft in het algemeen insignificant.
Met separatoren [1] erbij
komt de som van de rijen ongeveer op a1*k
en met [2] ertussen en maten k
in elk vlak op a1*k^2+2*k wat al minder bijdraagt.
Maar deze som blijft in n dimensies
kleiner dan n1^n1 inclusief separatoren.
Omdat de ruimtes tussenin toch altijd meer getalwaarde
bevatten, is inclusief separator waarden tellen
bij geneste index arrays en verder te verwaarlozen.
Het kleinst mogelijke array algoritme telt
alle variabele waarden n bij elkaar op.
Deze structuur som N of "bigN" gebruiken we
als ordeningsbasis voor de complexiteit
van array notaties.
Zo scoort Bird's geneste array structuur mogelijk als
een dubbele exponent, of als tetratie,
wat is vooralsnog onduidelijk.
Ook zijn we benieuwd of de structuur som,
die primitief recursief oogt,
in een hogere systeem constructie
de Ackermann supermacht n*{n}n kan tellen.
$ 6.2. Adam's dimensies
Adam is een primitief recursief array systeem,
waar iteraties worden afgeteld tot 0
en met de basis som b weer oplaadt.
Met drie regels over de
eerste rij
drukt Adam de popster supermachten in serie uit.
Afgerond of vanaf de vierde parameter k>1
in Adam is deze vergelijking geldig.
a,..f :k1 ~> a*{k}f2
Na de overgang ,[1]
die in Adam een nieuwe rij opent,
komt de teller k die de rij ervoor expandeert.
Tel deze af door een dimensionale regel,
die stapsgewijs extra variabelen
op de rij ervoor plaatst.
Na elke teller stap begint de evaluatie van de eerste rij
opnieuw met een hogere en grotere iterator b .
We ruimen nooit afgetelde iteratoren op,
zolang er nog hogere rijen of dimensies volgen.
In de evaluatie van grotere arrays neemt rij lengte
steeds met een groter aantal k parameters toe.
Elke nieuw subtotaal b is dermate dominant, dat opruimen
van de voorliggende uitgetelde dimensies geen zin heeft,
omdat de hoger opgeladen b
elk aantal variabelen daarin insignificant maakt.
Bird staat het opladen van afgetelde cellen ,1
alleen toe als er nog aftelbare variabelen
rechts in dezelfde rij volgen.
Hij elimineert al de lege structuren, die lager zijn
onder een hogere dimensie separator.
De consequentie van dit esthetisch principe is,
dat Bird de hele lege dimensie structuur
tegelijk moet opladen als de basis a,b
weer in de evaluatie ervan is bereikt.
Via een tussenvorm notatie met pijlhaken
bewaakt hij de maximaliteit van zijn array functie.
Bird mist ook onze eerste teller variabele,
omdat de vele rijen a,..1 ingebed in dimensies a[m]..1
ineens vanuit :b worden verspreid.
Het grote bezwaar tegen Bird's notatie is nu nog niet
duidelijk, maar welke van twee index substructuren
precies lager is, wordt in zijn hogere arrays
steeds moeilijker te bepalen.
Ook de simultane pijlhaak substituties
om alle links opgeruimde ruimtes in een
aparte evaluatie procedure opnieuw te vullen
is een drama.
Voor ons hoeft dit niet,
we groeien het nieuwe vanzelf aan op het oude.
Bouw de oplaadregel van Adam's rij
uit naar meer dimensies,
met ,[m] als separatoren.
De gewone komma , krijgt
de eerste ,[1] separator index.
Substitueer de cel van b
meteen door de a kopie,
wat we eerder uitstelden.
a,b1,{k>0},1R = a,a,{k}b,R
Voorwaarde hier is k>0 omdat in Adam a
bij de hele som b1 optelt.
Bij de stap met de teller
zou de tussenreeks k≥0 ook leeg kunnen zijn.
a,b1,{k},[m1]1R
= a,a,{k},[m]b,[m1]R
a,b1.,[m_i>0]..,[m1]1R :k
= a,a.,[m_i]..,[m]b,[m1]R :k
Of laat in geval k=0 elke separator introductie
aansluiten bij de motorregel;
qua getalgrootte haalt dit weinig uit.
a,b,1R = a,ab,R
a,b,[1m]1R = a,a,[m]b,[1m]R
De iteratie verschilt na opladen maar 1 stap
van subtotaal b zoals de motor regel dat optelt.
Maar omdat Adam over de rij de popster machten uitdrukt,
behouden we dit verschil in de regels voor dimensies.
Bij het opladen van b in een rij vervangt dit
de lege variabele zonder kleinere cel aan te plakken.
Volgt de regel voor eliminatie en komma substitutie
voor de uitgetelde separator index array.
,[] ≡ 0
,[1] ≡ ,
De equivalentie ≡ stelt dat deze separatoren
overal in de expressie vervangen kunnen worden.
Voor toepassing van een regel met index
zal die solo komma , een index ,[1] krijgen
en na evaluatie mag deze weer wegvallen.
De solo komma , verdeelt net als ,[1]
de rij dimensies onder in variabelen.
In de definitie tonen de regels 'a.'
de uitwerking met een komma ,
en daarna bij optie 'b.' de dimensie separator ,[m]
met de algemene vorm.
Bij uittellen van ,[1] tot ,[]
en eliminatie tot 0 blijkt dat de algemene regel
ook op rij parameters kan worden toepast,
niet alleen op dimensie lengte tellers.
Definitie van Adam systeem 'A.' voor de
multidimensionale structuur 'II.'
Deze regels gelden in volgorde.
Pas een regel pas op de expressie toe,
als de vorm van de regels ervoor geen match meer geeft.
-A.II.0. ,[1] ≡ ,
-A.II.1. a,b,1R = a,ab,R
-A.II.2a. a,b1,`,1R = a,a,`b,R
-A.II.2b. a,b1`,[1m]1R =
a,a`,[m]b,[1m]R
-A.II.3. a,b` = b
In de 'l-r' scan regels zijn alleen die tekens van belang,
die links van = de selectie van de expressie bepalen,
en die rechts van =
aangeven wat er na evaluatie verandert.
Op het uiteinde R of begin L of op de scan tik `
kan zich elke passieve passage bevinden (mogelijk leeg),
die bij precedentie van de regels ervoor
nog mogelijk is in de expressie.
Alternatief voor regel '3.' is om alle afgetelde iteraties
uiterst rechts op te ruimen, alvorens de uitkomst te geven.
Opruimen mag ook tijdens de evaluatie, voor
toepassing van regel '2.' plaatsvinden.
-A.II.3a. L,[m] = L, = L
-A.II.3b. a,b = b
Voeg naar keuze een speciale regel toe voor expressies,
die in de evaluatie van standaard a,R nooit ontstaan,
met m>0 in de dimensie index.
a,[m1]1R = a,[m]a,[m1]R
a,[m1]1R = a,a,[m1]R
In het geheel van dit grote getallen systeem
zijn deze opties niet significant.
$ 6.3. Eva's dimensies
Over de Eva rij zagen we een primitief recursieve
functie, die iteraties aftelt tot ,1
en met de som ab weer oplaadt.
Met maar twee regels over de
eerste rij
werden Eva's getallen zo groot als de supermachten.
a,..f :k1 ~> a*{k>0}f1
Nu gaan we reeksen van komma's ,{m} gebruiken
als dimensie separatoren, hoewel dit hetzelfde
werkt met een ,[m] dimensie index.
Het gaat er ons om met twee type tekens
zo groot mogelijke getallen te noteren
en te evalueren.
Maar de eerste komma in de basis a,b
van de expressie staat alleen.
De definitie van Eva systeem 'E'
voor de multidimensionale structuur 'II'.
De regels = betreffen de hele expressie,
en staan in volgorde van toepassing.
-E.II.1. a,b1`,{m1}2R =
a,1`,{m}ab,{m1}1R
-E.II.2. a,b` = ab
De variabele vorm b is gretig naar enen, zodat
een niet-lege passage ` moet beginnen met een komma.
Hetzelfde geldt voor de {m}
die het karakter ervoor herhaalt, zodat die tik `
niet eindigt met een komma, maar met een getal 1 .
Deze vorm b komt wel tijdelijk leeg
in de evaluatie, wat als 0 telt bij 1 .
In geval m=0 valt de verminderde komma ,{0} weg,
zodat 1ab optelt indien ` leeg is, of anders
om rechts de afgetelde variabele met 1ab op te laden.
Omdat de 'l-r' scan de eerste match na de passage `
pakt, zal die passage alleen uit afgetelde variabelen
bestaan, met ,{m}1 over vele dimensies.
Uitkomst regel '2' komt alleen ` aan bod als de hele
expressie met de eerdere regels is uitgewerkt.
Anders, na opruimen van rechts met extra regel '2a'
levert systeem Eva met compacte regel '2b'
de uitkomst zonder regel volgorde.
-E.II.2a. a,`,{m>0}1 = a,`
-E.II.2b. a,b = ab
Pas door voorbeelden uit te werken
en wat te schuiven met de tekens in regel '1.'
werd duidelijk, hoe systeem Eva
(principe ab opladen) goed kloppend is te maken.
Elke variabele laat in de evaluatie
een rest van 1 achter,
zodat elke komma reeks een dimensie aanduidt.
3,1,,3 = 3,1,{2}3 1= 3,1,{1}3,{2}2
1= 3,1,{0}3,{1}2,,2 = 3,4,2,,2
1= 3,1,{0}6,{1}1,,2 = 3,7,1,,2
1= 3,1,1,{1}9,{2}1 2= 3,1,1,9
1= 3,1,1,{0}3,{1}8 = 3,1,4,8
1= 3,1,{0}3,{1}3,8 = 3,4,3,8
= 3,10,1,8 = 3,1,13,7 = 3,37,1,7
= 3,1,40,6 = 3,1,121,5 = 3,1,364,4
= 3,1,3280,2 = 3,1,9841 = 3,29521,1
2= 29524
Een lengte teller ,,k1 voegt in Eva k
cellen toe aan de rij ervoor;
de ,1,9 in het voorbeeld.
De som waarde laadt op naar de rechtse iterator
en kan dus groot worden, hoewel dit ten opzichte
van de rij lengte niet significant is.
- - - - - - - - - - - - - - - -
Standaard dimensionale expressies in Eva
hebben de vorm a,1R die tijdens de evaluatie
gehandhaafd blijft. We kunnen ons systeem uitbreiden
met speciale regels voor expressies a,{k>1}R
om significant grotere getallen te noteren.
Bijvoorbeeld door het subtotaal ervan a,,m
om te zetten in een aantal komma's a,1,{m}a
wat er nogal verwrongen uitziet.
a,{k1}b = a,{k}1,{b}a
Samen met deze vernieuwde eerste regel
valt te bewijzen, dat onze extra Eva variant
met twee tekens de tweede separator index
van Adam evenaart.
a,{k}b1`,{m1}2R =
a,{k}1`,{m}ab,{m1}1R
Maar normaler voor k>0
is een toegevoegde regel als deze.
a,{k1}2R = a,{k}a,{k1}1R
Welke getallen Eva zo ongeveer uitdrukt
vergeleken met Conway's pijlketens en Bird's arrays
zullen we hieronder zien.
Gegeven dat twee tekens en twee regels
genoeg zijn om haar expressies te evalueren,
zal Eva ongetwijfeld het meest minimale systeem zijn
dat dergelijke record grote getallen oplevert.
$ 6.4. Adam en Eva op de Birdy rij
De systemen van Adam en Eva zijn vrijwel even krachtig.
We vergelijken hun dimensionale expressies
met die van Conway's pijlketens
en Conway-Knuth →↑{k} superpijlen
en die van Bird of Birdy over de lineaire array.
$ 6.4.1. Tweede rij met 'A' en 'E'
Adam en Eva drukken met de eerste cel op de tweede rij
allebei een supermacht uit, in Adam met 1 ster meer,
omdat Eva niet tot 0 maar tot 1 terugtelt.
A(a,b1,[2]c3) = a,a,b,[2]c2
= a,a*b1,,[2]c2
~ a,a,,a*b,[2]c1
~ a,a,,,a**a**2,[2]c {b~a}
~> a,a,{c3}a*{c2}a*{c2}2
~> a*{c3}a*{c3}2 ~> a*{c3}ab
E(a,b1,,c3) = a,1,ab,,c2
= a,1,1,a*ab,,c1
~> a,1,1,1,a**a**2,,c {b~a}
~> a,.1,..a*{c1}a*{c1}2 :c2
~> a*{c2}a*{c2}2
~> ab*{c3}2 <~ a*{c3}3
Die lengte teller wordt recursief opgeladen
met de tweede cel op de tweede rij.
De uitgetelde rij lengte die steeds resteert,
is insignificant, omdat deze wordt opgeteld
bij het volgende subtotaal in de eerste cel,
die consequent een supermacht groter is.
A(a,b1,[2],c1) = a,a,[2]b,c
~> a,a*{b}a,{b},[2],c
~> a*{..b..}a :c1:
-> a→b1→c1→2 =
a→b1→(..a^b1..) :c:
E(a,b,,1,c2) = a,1,,ab,c1
~> a,a*{ab}2,,1,c
~> a*{..ab..}2 :c1:
~ B(a,a,..ab..) :c1:
~ B(ab,c1,2,2)
~ Bird(ab,c1,1,2)
Hier in Eva lieten we dat rij restant ,1..
gelijk al weg, alsof het net als in Bird werd opgeruimd;
niet algoritmisch, maar bij benadering.
De functie 'B' is onze Birdy array functie
die verschilt van Bird in de manier van herladen
van cellen ,1 die op zijn.
Bird nest daar rechts de subexpressies in,
terwijl Birdy simpel de waarde van de tweede cel oplaadt,
die we vooraf nesten door 1 bij de derde cel te nemen.
A(a,b1,[2],,c1) = a,a,[2],b,c
~> a,a→a→b→2,[2],,c
~> a→a→(..b..)→2 :c1:
-> a→b1→c1→3
E(a,b1,,1,1,c2) = a,1,,1,ab1,c1
~> a,B(a,ab,2,2),,1,1,c
~> B(a,..ab..,2,2) :c:
~ B(ab,c1,3,2)
~ Bird(ab,c1,2,2)
Het verdere verloop over de tweede rij is daarmee duidelijk.
Het algoritme van Adam en Eva blijft even traag als voorheen,
waarbij elke volgende variabele op de rij
een enkele recursie uitdrukt.
A(a,b1,[2],{d1}c1)
= a,a,[2],{d}b,c
~> a,a→a→b→d1,[2],{d},c
~> a→a→(..b..)→d1 :c1:
-> a→b1→c1→d2
E(a,b1,,.1,..c2) :d1
= a,1,,.1,..ab1,c1 :d
~> a,B(a,ab,d1,2),,.1,..c :d1
~> B(a,..ab..,d1,2) :c:
~ B(ab,c1,d2,2)
~ Bird(ab,c1,d1,2)
Wie verwachtte dat de tweede rij gelijk ging lopen
met Bird's lineaire array,
zodra we de rij teller
met subtotalen van de eerste rij uitdrukken,
komt bedrogen uit.
Adam en Eva's oplaadregel is bijna zo krachtig
en de oplaadsom is aanvankelijk supergroot,
maar bij Conway en Birdy vindt dit opladen
herhaaldelijk plaats, in een onafzienbare trein
met geneste subexpressies.
En dat maakt het verschil.
$ 6.4.2. Het vlak van 'A'
De verschillen tussen Adam en Eva zijn
in de vergelijking met snellere systemen
eigenlijk onbelangrijk. Hier werken
we alleen de voorbeelden voor Adam uit.
De eerste parameter op de rij in Adam en Eva
is de lengte teller van de rij ervoor.
De teller die de tweede rij expandeert,
loopt zoals we zagen gelijk met de vierde
parameter d in Conway's pijlketen,
die de tweede dubbele recursie uitdrukt.
A(a,b1,[2],[2]d3) = a,a,[2],b,[2]d2
~ a,a→a→b→2,[2],,[2]d2
~ a,a→a→(a→a→b→2)→3,[2],,,[2]d1
~ a,a→a→b!→4,[2],,,,[2]d
~ a,a→a→b!→d3,[2],{d2},[2]1
~ a,a,[2],{d3}a→a→b!→d3
~ a→a→(..a..)→d3 :a→a→b!→d3:
~ a→a→(a→a→b!→d3)→d4
~> a→a→b!→d4
We voegen een uitroepteken toe aan een variabele b!
om een groot getal aan te geven dat daarmee is gemaakt,
maar dat niet significanter is dan de normale variabele
waarde zelf in deze context.
A(a,b1,[2],[2],d1) = a,a,[2],[2]b,d
~> a,a→a→a!→b1,[2],[2],d
~> a→a→a!→(..b1..) :d1
~> a→a→b!→d1→2
Vervolg deze vergelijking over de hele derde rij
van Adam. Deze werkt hetzelfde als op de tweede rij,
maar nu met de vijfde parameter in Conway's pijlketen.
A(a,b1,[2],[2],{e1}d1)
= a,a,[2],[2],{e}b,d
~> a,a→a→a!→b→e1,[2],[2],{e1}d
~> a→a→a!→(..b..)→e1 :d1
~> a→a→b!→d1→e2
Elke volgende rij in het vlak van Adam
drukt een dubbele recursie over de vorige rij uit.
Dit houdt in dat we steeds een schakel toevoegen
aan Conway's pijlketen in de vergelijking.
In zijn geheel geeft dit een tripel recursie.
A(a,b.,[2]..,{z}y) :k
~> a→..b!→y→z1 :k
Merk op dat systeem Eva hetzelfde presteert
met als tekens enen 1.. en twee separatoren,
namelijk , tussen variabelen
en ,, tussen de rijen.
Verschil is dat de afgetelden in Eva ,1..
en ,,1.. niet nul zijn, maar het aantal herhalingen
ervan blijft gelijk aan die in Adam.
De variabele rechts moet y1 zijn,
maar telt dus hetzelfde aantal stappen
van opladen.
# 6.4.3. Dimensies in 'E'
..