“Opus est magnis numeris”
– Vladimir Poetin
0
optellen, Ster 1
vermenigvuldigen, Ster 2
machtsverheffene=2
, Pijlketens onder e, In de pijlkubus met f, Pijldimensies over Birdy's rij2
gelijkt Conway's →d
, Adam's vlak gelijkt Conway's pijlketen, Dimensies in Eva gelijkt de Birdy rijTel 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.
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.
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 di is te vertalen :=
naar een serie factoren di*
van oplopende machten ^i
van r die opgeteld +
wordt.
di.. k:0 :=
d0.+di*r^i.. :k≥0
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..?
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...
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..?
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.
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.
0
optellenBij 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.
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.
1
vermenigvuldigenVermenigvuldigen 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.
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
machtsverheffenMachtsverheffen **
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
.
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.
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.
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.
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.
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.
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.
Evaluatie van supermachten gaat makkelijker in een functie. Alle operaties a*{c}b
die we uitwerken volgens de PopSter definitie krijgen deze vorm.
a*{ci+1}bi*{ci}+..b0 k:1 waar b>0 en ci1>ci≥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.
Zo is de reeks van sterparen die naar rechts toe aflopen compleet.
a*{i}bi*{i-}+..b0 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 bi 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.
De systemen in dit hoofdstuk beperken zich tot een enkele rij variabele getallen. We ontwerpen de primitief recursieve functies Adam en Eva, die een rij evalueren tot een getal 1..
in de orde van grootte van de a*{k}f
supermachten.
In systeem A voor “Adam” werken de iteratoren op de eerste rij als op de top gestapelde popsterren uit het vorige hoofdstuk.
Thema bij de constructie van Adam is natuurlijkheid, waarbij we iteraties aftellen tot 0
en cellen en hun structuren leeg kunnen staan.
Om zo zuinig mogelijk te zijn met type tekens, gebruikt systeem Adam geen ronde haakjes. We substitueren geen subexpressies (X)
maar steeds dezelfde kopie van constante a die optelt in b en schuiven die subtotalen b door naar rechts. Er is dus geen “functie recursie”, waar functie variabelen worden overschreven door een afgetelde functie expressie.
Adam's expressies op de rij bestaan uit tekens 1
in getallen en ertussen enkele komma ,
separatoren. Als variabelen afgeteld zijn, kunnen we naar keuze een 0
teken schrijven of deze gewoon weglaten. Meerdere komma's ,..
stellen dus geen hoger dimensionale structuur voor, maar een serie lege cellen.
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 subtotalen b naar de lege iteraties ,0
rechts, wat we “opladen” noemen. Zo bouwt Adam grote getallen op.
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
met dezelfde lengte.
Adam noteert supermachten met maar twee tekens en we evalueren Adam expressies op de rij door drie primitieve regels toe te passen.
De evaluatie van expressies A.I op de Adam rij verloopt congruent aan die van de popster supermachten. Maar Adam telt in de lage variabelen links op, terwijl 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 Knuth supermachten met hele grote reeksen). Een uitgetelde structuur met alleen nog lege ,0
rechts zou in Adam tot op het laatst kunnen 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 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, en drie regels voor selectie en evaluatie.
Variabele b≥0
en het aantal komma's ,{k≥0}
kan nul zijn, zonder teken.
Bij evaluatie regels met =
staat aan beide zijden de hele expressie. Voor het deel wat in de evaluatie ongewijzigd blijft wordt een tekst variabele gebruikt, die ook leeg (zonder tekens) kan zijn. Zoals hier het expressie deel R rechts.
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 worden opgeruimd.
In de uitgebreidere definitie Aa.I van Adam vallen de resterende komma's van afgetelde variabelen meteen vanaf rechts weg.
Ons “scan” teken `
staat hier voor de passieve passage aan de rechter kant.
Stel b≥0
bij het subtotaal. Waar we een aantal :k>0
afgetelde variabelen ,0
tussenin herhalen, zou dat strikt een rij lege komma's ,{k}
zijn.
De gesplitste regel verandert het systeem niet. Na elkaar toepassen van regel 2a. en 2b. in systeem Aa. werkt net zoals 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 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.
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.
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.
We vergelijken de evaluatie in functie A.I met de popster operaties. Na wat rekenen ermee volgt de algemene vorm van zulke vergelijkingen.
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.
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.,pi.. 0:k = a*{i}pi*{i-}+..p0 k:1 ~ a*{k}(pk+1)*{k-}+pk- ~ a*{k}(pk+2)
Bij kleine expressies k<2
of bij relatief grote superfactoren pk-
zal de bijtelling van pk+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.
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.
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. met een rij I. van variabelen.
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.
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.
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.
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 af0
op te tellen met een lege *{0}
ster.
a.,fi.. 0:k ~ a*{k}(fk+1)
De hoogste superexponent fk 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.
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.
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.
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.
Conway bedacht zijn pijlketen functie om significant grotere getallen te maken dan met Knuth's oppijlen mogelijk is.
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 separator komma ,
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.
Hier stelt de tekst variabele X het linker deel a.→ni.. :k
van de keten voor, met een k≥0
aantal variabelen ni maar op zijn minst de constante a.
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.
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.→xi..
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 vi 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.→vi.. :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.
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.
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.
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 zo uit te werken als gewoon de volgende rij recursies beginnen.
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
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.
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 →{mi}↑{ni}..
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.
Lineaire arrays zijn functie expressies bestaande uit een rij parameters: met de constante a en een subtotaal som b gevolgd door een aantal variabelen ,c,d,e,..
waarmee we stappen tellen van een recursie.
Door subexpressie substitutie in cel b en het opladen van afgetelde variabelen, noteert Bird's lineaire array maximaal grote getallen over de 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” eenvoudiger opzetten.
De eerste rij van Birdy gaat uit van de lineaire array notatie van Chris Bird. Uit zijn systeem verwijderen we de overbodige substituties, die aan de grootte van het uitkomst getal weinig bijdragen. Onze simpeler regel komt pas in het spel bij de vierde parameter en verder, na het supermacht trio.
Bouw een systeem Birdy met 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 hogere Birdy array systemen geldig.
Eerst twee eliminatie regels: om de uitkomst op te leveren en om een afgetelde variabele aan het uiteinde rechts te verwijderen.
De expressie term X links bevat in de expressie B(a,1)
alleen de a en bij uitbreiding een rij a.,pi..
met :k≥0
variabelen.
Nu reduceert B(a,1)
via B(a)
tot uitkomst a1
wat 1
optelt. Deze successor functie past bij optellen met paar a,b
en Birdy vangt hiermee hetzelfde aan als David Hilbert's functie reeks van primitieve recursies.
De selectie functie Bird(a) = a
werkt ook, een voorsprong van 1
draagt niet veel bij.
Regel 1. om afgetelde uiteindes ,1
te verwijderen, zal in elke Birdy expressie gelden met een laatste rij deel.
En voor uitgebreide separatoren ,[X]1
in hogere arrays kan dit principe om afgetelde iteratoren op het array einde op te ruimen van kracht blijven. Maar we zien af van Bird's selectie apparaat om laatste variabelen of lege structuren ook uit de voorafgaande rijen of arrayruimtes te elimineren.
Bird neemt, in navolging van Conway's pijlketen, als basis operatie B(a,b)
het machtsverheffen. Dit vooronderstelt een stap van vermenigvuldigen, die we kunnen herhalen buiten de array functie.
Bird(a,b1) = a*(a,b) == a*..(a,1) :b = a^b*(a) = a^b*a = a^b1 macht
Net als Hilbert begint Jonathan Bowers, die het oorspronkelijke idee voor Bird's arrays had, zijn array functie primitief door a+b
op te tellen.
We gaan het parameter paar in Birdy direct optellen, door de enige komma te elimineren en de uitkomst uit de functie te tillen.
Dit maakt regel 0. van de successor uitkomst alsnog overbodig.
Een alternatieve regel telt het paar a,b
op door enen stapsgewijs over te hevelen van b naar a ofwel door te tellen.
Of voer dit met een functie B(a,b1) = B(B(a),b)
terug tot optellen, zoals Hilbert deed. Hier is b de iterator, die de successor functie recursief in cel a substitueert.
Optellen aan het begin kost ons Birdy systeem twee supermachten **
ten opzichte van Bird, in de nu volgende arrays a,b,c
met drie parameters.
De algoritmische motor in Bird's lineaire array is de recursieve functie substitutie. Deze regel telt de derde parameter c af en substitueert de tweede cel b voor een subexpressie die met b-
vrijwel minimaal is afgeteld. Met herhaald aftellen van b tot 1
volgt de hele functie recursie. Samen met aftellen van c tot 1
vormt dit proces de “dubbele recursie” die de supermacht getallen genereert.
Drie parameters drukken bij Bird exact de supermacht operaties a^{c}b
uit, maar de dubbele recursie begint in Birdy a,b,1
met optellen. We moeten hier dan 2
tellen bij input parameters c om dezelfde uitkomst te verkrijgen.
Als de laatste recursie stap met b=1
is bereikt, reduceert de subexpressie tot de constante a, mits daar geen parameter c=1
op volgt in de rij.
Tekst variabele X omvat hier de rij rechts met een of meer variabelen. En bij uitbreiding naar hogere arrays staat X voor elk mogelijk vervolg rechts.
De regel voor substitutie, de functie recursie stap, is de werkmotor om getallen groot te maken op de eerste rij. Deze is essentieel voor arrays, die snel moeten starten. Bird nummert dit als Rule 5. in zijn lineaire array.
Voorwaarde bij deze substitutie regel is dat b>0
omdat cellen in Birdy nooit leeg komen te staan.
De tekst variabele X≥0
begint hier met de rest 1..
van de waarde van derde parameter c en dan volgen eventueel meerdere parameters rechts. Later omvat deze X alle mogelijke hogere arrayruimtes, maar X kan ook leeg zijn.
Zo evalueert B(a,2,c1)
tot B(a,a,c)
door subexpressie substitutie en daarna de bodem regel. Als c=2
dan geeft dit een kwadraat. Hier geldt c>0
omdat anders regel 1. voor afval van ,1
wordt toegepast.
Een regel is toepasbaar, als zijn vorm links kan worden gevonden in de expressie. Dat is bij regel 4. in B(a,b,c)
zolang parameter b>1
en c>1
aftelbaar zijn.
De vorm van de regels in deze definitie is zo, dat we precedentie van eerdere regels niet als voorwaarde hoeven stellen in Birdy.
Het trio, een rij met drie parameters, produceert aldus de supermachten.
Met 1
stap van c nest de recursie een reeks van b subexpressies tot aan de constante a op de bodem.
B(a,b1,c1) = B(a,(a,b,c1),c) == B(a,..(a,1,c1)..,c) :b: = (a,..a..,c) :b:
We mogen het functie voorschrift weglaten, bestaande uit de letter B. voor Birdy en de expressie haakjes, als het gebruikte systeem duidelijk genoeg is.
Na optellen ab
met B(a,b)
, vermenigvuldigen a*b
met B(a,b,2)
en machtsverheffen a**b
met B(a,b,3)
drukt het Birdy trio B(a,b,c1)
exact de getallen uit van de ster supermachten a*{c}b
uit hoofdstuk $.2.
We willen grote getallen in systeem Birdy ongeveer parallel laten lopen met die van Bird's arrays, waarbij expressies met c2
in Birdy altijd gelijk of insignificant groter zijn dan die van dezelfde input met c in Bird, nooit kleiner.
Gegeven een aftelbare expressie (a,1Z)
van een Bird type array functie, dan krijgt in de volgende evaluatiestap de subexpressie de vorm (a,Z)
die we bij de substitutie regel al zagen en hier afkorten met een dollar $
teken.
Bird substitueert de subexpressie $
ook in zijn Rule 4. voor opladen van de rij, maar alleen in de hoogste, rechts afgetelde cel.
Bird(a,b1.,1..1R) :k>1 = Bird(.a,..$,1R) :k
De rij lengte bij k=1
behandelde Bird als een apart geval met zijn Rule 5. voor functie substitutie, dat is bij Birdy regel 4.
We maken Bird's oplaadregel nu simpeler door niet de subexpressie maar het subtotaal uit b in de laatste cel ,1
van de afgetelde reeks te substitueren.
Tussenliggende variabelen laten we hierbij ongemoeid.
In ons Birdy systeem komt in cel b een kopie van constante a in de plaats.
Regel voor het opladen van afgetelde variabelen ,1
op de eerste rij. Stel k>0
voor het aantal lege cellen, zodat c=1
als eerste opgeladen wordt.
Herhaalde toepassing ==
van deze oplaadregel in Birdy vult het afgetelde deel van de expressie naar links. Het resultaat is ongeveer hetzelfde als Bird met zijn complete oplaadregel voor de rij bereikt: alle voorliggende variabelen ,1
zijn door ,a
vervangen.
B(a,b1.,1..1X) :k2 = B(a,a1.,1..b,1X) :k1 == B(a,a1,1.a,..b,1X) :k = B(a,$,.a,..b,1X) :k
We kunnen ook eerst het subtotaal uit b verschuiven en de lege cel b=1
pas daarna met een kopie van a aanvullen. Dit geeft een tweevoudige methode voor opladen, waar bij b>1
het hele subtotaal verkast.
De afleiding uit primitievere regels zal wiskundigen een plezier doen.
Maar bij hogere arrays werken we ons met die a kopie in de nesten, omdat het grote subtotaal uit b vervolgens niet meer beschikbaar is om op te laden binnen de afgetelde geneste arrays. Zo blijven de uitkomsten onbetamelijk klein.
Bij index array separatoren zullen we het subtotaal in b dus laten staan en laden er een kopie van op.
Van Bird is bekend hoe zijn array met vier parameters ongeveer even grote getallen uitdrukt als Conway's pijlketen over zijn gehele lengte.
We vergelijken in dit hoofdstuk verschillende notatie systemen voor de eerste rij. Om met aanpassing van de input expressies even grote getallen uit te drukken.
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 een minimaal kleinere en na <-
een minimaal grotere uitkomst. Na aanpassing van de input a zal dit verschil verdwijnen.
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: x
-> 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)
Elke rij expressie in Birdy is dus “iets kleiner” <~
dan dezelfde expressie in Bird. Het subexpressie opladende systeem van Bird en ons subtotaal opladende Birdy systeem zijn daarmee vergeleken.
Zowel Bird als Birdy 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 belangrijk.
Of die opgeladen b steeds verpakt wordt in een subexpressie $
zoals bij Bird, is van ondergeschikt belang. Tel 1
extra bij input parameter c in Birdy, dan geeft dit een substitutie $
stap extra, die het verschil al bijna compenseert.
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.
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 volgende type recursie noemen we “tripel recursie”.
Vergelijk de Conway-Knuth superpijlketens, die we definieerden in hoofdstuk $.4.3, met onze simpele Birdy versie van de array notatie van Bird.
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.
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 subexpressie 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!
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.
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 di+1
van voorliggende pijldimensie i+1
elkaar dan zo op. Herken de dubbele recursie b→c
rechts in de keten.
B(a,b,c.,1di..) :k>1 <-> Ti..b→c 1:k & Ti = a→↑{i-}.. :di
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 d1 een pijl meer aan, die onder een hogere parameter 1di>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 arrayruimte 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 lineaire array functie met een links oplaadbare rij parameters te maken zijn, vergelijkbaar met die van de eerste serie Conway-Knuth superpijlen. Ook bij andere waarden voor parameters a hier, mits niet op schaal te groot of triviaal klein, blijft de vergelijking geldig.
Iedere Conway-Knuth superpijl bouwt met het voorgaande type recursie een hogere reeks recursies. Recursie typen zijn hier telbaar geworden.
De enumeratie van recursies komt veel langzamer tot stand dan de natuurlijke getallen. Het valt te verwachten dat deze type getallen door hogere array structuren als het ware worden vermenigvuldigd, etc. en dat we ze uiteindelijk kunnen noteren met dezelfde soort arrays.
Elke nieuwe recursie is gebouwd op een reeks vorige recursies. Maar het hele concept van reeks of rij valt als insignificant weg te strepen tegen de diepte van geneste arrays. Misschien dat in de diepte de recursie typen samenvallen met de getallen uit de functie arrays die ermee worden geclassificeerd.
Zou dit niet zo zijn en blijven de typen arrays significant achter bij de natuurlijke functie arrays, dan zou door het rigoreus definieren van overgangen of cycli daartussen, de cycli gebruikt kunnen worden om record grote getallen functies mee aan te geven.
Een multidimensionale array is een structuur, onderverdeeld in repeterende reeksen van variabelen. De structuursom die alle variabelen optelt is triviaal en traag. We evaluaren multidimensionale expressies met verschillende algoritmes voor het maken van grote getallen.
Onze Adam en Eva systemen beginnen primitief met supermachten over de rij, maar lopen in meerdere dimensies parallel aan de Conway-Knuth ketens met superpijlen. Multidimensionale Birdy arrays, die we afleiden uit die van Bird, zijn maximaal snel, doordat we functie recursies opladen naar hogere iteratoren.
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 de ontstane ruimtes in de array kwantificeren met een structuursom.
Bij de structuursom vormt elke volgende dimensie een vermenigvuldiging en de hele multidimensionale array een macht. Dit leggen we uit.
Reeksen enen 1..
maken de natuurlijke getallen, die de variabelen vormen in de expressie. De functie van variabelen in de array functie wordt bepaald door hun positie in de structuur en door het toegepaste algoritme.
Een rij met variabelen noemen we de eerste dimensie in een array, terwijl deze eigenlijk bestaat uit rijen van rijen van enen. Als we deze getallen alleen maar optellen, dan drukt de rij lengte een vermenigvuldiging uit.
Ook kunnen we gelijke variabelen in een dimensionele structuur plaatsen, die geen andere functie heeft dan optellen.
Vul een kubus van 3 bij 3 bij 3 met getallen 3
en tel deze op.
111 = 3 = 3*1 = 3^1 getal + 111 + 111 = 3*3 = 3^2 rij + 111 111 111 = 3*3*2 + 111 111 111 = 3*3*3 = 3^3 vlak + 3^3 + 3^3 = 3^4 = 81. kubus
Hier voegen we rij op rij toe in de tweede dimensie. De array structuur met een reeks rijen noemen we een vlak, hoewel naast getalwaarden ook de rij lengtes in de evaluatie ervan sterk variabel zijn.
We stapelen een aantal vlakken in de kubieke ruimte, de derde dimensie. Elke herhaling van de voorgaande dimensie structuur vormt de volgende dimensie.
Maar in de array notatie staat elke ruimte structuur op een lijn, waarin deze van elkaar gescheiden zijn met specifieke separatoren. Het simpelst is om een aantal komma's ,{m}
na elkaar te gebruiken om de dimensie m onder te verdelen.
a,..,,..,,,.. :ki,j :ki :k3
Stellen we gelijke zijden k dan sommeert dit tot a*k^3
in een kubieke array.
Of tel met gelijke maten k een m aantal dimensies op tot a*k^m
een macht.
a.Ti.. :m
Ti = ,{i}.. :k
Voor de structuursom stellen we alle aantallen gelijk aan a, zowel de variabele waarden als de rij lengtes, de dimensie maten en het aantal dimensies. Vervolgens laten we alle separatoren ertussen wegvallen.
Elke komma telt dus voor 0
en heeft geen functie, behalve optellen. Ook als we de komma teller ,{m}
uitbreiden tot index arrays, met geneste index getallen, vervallen deze in hun geheel tot 0
en houden we de structuursom over.
Zouden we die index waarden meetellen in de som, dan blijft dat insignificant. Met index [1]
erbij en lengte k komt de som op de rij ongeveer op a1*k
. En met index [2]
en k rijen in het vlak op a1*k^2+2*k
wat al minder bijdraagt. Zo blijft de som inclusief indexen in a dimensies kleiner dan a1^a1
.
De som van de variabelen in de gescheiden ruimte zal altijd significant groter zijn, dan de som van de indexen van hun scheiding, ook bij diep geneste arrays.
Voor de structuursom tellen we variabelen a op in alle ruimtes, allen met vaste maten a en gegeven a dimensies. Dan is de structuursom a^a1
voor de multidimensionale array, wat we tot een tetratie a^^2
kunnen afronden.
Array functies laden afgetelde iteratoren opnieuw op en via de lengte tellers ook de dimensie maten. Als we meerdere komma's gebruiken voor het scheiden van dimensies, mogen we iteraties dus niet aftellen tot 0
maar tot 1
om de structuur intact te houden. Gebruik anders een komma index ,[m]
of in de stijl van Bird [m]
voor de dimensie m van de ermee onderscheiden ruimte.
De structuursom kwantificeert de wiskundige informatie die de arrayruimte kan bevatten, ongeacht de tekens van de separatoren of operatoren die we op de variabelen erin toepassen.
Het is voorlopig nog de vraag of de structuursom primitief recursief blijft, of in een hogere array constructie de Ackermann supermachten a*{a}a
te boven gaat.
Adam is een primitief recursief array systeem, waar iteraties worden afgeteld tot 0
en met een som b weer opgeladen. Met de variabelen van de eerste rij drukt Adam de reeks popster supermachten uit.
Vanaf de vierde parameter k>1
in Adam, of ook afgerond, is dat in vergelijking.
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.,[mi>0]..,[m1]1R :k = a,a.,[mi]..,[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. met een separator index.
Deze regels gelden in volgorde. Pas dus een regel pas op de expressie toe, als de vorm van de regels ervoor geen match meer geeft.
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.
Een alternatieve regel 3. ruimt de afgetelde iteraties uiterst rechts op en geeft daarna de uitkomst. Dit opruimen mag ook voordat we regel 2. toepassen.
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.
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
We zullen in Eva reeksen van komma's ,{m}
gebruiken als dimensie separator, wat net zo werkt als de dimensie index ,[m]
in Adam. Het gaat ons er hier 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 blijft alleen staan.
De definitie van Eva systeem E. voor de multidimensionale structuur IIa. met als separator index een aantal komma's.
De regels =
betreffen de hele expressie, en staan in volgorde van toepassing.
De variabele vorm b is gretig naar enen, zodat een niet-lege passage `
begint met een komma. Hetzelfde geldt voor m≥0
in de kwantificatie, die het teken ervoor herhaalt, zodat de tik `
niet eindigt met een komma, maar op cijfer 1
.
Vorm b komt wel tijdelijk leeg te staan en telt als 0
in de volgende evaluatie.
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.
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.
In de functies Adam A en Eva E passen we op dezelfde structuren verschillende regels toe, maar de uitgedrukte getallen zijn ongeveer even groot.
Hier worden multidimensionale expressies in systeem A en E eerst vergeleken met Conway's pijlketens en vervolgens met Bird of Birdy over de lineaire array.
2
gelijkt Conway's →d
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,c1) = a,1,,ab,c ~> a,a*{ab}2,,1,c ~> a*{..ab..}2 :c: ≈ B(a,a,..ab..) :c: ~ 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.
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 de variabele b!
om een groot getal aan te geven dat daarmee is gemaakt, maar dat toch niet significant groter wordt dan een normale input waarde binnen de gegeven context.
Zoals een faculteit n! = 1.*i.. :n
dat zou kunnen zijn.
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.
Ga uit van een d aantal rijen in het Eva vlak, waarbij de laatste rij op dezelfde manier is verlengd als in de vergelijking van de tweede rij hierboven.
Die tweede dimensie teller in Eva is te vergelijken met de vierde parameter in Birdy, die zoals we van Bird weten de lengte van Conway's pijlketen geeft.
E(a,b,,,d2) = a,1,,ab,,,d1 ~> a,1.,,ab!.. :d1 ~> a,a.,,a..,a..b :d :b! ~> B(a,a,b!,d1) ~> B(a,b,1,d2) ~ ab→↑d3
Eva's tweede dimensie teller wordt recursief opgeladen met subtotalen b.
E(a,b,,,1,c1) = a,1,,,ab,c ~> a,B(a,b,1,ab),,,1,c ~> B(a,b,1,..ab..) :c: ~ B(ab,c1,2,1,2)
Zo correspondeert de tweede cel in Birdy met de laatste variabele in Eva, want beide tellen de functie recursie af over de hele expressie.
Zo drukt de derde cel in Birdy de lengte uit van de laatste rij in Eva, die (net als haar eerste rij) een dubbele recursie toevoegt.
Zo staat de vierde cel in Birdy gelijk aan het aantal rijen in het laatste vlak van Eva, die als een tripel recursie of pijlketen van Conway is aangeplakt.
En zo telt de vijfde cel e in Birdy het aantal vlakken in de derde dimensie van Eva. Bij uitbreiding die in de laatste (meest rechtse) drie dimensionale array.
E(a,b,,,,e1) = a,1,,,ab,,,,e ~> a,1.,,,ab!.. :e ~> B(a,b,1,1,e1)
Zo krijgt in het algemeen in de vergelijking elke rechts gesorteerde Eva dimensie een corresponderende parameter op de rij van Bird of Birdy, die in Eva het aantal van die dimensies telt en in Birdy een type recursie toevoegt.
Het aantal separator tekens k voor de hoogste Eva dimensie is dominant en dan het aantal :f
van die te vullen ruimtes.
E(a,b,{k1}f1) ~> a,1.,{k}ab!.. :f ~> B(a,b.,1..f) :k ~ ab→↑{k-}f1
De dimensionale structuur van Conway-Knuth →↑
superpijlen werd in sectie $.5.3.4. al precies vergeleken met de lineaire array van Birdy.
De rij van Eva begint bij de supermacht parameter c van Conway en Bird. Het vlak met rijen ,,
van Eva vormt Conway's pijlketen →
of parameter d bij Bird. Elke volgende ruimte ,{k2}
in Eva loopt een dimensie achter bij die van de Conway-Knuth →↑{k}
superpijlen en opent een parameter op de rij van Bird.
In multidimensionale expressies van systeem Birdy noteren we vrijwel even grote getallen als met Bird's multidimensionale arrays, maar Birdy's definitie is simpeler en de evaluatie van expressies verloopt stapsgewijs.
Tot de functie recursie regel 4. is de definitie van Birdy dezelfde als voor de rij, maar de tekst vorm X kan elke toegestane multidimensionale passage bevatten.
Omdat eerdere regels voorrang krijgen, zijn er op de scan tic `
hier alleen nog reeksen ,[mi]1..
afgetelde cellen te verwachten in meerdere dimensies, met separator indices mi>0
en als eerste index ,[1]
de gewone ,
komma.
Opladen met regel 5b. onder separatoren met index in Birdy is vergelijkbaar met oplaadregel 2b. voor dimensies in systeem Adam. Maar de in Birdy uitgedrukte getallen worden door subexpressie recursie dimensionaal groter.
Separator eliminatie met regel 6a. is alleen nodig, als we de vorm van opladen op de rij 5a. overslaan en daar de dimensionale vorm 5b. toepassen.
Afgetelde cellen in tussenliggende dimensies laten we in Birdy net als in Adam gewoon staan. Lengtes en maten nemen zodoende cummulatief toe en worden steeds allemaal opnieuw opgeladen. Maar al deze extra ruimte blijft insignificant vergeleken met elke daarboven opgeladen teller, die stapsgewijs een dominant grote ruimte toevoegt. Wel of niet opruimen verandert de uitkomst vrijwel niet.
De dimensie index ,[m]
van de separator komma kan worden verlengd tot een rij ,[m.,ni..]
van index variabelen. Een structuur of getalruimte met deze hierarchie van separatoren noemt Bird de hyperdimensionale array.
Op hun beurt kunnen separatoren in index arrays weer met een volgende index of rij worden uitgebreid. Zo nesten we rijen in eerdere rijen tot elke mogelijke diepte. Zo'n systeem voor grote getallen noemt Bird “geneste arrays”.
Bouw een structuursom van geneste arrays op door nieuwe separatoren toe te voegen en rond daarbij alle maten gelijk af tot n, dat wil zeggen de variabele waarden en rij lengtes, die op dat niveau ondergeschikt zijn.
Begin door op de rij met alleen komma ,
separatoren een som =>
van een n aantal variabelen n op te tellen.
, => n*n ,[2] => n^3 ,[m] => n^n
De structuursom van de multidimensionale array is aldus een macht.
Elke volgende separator schept ruimte voor n keer de vorige som.
,[1,1] => n^n1 ,[m,1] => n^nn ,[m,n] => n^(n*n)
De eerste index doet de som n^n
keer. Met elke volgende index wordt de vorige index vermenigvuldiging n keer herhaald.
,[m,1,1] => n^(n*n1) ,[m,n,1] => n^(n*n*2) ,[m,n,n2] => n^n^3
Volgt de structuursom met de eerste geneste rij in hyperdimensionale arrays.
,[m.,ni..] = ,[,[2]1] => n^n^n ,[m,[2]1] => n^(n^n+n) ,[m.,ni..,[2]1] => n^(n^n*2)
Elke index stap rechts op een voorgaande index structuur herhaalt dus de toegevoegde exponent van de vorige som.
,[,[2]3] => n^(n^n*3) ,[,[2]m] => n^n^n1 ,[,[2]m,1] => n^(n^n1*2)
Zodat elke rechtse index variabele 1
telt bij de dubbele exponent en elke extra index rij dus n daarbij optelt, wat de som geeft van het index vlak.
,[,[2]m,n] => n^n^n2 ,[,[2],[2]1] => n^n^nn ,[,[2],[2],[2]1] => n^n^(n*3)
Vervolg de derde index dimensie door rechts lagere structuren te plaatsen.
,[,[3]1] => n^n^n^2 ,[,[3]m] => n^n^(n^2+1) ,[,[3],[2]1] => n^n^(n^2+n)
Dezelfde index dimensie opbouwen herhaalt de hoge exponent in de som.
,[,[3],[3]1] => n^n^(n^2*2) ,[,[4]1] => n^n^n^3 ,[,[m]1] => n^n^n^n
De tweede niveau index telt dus de tetratie n^^4
als som. Vergelijk de eerste index ,[m]
met som n^^2
en de eerste index rij ,[,[2]1]
daartussen met n^^3
als som.
Als dat zo doorgaat dan telt de tweede geneste index rij de tetratie n^^5
op.
,[,[m,1]1] => n^n^n^nn ,[,[m,n]1] => n^n^n^n^2 ,[,[,[2]1]1] => n^n^n^n^n
Als de structuur rechts op het eerste index niveau een index [L,n]
extra krijgt, dan telt dat 1
bij de derde exponent. Gebeurt dit op het tweede geneste niveau, dan telt dat 1
bij de vijfde exponent.
,[,[,[m]1]1]1 => n^^6 ,[..2..]1 :t: => n^^tt- ,[..m..]1 :t: => n^tt
De som van de hele ruimte van rij in rij geneste arrays volgt dan als tetratie. Met een even toren (van exponenten) bij een enkele index binnenin en een oneven toren bij een rij met een aantal indexen binnenin.
Om variabelen te ordenen in meerdimensionale arrays gebruikten we in Adam een index ,[m]
bij de komma en in Eva reeksen ,{m}
komma's. Zo kon Eva met maar twee tekens getallen uitdrukken ter grootte van Bird's lineaire array.
Vergelijk meervoudige separatoren met telbare elementen, zoals voorgesteld voor Eva, versus <=>
de gebruikte indexering in systeem Adam.
Bij de hyperdimensionale arrays wordt op het eerste geneste array niveau in Adam aan de komma een rij van indexen gehecht. Dezelfde hyperruimte kan worden onderverdeeld door seperatoren bestaande uit telbare komma's met een tweede type separator ,[2]
ertussen, hier links in Eva.
,{m} <=> ,[m] ,{m},[2],{n} <=> ,[m,n] ,{m}.,[2],{ni}.. <=> ,[m.,ni..]
Om deze opbouw te vervolgen maken we in dit hoofdstuk alle komma met index elementen ,[2]
ook telbaar in Eva. Aan de dubbel geneste indexen in Adam ontspruit een even grote verzameling separatoren. De ruimte van deze arrays zouden we multidimensionale hyperdimensies kunnen noemen.
L,[2],[2]R <=> ,[L,[2]R] ,[2],[2],[2] <=> ,[,[3]] ,[2].. :m <=> ,[,[m]]
Deze groeiende elementen verdelen steeds links L en rechts R de voorgaande subruimte in de separator. Bij Eva is dat in de komma elementen serie, versus in de vooronder geneste index array bij Adam.
L,[3]R <=> ,[L,[,1]R] ,[3].. :m1 <=> ,[,[m,1]] ,[n2].. :m1 <=> ,[,[m,n]]
Eva's eerste telbare index vormt dezelfde ruimtes als de tweede enkele index in de dubbel geneste array van Adam. Dan volgt de tweede telbare index in Eva, eerste nest, versus de derde index in Adam, tweede nest.
L,[1,2]R <=> ,[L,[,0,1]R] ,[1n,2].. :m1 <=> ,[,[m,n,1]] ,[1n1,1n2].. :m1 <=> ,[,[m,n1,n2]]
Volgende komma indexen lopen parallel in Eva telbaar in het eerste nest, versus Adam enkel in het tweede nest. Adam's index dimensie teller m is de laagste variabele en deze ontbreekt bij Eva, zodat de index rij in Eva 1
korter uitvalt.
,[.1,..2] :p <=> ,[,[.,0..,1]] :p
,[.1ni,..1].. :p :m1 <=> ,[,[m.,ni..]] :p
De eerste index rij van meervoudige separatoren blijkt equivalent te zijn aan de tweede geneste index rij met enkelvoudige separatoren.
Elke geneste array kan op dezelfde manier in ruimtes worden onderverdeeld. Eén index niveau in Eva met telbare separatoren valt steeds gelijk uit met twee niveau's in Adam met enkelvoudige.
Dus geldt voor alle geneste index rijen in Eva versus Adam.
,[..Q1..].. :q: :m & Q = ni,.. :p <=> ,[..m,Q..] :qq:
Een geneste arrays met telbare separatoren zal met een soortgelijk algoritme even grote getallen maken als een geneste arrays met enkelvoudige separatoren. Maar het aantal nest niveau's is de helft als separatoren op alle niveau's telbaar zijn.
Helaas is dit geen belangrijke verbetering, het verschil bedraagt slechts een factor 2
qua nest diepte. Met in het systeem vervolg een diepte teller die oplaadbaar is, wordt dit verschil insignificant.
Conclusie is dat telbare tekens aanvankelijk belangrijk zijn, te beginnen met de 1..
natuurlijke getallen en eventueel met ,..
komma's voor array dimensies. Maar dat array functies met enkelvoudige separatoren, enkelvoudige haakjes, etcetera, “oneven” zo snel over de geneste niveau's gaan, en na uitbreiding in de diepte ongeveer net zo snel.
Als meervoudige tekens geen voordeel dienen, houden we regels voor recursies en structuur elementen liever simpel, door alleen te tellen met variabelen. Zulke systemen groeien door grotere structuur concepten te herkennen, en deze als voorheen recursief te herhalen vanuit de basis som.
Het opladen van indexen in een geneste array noemen we “inladen”. Daar zijn wat problemen mee, zodat we de regels ervoor secuur moeten bepalen.
Het eerste probleem is, dat het inladen van een subtotaal niet in een passieve index array met een lege teller erboven mag gebeuren. Want dan zou de opgebouwde som, de q in dit voorbeeld, verloren gaan.
a,b1,[1,1]1 = a,a,[,1]b,[1,1] = a,a,[a-,]b,[1,1] == a,q,`,[1,1] ≠ a,a,`,[q,]
Om dit te voorkomen moeten we separator index arrays opruimen, als de iterator ervan is afgeteld en die separator de laatste is binnen zijn ouder array of rechts in de expressie.
Dit geldt eigenlijk alleen als die index arrays een actief separator-iterator element bevatten, zoals de ,1
in de subarray ,[1,1]
rechts in het voorbeeld. Maar het is mooier en makkelijker om ook de afgetelde dimensionale separatoren ,[m]
en enkele komma's ,
te verwijderen, die op het eind van de ouder array komen.
Zolang er in de ouder array nog een actief element volgt, worden lege iteratoren vanzelf opnieuw opgeladen, dus hoeven we deze niet op te ruimen.
Merk op dat Bird ervoor kiest om afgetelde separatoren te verwijderen, als deze links voor een grotere staan. Maar we vinden het te bewerkelijk om alle soorten index arrays qua grootte te moeten kunnen vergelijken.
Het tweede probleem
Definitie Adam systeem A. met geneste structuur III. voor het nesten van rijen separator indexen.
De regels gelden in volgorde: de eerste vorm van links die past, evalueert de expressie naar rechts.
Een l-r scan `=
selecteert de eerste vorm vanaf de linker kant in de expressie, en kan op de spatie
een fragment overslaan. Als een tweede vorm in de regel volgt, selecteren we de eerste match ervan (na de eerste vorm) in de expressie, mogelijk te vinden in een geneste array. In het overgeslagen passieve tekst fragment bevindt zich dus zeker geen match.
Zo komt de selectie van een r-l regel met =`
direct rechts in expressies.
Bij een regel met gelijk teken =
selecteert de vorm een hele expressie.
Met substitutie equivalentie ≡
kan de vorm overal te vinden zijn.
Teken 0
staat voor een evaluatie waar de selectie vorm geheel vervalt.
Een expressie in Adam kan eventueel tussen ronde A()
haakjes staan.
De tekst variabelen S zijn gesloten, zodat elk open haakje erin van een geneste index array [Si]
gepaard is aan een sluit haakje.
Ons “rechts binnen” criterium is simpel te constateren. En we slagen er goed in, om alle inactief blijvende elementen te elimineren. Waarna regel 1. de uitkomst geeft. Opruimen met regels 4. moet wel tijdens de evaluatie plaatsvinden, met voorrang boven regels 5. dus.
Eva moet een systeem worden, dat met zo weinig mogelijk tekens en eenvoudige regels zo groot mogelijke getallen uitdrukt. Eerst nog bouwen we Eva's telbare komma's voor dimensies uit naar een rij hyperdimensionale indexen. Bij dieper geneste arrays zetten we het systeem over naar de bekende index variabelen.
Bird noteerde zijn hyperdimensionale arrays met separatoren bestaande uit een rij index variabelen, de eerste van zijn geneste arrays.
We zagen in $.7.3.1 al hoe de rij indexen van Adam ook met aantallen komma's kan worden weergegeven en dan dezelfde ruimtes voor variabelen schept. Hier vervolgen we het dimensionale systeem IIa. van Eva en introduceren de enkele punt komma ;
als separator tussen de reeksen van komma's.
Definitie systeem Eva E. voor de eerste geneste rij IIb. met telbare komma's als hyperindexen. Pas die `=
regel toe, die een vorm selecteert die het meest links in de expressie begint.
De reductie van expressies verloopt dan zo.
a,b1,`,,;,,;,,2 4,2= a,1,`,;,,;,,ab 3= a,1,`,{a1};,;,,ab == a,c1,`,{a1};,;,,2 4,2= a,1,`,{a};,;,,ac == a,d1,`,,;,;,,2 4,2= a,1,`,;,;,,ad 3,2a= a,1,`,;,{a1}ad 3= a,1,`,{a1};,{a}ad
Er ontstaat een probleem. De komma reeksen in de separator worden steeds met de constante a opgeladen en niet met de groeiende subtotalen, hier met b<c<d
in de evaluatie trein aangegeven.
Want op het moment dat een komma index of aantal tot 1
wordt afgeteld, schuift het subtotaal naar de variabele erboven. De uitkomst blijft zodoende klein.
Het algoritme van Adam of Eva kopieert alleen de constante en nergens het subtotaal. Dit kan alleen werken, als een geneste array wordt opgeladen door de iterator of index, die rechts in de array erboven staat. De regel daarvoor moet duidelijk maken waar de separator structuur precies eindigt, wat niet triviaal is.
Bij meerdere niveau's van arrays zal de subtotaal waarde zich trapsgewijs naar binnen toe verplaatsen. Het geeft geen pas daar in Eva steeds de constante a bij op te tellen.
Voor geneste arrays in het algemeen in Eva stappen we over op het komma index systeem van Adam. Definitie Eva systeem E. voor geneste rijen III. met regels in volgorde.
..
We kiezen er bij het opladen in Bodhi systeem Bo. voor om subtotaal b te laten staan, om daarna de eventueel afgetelde indexen voor zijn rekening te nemen. Dit lijkt het simpelst, maar betekent dat er een kopie van b moet worden gemaakt om in te voegen.
De voorafgaande reeks afgetelde iteraties wordt daarna ook met het grote subtotaal b gevuld. Maar toch zijn Bodhi's uitkomsten niet significant groter dan die bij Bird of Birdy, waar de ruimte links met de kleine a wordt gevuld.
Regel voor het opladen van afgetelde variabelen ,1
op de eerste rij. Stel k>0
voor het aantal lege cellen, zodat c=1
als eerste kan opladen.
Herhaalde toepassing ==
van deze regel vult het hele afgetelde deel links in de rij stapsgewijs met kopies b>0
van het subtotaal.
== Bo(a,1b,1.b,..1X) :k = Bo(a,$.,b..,1X) :k
We kunnen in evaluatie voorbeelden de gebruikte regelnummers aangeven.
Ook expressies B(a,1,1)
en B(a,1,1,R)
waar regel 3. geen match voor vormt, kunnen onder regel 5. vallen.
B(a,1,1,2,3) 5= B(a,1,1,1,3) 5== B(a,1,1,1,1) 1== B(a) 2= a
Zulke expressies ontstaan nooit in de evaluatietrein en hebben als input weinig zin. Altijd is die expressie triviaal te herleiden tot a.
Vergelijk Birdy B. met Bodhi Bo.
B(a,b1,2,2) ~> Bo(a,b1,2,2) <- (a,3,..a..1) :b:
Omdat:
B(a,b1,2,2) = (a,(a,b,2,2),1,2) := (a,(a,b,2,2),(a,b,2,2)) <- (a,(a,a,(a,b,2,2)),(a,b,2,2)) =: (a,3,(a,b,2,2)1) == (a,3,..a..1) :b:
..
0
optellen, Ster 1
vermenigvuldigen, Ster 2
machtsverheffene=2
, Pijlketens onder e, In de pijlkubus met f, Pijldimensies over Birdy's rij2
gelijkt Conway's →d
, Adam's vlak gelijkt Conway's pijlketen, Dimensies in Eva gelijkt de Birdy rijTel 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.
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.
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 di is te vertalen :=
naar een serie factoren di*
van oplopende machten ^i
van r die opgeteld +
wordt.
di.. k:0 :=
d0.+di*r^i.. :k≥0
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..?
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...
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..?
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.
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.
0
optellenBij 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.
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.
1
vermenigvuldigenVermenigvuldigen 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.
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
machtsverheffenMachtsverheffen **
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
.
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.
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.
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.
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.
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.
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.
Evaluatie van supermachten gaat makkelijker in een functie. Alle operaties a*{c}b
die we uitwerken volgens de PopSter definitie krijgen deze vorm.
a*{ci+1}bi*{ci}+..b0 k:1 waar b>0 en ci1>ci≥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.
Zo is de reeks van sterparen die naar rechts toe aflopen compleet.
a*{i}bi*{i-}+..b0 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 bi 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.
De systemen in dit hoofdstuk beperken zich tot een enkele rij variabele getallen. We ontwerpen de primitief recursieve functies Adam en Eva, die een rij evalueren tot een getal 1..
in de orde van grootte van de a*{k}f
supermachten.
In systeem A voor “Adam” werken de iteratoren op de eerste rij als op de top gestapelde popsterren uit het vorige hoofdstuk.
Thema bij de constructie van Adam is natuurlijkheid, waarbij we iteraties aftellen tot 0
en cellen en hun structuren leeg kunnen staan.
Om zo zuinig mogelijk te zijn met type tekens, gebruikt systeem Adam geen ronde haakjes. We substitueren geen subexpressies (X)
maar steeds dezelfde kopie van constante a die optelt in b en schuiven die subtotalen b door naar rechts. Er is dus geen “functie recursie”, waar functie variabelen worden overschreven door een afgetelde functie expressie.
Adam's expressies op de rij bestaan uit tekens 1
in getallen en ertussen enkele komma ,
separatoren. Als variabelen afgeteld zijn, kunnen we naar keuze een 0
teken schrijven of deze gewoon weglaten. Meerdere komma's ,..
stellen dus geen hoger dimensionale structuur voor, maar een serie lege cellen.
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 subtotalen b naar de lege iteraties ,0
rechts, wat we “opladen” noemen. Zo bouwt Adam grote getallen op.
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
met dezelfde lengte.
Adam noteert supermachten met maar twee tekens en we evalueren Adam expressies op de rij door drie primitieve regels toe te passen.
De evaluatie van expressies A.I op de Adam rij verloopt congruent aan die van de popster supermachten. Maar Adam telt in de lage variabelen links op, terwijl 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 Knuth supermachten met hele grote reeksen). Een uitgetelde structuur met alleen nog lege ,0
rechts zou in Adam tot op het laatst kunnen 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 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, en drie regels voor selectie en evaluatie.
Variabele b≥0
en het aantal komma's ,{k≥0}
kan nul zijn, zonder teken.
Bij evaluatie regels met =
staat aan beide zijden de hele expressie. Voor het deel wat in de evaluatie ongewijzigd blijft wordt een tekst variabele gebruikt, die ook leeg (zonder tekens) kan zijn. Zoals hier het expressie deel R rechts.
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 worden opgeruimd.
In de uitgebreidere definitie Aa.I van Adam vallen de resterende komma's van afgetelde variabelen meteen vanaf rechts weg.
Ons “scan” teken `
staat hier voor de passieve passage aan de rechter kant.
Stel b≥0
bij het subtotaal. Waar we een aantal :k>0
afgetelde variabelen ,0
tussenin herhalen, zou dat strikt een rij lege komma's ,{k}
zijn.
De gesplitste regel verandert het systeem niet. Na elkaar toepassen van regel 2a. en 2b. in systeem Aa. werkt net zoals 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 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.
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.
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.
We vergelijken de evaluatie in functie A.I met de popster operaties. Na wat rekenen ermee volgt de algemene vorm van zulke vergelijkingen.
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.
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.,pi.. 0:k = a*{i}pi*{i-}+..p0 k:1 ~ a*{k}(pk+1)*{k-}+pk- ~ a*{k}(pk+2)
Bij kleine expressies k<2
of bij relatief grote superfactoren pk-
zal de bijtelling van pk+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.
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.
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. met een rij I. van variabelen.
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.
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.
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.
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 af0
op te tellen met een lege *{0}
ster.
a.,fi.. 0:k ~ a*{k}(fk+1)
De hoogste superexponent fk 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.
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.
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.
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.
Conway bedacht zijn pijlketen functie om significant grotere getallen te maken dan met Knuth's oppijlen mogelijk is.
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 separator komma ,
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.
Hier stelt de tekst variabele X het linker deel a.→ni.. :k
van de keten voor, met een k≥0
aantal variabelen ni maar op zijn minst de constante a.
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.
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.→xi..
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 vi 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.→vi.. :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.
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.
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.
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 zo uit te werken als gewoon de volgende rij recursies beginnen.
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
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.
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 →{mi}↑{ni}..
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.
Lineaire arrays zijn functie expressies bestaande uit een rij parameters: met de constante a en een subtotaal som b gevolgd door een aantal variabelen ,c,d,e,..
waarmee we stappen tellen van een recursie.
Door subexpressie substitutie in cel b en het opladen van afgetelde variabelen, noteert Bird's lineaire array maximaal grote getallen over de 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” eenvoudiger opzetten.
De eerste rij van Birdy gaat uit van de lineaire array notatie van Chris Bird. Uit zijn systeem verwijderen we de overbodige substituties, die aan de grootte van het uitkomst getal weinig bijdragen. Onze simpeler regel komt pas in het spel bij de vierde parameter en verder, na het supermacht trio.
Bouw een systeem Birdy met 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 hogere Birdy array systemen geldig.
Eerst twee eliminatie regels: om de uitkomst op te leveren en om een afgetelde variabele aan het uiteinde rechts te verwijderen.
De expressie term X links bevat in de expressie B(a,1)
alleen de a en bij uitbreiding een rij a.,pi..
met :k≥0
variabelen.
Nu reduceert B(a,1)
via B(a)
tot uitkomst a1
wat 1
optelt. Deze successor functie past bij optellen met paar a,b
en Birdy vangt hiermee hetzelfde aan als David Hilbert's functie reeks van primitieve recursies.
De selectie functie Bird(a) = a
werkt ook, een voorsprong van 1
draagt niet veel bij.
Regel 1. om afgetelde uiteindes ,1
te verwijderen, zal in elke Birdy expressie gelden met een laatste rij deel.
En voor uitgebreide separatoren ,[X]1
in hogere arrays kan dit principe om afgetelde iteratoren op het array einde op te ruimen van kracht blijven. Maar we zien af van Bird's selectie apparaat om laatste variabelen of lege structuren ook uit de voorafgaande rijen of arrayruimtes te elimineren.
Bird neemt, in navolging van Conway's pijlketen, als basis operatie B(a,b)
het machtsverheffen. Dit vooronderstelt een stap van vermenigvuldigen, die we kunnen herhalen buiten de array functie.
Bird(a,b1) = a*(a,b) == a*..(a,1) :b = a^b*(a) = a^b*a = a^b1 macht
Net als Hilbert begint Jonathan Bowers, die het oorspronkelijke idee voor Bird's arrays had, zijn array functie primitief door a+b
op te tellen.
We gaan het parameter paar in Birdy direct optellen, door de enige komma te elimineren en de uitkomst uit de functie te tillen.
Dit maakt regel 0. van de successor uitkomst alsnog overbodig.
Een alternatieve regel telt het paar a,b
op door enen stapsgewijs over te hevelen van b naar a ofwel door te tellen.
Of voer dit met een functie B(a,b1) = B(B(a),b)
terug tot optellen, zoals Hilbert deed. Hier is b de iterator, die de successor functie recursief in cel a substitueert.
Optellen aan het begin kost ons Birdy systeem twee supermachten **
ten opzichte van Bird, in de nu volgende arrays a,b,c
met drie parameters.
De algoritmische motor in Bird's lineaire array is de recursieve functie substitutie. Deze regel telt de derde parameter c af en substitueert de tweede cel b voor een subexpressie die met b-
vrijwel minimaal is afgeteld. Met herhaald aftellen van b tot 1
volgt de hele functie recursie. Samen met aftellen van c tot 1
vormt dit proces de “dubbele recursie” die de supermacht getallen genereert.
Drie parameters drukken bij Bird exact de supermacht operaties a^{c}b
uit, maar de dubbele recursie begint in Birdy a,b,1
met optellen. We moeten hier dan 2
tellen bij input parameters c om dezelfde uitkomst te verkrijgen.
Als de laatste recursie stap met b=1
is bereikt, reduceert de subexpressie tot de constante a, mits daar geen parameter c=1
op volgt in de rij.
Tekst variabele X omvat hier de rij rechts met een of meer variabelen. En bij uitbreiding naar hogere arrays staat X voor elk mogelijk vervolg rechts.
De regel voor substitutie, de functie recursie stap, is de werkmotor om getallen groot te maken op de eerste rij. Deze is essentieel voor arrays, die snel moeten starten. Bird nummert dit als Rule 5. in zijn lineaire array.
Voorwaarde bij deze substitutie regel is dat b>0
omdat cellen in Birdy nooit leeg komen te staan.
De tekst variabele X≥0
begint hier met de rest 1..
van de waarde van derde parameter c en dan volgen eventueel meerdere parameters rechts. Later omvat deze X alle mogelijke hogere arrayruimtes, maar X kan ook leeg zijn.
Zo evalueert B(a,2,c1)
tot B(a,a,c)
door subexpressie substitutie en daarna de bodem regel. Als c=2
dan geeft dit een kwadraat. Hier geldt c>0
omdat anders regel 1. voor afval van ,1
wordt toegepast.
Een regel is toepasbaar, als zijn vorm links kan worden gevonden in de expressie. Dat is bij regel 4. in B(a,b,c)
zolang parameter b>1
en c>1
aftelbaar zijn.
De vorm van de regels in deze definitie is zo, dat we precedentie van eerdere regels niet als voorwaarde hoeven stellen in Birdy.
Het trio, een rij met drie parameters, produceert aldus de supermachten.
Met 1
stap van c nest de recursie een reeks van b subexpressies tot aan de constante a op de bodem.
B(a,b1,c1) = B(a,(a,b,c1),c) == B(a,..(a,1,c1)..,c) :b: = (a,..a..,c) :b:
We mogen het functie voorschrift weglaten, bestaande uit de letter B. voor Birdy en de expressie haakjes, als het gebruikte systeem duidelijk genoeg is.
Na optellen ab
met B(a,b)
, vermenigvuldigen a*b
met B(a,b,2)
en machtsverheffen a**b
met B(a,b,3)
drukt het Birdy trio B(a,b,c1)
exact de getallen uit van de ster supermachten a*{c}b
uit hoofdstuk $.2.
We willen grote getallen in systeem Birdy ongeveer parallel laten lopen met die van Bird's arrays, waarbij expressies met c2
in Birdy altijd gelijk of insignificant groter zijn dan die van dezelfde input met c in Bird, nooit kleiner.
Gegeven een aftelbare expressie (a,1Z)
van een Bird type array functie, dan krijgt in de volgende evaluatiestap de subexpressie de vorm (a,Z)
die we bij de substitutie regel al zagen en hier afkorten met een dollar $
teken.
Bird substitueert de subexpressie $
ook in zijn Rule 4. voor opladen van de rij, maar alleen in de hoogste, rechts afgetelde cel.
Bird(a,b1.,1..1R) :k>1 = Bird(.a,..$,1R) :k
De rij lengte bij k=1
behandelde Bird als een apart geval met zijn Rule 5. voor functie substitutie, dat is bij Birdy regel 4.
We maken Bird's oplaadregel nu simpeler door niet de subexpressie maar het subtotaal uit b in de laatste cel ,1
van de afgetelde reeks te substitueren.
Tussenliggende variabelen laten we hierbij ongemoeid.
In ons Birdy systeem komt in cel b een kopie van constante a in de plaats.
Regel voor het opladen van afgetelde variabelen ,1
op de eerste rij. Stel k>0
voor het aantal lege cellen, zodat c=1
als eerste opgeladen wordt.
Herhaalde toepassing ==
van deze oplaadregel in Birdy vult het afgetelde deel van de expressie naar links. Het resultaat is ongeveer hetzelfde als Bird met zijn complete oplaadregel voor de rij bereikt: alle voorliggende variabelen ,1
zijn door ,a
vervangen.
B(a,b1.,1..1X) :k2 = B(a,a1.,1..b,1X) :k1 == B(a,a1,1.a,..b,1X) :k = B(a,$,.a,..b,1X) :k
We kunnen ook eerst het subtotaal uit b verschuiven en de lege cel b=1
pas daarna met een kopie van a aanvullen. Dit geeft een tweevoudige methode voor opladen, waar bij b>1
het hele subtotaal verkast.
De afleiding uit primitievere regels zal wiskundigen een plezier doen.
Maar bij hogere arrays werken we ons met die a kopie in de nesten, omdat het grote subtotaal uit b vervolgens niet meer beschikbaar is om op te laden binnen de afgetelde geneste arrays. Zo blijven de uitkomsten onbetamelijk klein.
Bij index array separatoren zullen we het subtotaal in b dus laten staan en laden er een kopie van op.
Van Bird is bekend hoe zijn array met vier parameters ongeveer even grote getallen uitdrukt als Conway's pijlketen over zijn gehele lengte.
We vergelijken in dit hoofdstuk verschillende notatie systemen voor de eerste rij. Om met aanpassing van de input expressies even grote getallen uit te drukken.
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 een minimaal kleinere en na <-
een minimaal grotere uitkomst. Na aanpassing van de input a zal dit verschil verdwijnen.
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: x
-> 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)
Elke rij expressie in Birdy is dus “iets kleiner” <~
dan dezelfde expressie in Bird. Het subexpressie opladende systeem van Bird en ons subtotaal opladende Birdy systeem zijn daarmee vergeleken.
Zowel Bird als Birdy 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 belangrijk.
Of die opgeladen b steeds verpakt wordt in een subexpressie $
zoals bij Bird, is van ondergeschikt belang. Tel 1
extra bij input parameter c in Birdy, dan geeft dit een substitutie $
stap extra, die het verschil al bijna compenseert.
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.
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 volgende type recursie noemen we “tripel recursie”.
Vergelijk de Conway-Knuth superpijlketens, die we definieerden in hoofdstuk $.4.3, met onze simpele Birdy versie van de array notatie van Bird.
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.
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 subexpressie 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!
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.
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 di+1
van voorliggende pijldimensie i+1
elkaar dan zo op. Herken de dubbele recursie b→c
rechts in de keten.
B(a,b,c.,1di..) :k>1 <-> Ti..b→c 1:k & Ti = a→↑{i-}.. :di
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 d1 een pijl meer aan, die onder een hogere parameter 1di>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 arrayruimte 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 lineaire array functie met een links oplaadbare rij parameters te maken zijn, vergelijkbaar met die van de eerste serie Conway-Knuth superpijlen. Ook bij andere waarden voor parameters a hier, mits niet op schaal te groot of triviaal klein, blijft de vergelijking geldig.
Iedere Conway-Knuth superpijl bouwt met het voorgaande type recursie een hogere reeks recursies. Recursie typen zijn hier telbaar geworden.
De enumeratie van recursies komt veel langzamer tot stand dan de natuurlijke getallen. Het valt te verwachten dat deze type getallen door hogere array structuren als het ware worden vermenigvuldigd, etc. en dat we ze uiteindelijk kunnen noteren met dezelfde soort arrays.
Elke nieuwe recursie is gebouwd op een reeks vorige recursies. Maar het hele concept van reeks of rij valt als insignificant weg te strepen tegen de diepte van geneste arrays. Misschien dat in de diepte de recursie typen samenvallen met de getallen uit de functie arrays die ermee worden geclassificeerd.
Zou dit niet zo zijn en blijven de typen arrays significant achter bij de natuurlijke functie arrays, dan zou door het rigoreus definieren van overgangen of cycli daartussen, de cycli gebruikt kunnen worden om record grote getallen functies mee aan te geven.
Een multidimensionale array is een structuur, onderverdeeld in repeterende reeksen van variabelen. De structuursom die alle variabelen optelt is triviaal en traag. We evaluaren multidimensionale expressies met verschillende algoritmes voor het maken van grote getallen.
Onze Adam en Eva systemen beginnen primitief met supermachten over de rij, maar lopen in meerdere dimensies parallel aan de Conway-Knuth ketens met superpijlen. Multidimensionale Birdy arrays, die we afleiden uit die van Bird, zijn maximaal snel, doordat we functie recursies opladen naar hogere iteratoren.
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 de ontstane ruimtes in de array kwantificeren met een structuursom.
Bij de structuursom vormt elke volgende dimensie een vermenigvuldiging en de hele multidimensionale array een macht. Dit leggen we uit.
Reeksen enen 1..
maken de natuurlijke getallen, die de variabelen vormen in de expressie. De functie van variabelen in de array functie wordt bepaald door hun positie in de structuur en door het toegepaste algoritme.
Een rij met variabelen noemen we de eerste dimensie in een array, terwijl deze eigenlijk bestaat uit rijen van rijen van enen. Als we deze getallen alleen maar optellen, dan drukt de rij lengte een vermenigvuldiging uit.
Ook kunnen we gelijke variabelen in een dimensionele structuur plaatsen, die geen andere functie heeft dan optellen.
Vul een kubus van 3 bij 3 bij 3 met getallen 3
en tel deze op.
111 = 3 = 3*1 = 3^1 getal + 111 + 111 = 3*3 = 3^2 rij + 111 111 111 = 3*3*2 + 111 111 111 = 3*3*3 = 3^3 vlak + 3^3 + 3^3 = 3^4 = 81. kubus
Hier voegen we rij op rij toe in de tweede dimensie. De array structuur met een reeks rijen noemen we een vlak, hoewel naast getalwaarden ook de rij lengtes in de evaluatie ervan sterk variabel zijn.
We stapelen een aantal vlakken in de kubieke ruimte, de derde dimensie. Elke herhaling van de voorgaande dimensie structuur vormt de volgende dimensie.
Maar in de array notatie staat elke ruimte structuur op een lijn, waarin deze van elkaar gescheiden zijn met specifieke separatoren. Het simpelst is om een aantal komma's ,{m}
na elkaar te gebruiken om de dimensie m onder te verdelen.
a,..,,..,,,.. :ki,j :ki :k3
Stellen we gelijke zijden k dan sommeert dit tot a*k^3
in een kubieke array.
Of tel met gelijke maten k een m aantal dimensies op tot a*k^m
een macht.
a.Ti.. :m
Ti = ,{i}.. :k
Voor de structuursom stellen we alle aantallen gelijk aan a, zowel de variabele waarden als de rij lengtes, de dimensie maten en het aantal dimensies. Vervolgens laten we alle separatoren ertussen wegvallen.
Elke komma telt dus voor 0
en heeft geen functie, behalve optellen. Ook als we de komma teller ,{m}
uitbreiden tot index arrays, met geneste index getallen, vervallen deze in hun geheel tot 0
en houden we de structuursom over.
Zouden we die index waarden meetellen in de som, dan blijft dat insignificant. Met index [1]
erbij en lengte k komt de som op de rij ongeveer op a1*k
. En met index [2]
en k rijen in het vlak op a1*k^2+2*k
wat al minder bijdraagt. Zo blijft de som inclusief indexen in a dimensies kleiner dan a1^a1
.
De som van de variabelen in de gescheiden ruimte zal altijd significant groter zijn, dan de som van de indexen van hun scheiding, ook bij diep geneste arrays.
Voor de structuursom tellen we variabelen a op in alle ruimtes, allen met vaste maten a en gegeven a dimensies. Dan is de structuursom a^a1
voor de multidimensionale array, wat we tot een tetratie a^^2
kunnen afronden.
Array functies laden afgetelde iteratoren opnieuw op en via de lengte tellers ook de dimensie maten. Als we meerdere komma's gebruiken voor het scheiden van dimensies, mogen we iteraties dus niet aftellen tot 0
maar tot 1
om de structuur intact te houden. Gebruik anders een komma index ,[m]
of in de stijl van Bird [m]
voor de dimensie m van de ermee onderscheiden ruimte.
De structuursom kwantificeert de wiskundige informatie die de arrayruimte kan bevatten, ongeacht de tekens van de separatoren of operatoren die we op de variabelen erin toepassen.
Het is voorlopig nog de vraag of de structuursom primitief recursief blijft, of in een hogere array constructie de Ackermann supermachten a*{a}a
te boven gaat.
Adam is een primitief recursief array systeem, waar iteraties worden afgeteld tot 0
en met een som b weer opgeladen. Met de variabelen van de eerste rij drukt Adam de reeks popster supermachten uit.
Vanaf de vierde parameter k>1
in Adam, of ook afgerond, is dat in vergelijking.
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.,[mi>0]..,[m1]1R :k = a,a.,[mi]..,[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. met een separator index.
Deze regels gelden in volgorde. Pas dus een regel pas op de expressie toe, als de vorm van de regels ervoor geen match meer geeft.
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.
Een alternatieve regel 3. ruimt de afgetelde iteraties uiterst rechts op en geeft daarna de uitkomst. Dit opruimen mag ook voordat we regel 2. toepassen.
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.
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
We zullen in Eva reeksen van komma's ,{m}
gebruiken als dimensie separator, wat net zo werkt als de dimensie index ,[m]
in Adam. Het gaat ons er hier 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 blijft alleen staan.
De definitie van Eva systeem E. voor de multidimensionale structuur IIa. met als separator index een aantal komma's.
De regels =
betreffen de hele expressie, en staan in volgorde van toepassing.
De variabele vorm b is gretig naar enen, zodat een niet-lege passage `
begint met een komma. Hetzelfde geldt voor m≥0
in de kwantificatie, die het teken ervoor herhaalt, zodat de tik `
niet eindigt met een komma, maar op cijfer 1
.
Vorm b komt wel tijdelijk leeg te staan en telt als 0
in de volgende evaluatie.
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.
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.
In de functies Adam A en Eva E passen we op dezelfde structuren verschillende regels toe, maar de uitgedrukte getallen zijn ongeveer even groot.
Hier worden multidimensionale expressies in systeem A en E eerst vergeleken met Conway's pijlketens en vervolgens met Bird of Birdy over de lineaire array.
2
gelijkt Conway's →d
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,c1) = a,1,,ab,c ~> a,a*{ab}2,,1,c ~> a*{..ab..}2 :c: ≈ B(a,a,..ab..) :c: ~ 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.
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 de variabele b!
om een groot getal aan te geven dat daarmee is gemaakt, maar dat toch niet significant groter wordt dan een normale input waarde binnen de gegeven context.
Zoals een faculteit n! = 1.*i.. :n
dat zou kunnen zijn.
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.
Ga uit van een d aantal rijen in het Eva vlak, waarbij de laatste rij op dezelfde manier is verlengd als in de vergelijking van de tweede rij hierboven.
Die tweede dimensie teller in Eva is te vergelijken met de vierde parameter in Birdy, die zoals we van Bird weten de lengte van Conway's pijlketen geeft.
E(a,b,,,d2) = a,1,,ab,,,d1 ~> a,1.,,ab!.. :d1 ~> a,a.,,a..,a..b :d :b! ~> B(a,a,b!,d1) ~> B(a,b,1,d2) ~ ab→↑d3
Eva's tweede dimensie teller wordt recursief opgeladen met subtotalen b.
E(a,b,,,1,c1) = a,1,,,ab,c ~> a,B(a,b,1,ab),,,1,c ~> B(a,b,1,..ab..) :c: ~ B(ab,c1,2,1,2)
Zo correspondeert de tweede cel in Birdy met de laatste variabele in Eva, want beide tellen de functie recursie af over de hele expressie.
Zo drukt de derde cel in Birdy de lengte uit van de laatste rij in Eva, die (net als haar eerste rij) een dubbele recursie toevoegt.
Zo staat de vierde cel in Birdy gelijk aan het aantal rijen in het laatste vlak van Eva, die als een tripel recursie of pijlketen van Conway is aangeplakt.
En zo telt de vijfde cel e in Birdy het aantal vlakken in de derde dimensie van Eva. Bij uitbreiding die in de laatste (meest rechtse) drie dimensionale array.
E(a,b,,,,e1) = a,1,,,ab,,,,e ~> a,1.,,,ab!.. :e ~> B(a,b,1,1,e1)
Zo krijgt in het algemeen in de vergelijking elke rechts gesorteerde Eva dimensie een corresponderende parameter op de rij van Bird of Birdy, die in Eva het aantal van die dimensies telt en in Birdy een type recursie toevoegt.
Het aantal separator tekens k voor de hoogste Eva dimensie is dominant en dan het aantal :f
van die te vullen ruimtes.
E(a,b,{k1}f1) ~> a,1.,{k}ab!.. :f ~> B(a,b.,1..f) :k ~ ab→↑{k-}f1
De dimensionale structuur van Conway-Knuth →↑
superpijlen werd in sectie $.5.3.4. al precies vergeleken met de lineaire array van Birdy.
De rij van Eva begint bij de supermacht parameter c van Conway en Bird. Het vlak met rijen ,,
van Eva vormt Conway's pijlketen →
of parameter d bij Bird. Elke volgende ruimte ,{k2}
in Eva loopt een dimensie achter bij die van de Conway-Knuth →↑{k}
superpijlen en opent een parameter op de rij van Bird.
In multidimensionale expressies van systeem Birdy noteren we vrijwel even grote getallen als met Bird's multidimensionale arrays, maar Birdy's definitie is simpeler en de evaluatie van expressies verloopt stapsgewijs.
Tot de functie recursie regel 4. is de definitie van Birdy dezelfde als voor de rij, maar de tekst vorm X kan elke toegestane multidimensionale passage bevatten.
Omdat eerdere regels voorrang krijgen, zijn er op de scan tic `
hier alleen nog reeksen ,[mi]1..
afgetelde cellen te verwachten in meerdere dimensies, met separator indices mi>0
en als eerste index ,[1]
de gewone ,
komma.
Opladen met regel 5b. onder separatoren met index in Birdy is vergelijkbaar met oplaadregel 2b. voor dimensies in systeem Adam. Maar de in Birdy uitgedrukte getallen worden door subexpressie recursie dimensionaal groter.
Separator eliminatie met regel 6a. is alleen nodig, als we de vorm van opladen op de rij 5a. overslaan en daar de dimensionale vorm 5b. toepassen.
Afgetelde cellen in tussenliggende dimensies laten we in Birdy net als in Adam gewoon staan. Lengtes en maten nemen zodoende cummulatief toe en worden steeds allemaal opnieuw opgeladen. Maar al deze extra ruimte blijft insignificant vergeleken met elke daarboven opgeladen teller, die stapsgewijs een dominant grote ruimte toevoegt. Wel of niet opruimen verandert de uitkomst vrijwel niet.
De dimensie index ,[m]
van de separator komma kan worden verlengd tot een rij ,[m.,ni..]
van index variabelen. Een structuur of getalruimte met deze hierarchie van separatoren noemt Bird de hyperdimensionale array.
Op hun beurt kunnen separatoren in index arrays weer met een volgende index of rij worden uitgebreid. Zo nesten we rijen in eerdere rijen tot elke mogelijke diepte. Zo'n systeem voor grote getallen noemt Bird “geneste arrays”.
Bouw een structuursom van geneste arrays op door nieuwe separatoren toe te voegen en rond daarbij alle maten gelijk af tot n, dat wil zeggen de variabele waarden en rij lengtes, die op dat niveau ondergeschikt zijn.
Begin door op de rij met alleen komma ,
separatoren een som =>
van een n aantal variabelen n op te tellen.
, => n*n ,[2] => n^3 ,[m] => n^n
De structuursom van de multidimensionale array is aldus een macht.
Elke volgende separator schept ruimte voor n keer de vorige som.
,[1,1] => n^n1 ,[m,1] => n^nn ,[m,n] => n^(n*n)
De eerste index doet de som n^n
keer. Met elke volgende index wordt de vorige index vermenigvuldiging n keer herhaald.
,[m,1,1] => n^(n*n1) ,[m,n,1] => n^(n*n*2) ,[m,n,n2] => n^n^3
Volgt de structuursom met de eerste geneste rij in hyperdimensionale arrays.
,[m.,ni..] = ,[,[2]1] => n^n^n ,[m,[2]1] => n^(n^n+n) ,[m.,ni..,[2]1] => n^(n^n*2)
Elke index stap rechts op een voorgaande index structuur herhaalt dus de toegevoegde exponent van de vorige som.
,[,[2]3] => n^(n^n*3) ,[,[2]m] => n^n^n1 ,[,[2]m,1] => n^(n^n1*2)
Zodat elke rechtse index variabele 1
telt bij de dubbele exponent en elke extra index rij dus n daarbij optelt, wat de som geeft van het index vlak.
,[,[2]m,n] => n^n^n2 ,[,[2],[2]1] => n^n^nn ,[,[2],[2],[2]1] => n^n^(n*3)
Vervolg de derde index dimensie door rechts lagere structuren te plaatsen.
,[,[3]1] => n^n^n^2 ,[,[3]m] => n^n^(n^2+1) ,[,[3],[2]1] => n^n^(n^2+n)
Dezelfde index dimensie opbouwen herhaalt de hoge exponent in de som.
,[,[3],[3]1] => n^n^(n^2*2) ,[,[4]1] => n^n^n^3 ,[,[m]1] => n^n^n^n
De tweede niveau index telt dus de tetratie n^^4
als som. Vergelijk de eerste index ,[m]
met som n^^2
en de eerste index rij ,[,[2]1]
daartussen met n^^3
als som.
Als dat zo doorgaat dan telt de tweede geneste index rij de tetratie n^^5
op.
,[,[m,1]1] => n^n^n^nn ,[,[m,n]1] => n^n^n^n^2 ,[,[,[2]1]1] => n^n^n^n^n
Als de structuur rechts op het eerste index niveau een index [L,n]
extra krijgt, dan telt dat 1
bij de derde exponent. Gebeurt dit op het tweede geneste niveau, dan telt dat 1
bij de vijfde exponent.
,[,[,[m]1]1]1 => n^^6 ,[..2..]1 :t: => n^^tt- ,[..m..]1 :t: => n^tt
De som van de hele ruimte van rij in rij geneste arrays volgt dan als tetratie. Met een even toren (van exponenten) bij een enkele index binnenin en een oneven toren bij een rij met een aantal indexen binnenin.
Om variabelen te ordenen in meerdimensionale arrays gebruikten we in Adam een index ,[m]
bij de komma en in Eva reeksen ,{m}
komma's. Zo kon Eva met maar twee tekens getallen uitdrukken ter grootte van Bird's lineaire array.
Vergelijk meervoudige separatoren met telbare elementen, zoals voorgesteld voor Eva, versus <=>
de gebruikte indexering in systeem Adam.
Bij de hyperdimensionale arrays wordt op het eerste geneste array niveau in Adam aan de komma een rij van indexen gehecht. Dezelfde hyperruimte kan worden onderverdeeld door seperatoren bestaande uit telbare komma's met een tweede type separator ,[2]
ertussen, hier links in Eva.
,{m} <=> ,[m] ,{m},[2],{n} <=> ,[m,n] ,{m}.,[2],{ni}.. <=> ,[m.,ni..]
Om deze opbouw te vervolgen maken we in dit hoofdstuk alle komma met index elementen ,[2]
ook telbaar in Eva. Aan de dubbel geneste indexen in Adam ontspruit een even grote verzameling separatoren. De ruimte van deze arrays zouden we multidimensionale hyperdimensies kunnen noemen.
L,[2],[2]R <=> ,[L,[2]R] ,[2],[2],[2] <=> ,[,[3]] ,[2].. :m <=> ,[,[m]]
Deze groeiende elementen verdelen steeds links L en rechts R de voorgaande subruimte in de separator. Bij Eva is dat in de komma elementen serie, versus in de vooronder geneste index array bij Adam.
L,[3]R <=> ,[L,[,1]R] ,[3].. :m1 <=> ,[,[m,1]] ,[n2].. :m1 <=> ,[,[m,n]]
Eva's eerste telbare index vormt dezelfde ruimtes als de tweede enkele index in de dubbel geneste array van Adam. Dan volgt de tweede telbare index in Eva, eerste nest, versus de derde index in Adam, tweede nest.
L,[1,2]R <=> ,[L,[,0,1]R] ,[1n,2].. :m1 <=> ,[,[m,n,1]] ,[1n1,1n2].. :m1 <=> ,[,[m,n1,n2]]
Volgende komma indexen lopen parallel in Eva telbaar in het eerste nest, versus Adam enkel in het tweede nest. Adam's index dimensie teller m is de laagste variabele en deze ontbreekt bij Eva, zodat de index rij in Eva 1
korter uitvalt.
,[.1,..2] :p <=> ,[,[.,0..,1]] :p
,[.1ni,..1].. :p :m1 <=> ,[,[m.,ni..]] :p
De eerste index rij van meervoudige separatoren blijkt equivalent te zijn aan de tweede geneste index rij met enkelvoudige separatoren.
Elke geneste array kan op dezelfde manier in ruimtes worden onderverdeeld. Eén index niveau in Eva met telbare separatoren valt steeds gelijk uit met twee niveau's in Adam met enkelvoudige.
Dus geldt voor alle geneste index rijen in Eva versus Adam.
,[..Q1..].. :q: :m & Q = ni,.. :p <=> ,[..m,Q..] :qq:
Een geneste arrays met telbare separatoren zal met een soortgelijk algoritme even grote getallen maken als een geneste arrays met enkelvoudige separatoren. Maar het aantal nest niveau's is de helft als separatoren op alle niveau's telbaar zijn.
Helaas is dit geen belangrijke verbetering, het verschil bedraagt slechts een factor 2
qua nest diepte. Met in het systeem vervolg een diepte teller die oplaadbaar is, wordt dit verschil insignificant.
Conclusie is dat telbare tekens aanvankelijk belangrijk zijn, te beginnen met de 1..
natuurlijke getallen en eventueel met ,..
komma's voor array dimensies. Maar dat array functies met enkelvoudige separatoren, enkelvoudige haakjes, etcetera, “oneven” zo snel over de geneste niveau's gaan, en na uitbreiding in de diepte ongeveer net zo snel.
Als meervoudige tekens geen voordeel dienen, houden we regels voor recursies en structuur elementen liever simpel, door alleen te tellen met variabelen. Zulke systemen groeien door grotere structuur concepten te herkennen, en deze als voorheen recursief te herhalen vanuit de basis som.
Het opladen van indexen in een geneste array noemen we “inladen”. Daar zijn wat problemen mee, zodat we de regels ervoor secuur moeten bepalen.
Het eerste probleem is, dat het inladen van een subtotaal niet in een passieve index array met een lege teller erboven mag gebeuren. Want dan zou de opgebouwde som, de q in dit voorbeeld, verloren gaan.
a,b1,[1,1]1 = a,a,[,1]b,[1,1] = a,a,[a-,]b,[1,1] == a,q,`,[1,1] ≠ a,a,`,[q,]
Om dit te voorkomen moeten we separator index arrays opruimen, als de iterator ervan is afgeteld en die separator de laatste is binnen zijn ouder array of rechts in de expressie.
Dit geldt eigenlijk alleen als die index arrays een actief separator-iterator element bevatten, zoals de ,1
in de subarray ,[1,1]
rechts in het voorbeeld. Maar het is mooier en makkelijker om ook de afgetelde dimensionale separatoren ,[m]
en enkele komma's ,
te verwijderen, die op het eind van de ouder array komen.
Zolang er in de ouder array nog een actief element volgt, worden lege iteratoren vanzelf opnieuw opgeladen, dus hoeven we deze niet op te ruimen.
Merk op dat Bird ervoor kiest om afgetelde separatoren te verwijderen, als deze links voor een grotere staan. Maar we vinden het te bewerkelijk om alle soorten index arrays qua grootte te moeten kunnen vergelijken.
Het tweede probleem
Definitie Adam systeem A. met geneste structuur III. voor het nesten van rijen separator indexen.
De regels gelden in volgorde: de eerste vorm van links die past, evalueert de expressie naar rechts.
Een l-r scan `=
selecteert de eerste vorm vanaf de linker kant in de expressie, en kan op de spatie
een fragment overslaan. Als een tweede vorm in de regel volgt, selecteren we de eerste match ervan (na de eerste vorm) in de expressie, mogelijk te vinden in een geneste array. In het overgeslagen passieve tekst fragment bevindt zich dus zeker geen match.
Zo komt de selectie van een r-l regel met =`
direct rechts in expressies.
Bij een regel met gelijk teken =
selecteert de vorm een hele expressie.
Met substitutie equivalentie ≡
kan de vorm overal te vinden zijn.
Teken 0
staat voor een evaluatie waar de selectie vorm geheel vervalt.
Een expressie in Adam kan eventueel tussen ronde A()
haakjes staan.
De tekst variabelen S zijn gesloten, zodat elk open haakje erin van een geneste index array [Si]
gepaard is aan een sluit haakje.
Ons “rechts binnen” criterium is simpel te constateren. En we slagen er goed in, om alle inactief blijvende elementen te elimineren. Waarna regel 1. de uitkomst geeft. Opruimen met regels 4. moet wel tijdens de evaluatie plaatsvinden, met voorrang boven regels 5. dus.
Eva moet een systeem worden, dat met zo weinig mogelijk tekens en eenvoudige regels zo groot mogelijke getallen uitdrukt. Eerst nog bouwen we Eva's telbare komma's voor dimensies uit naar een rij hyperdimensionale indexen. Bij dieper geneste arrays zetten we het systeem over naar de bekende index variabelen.
Bird noteerde zijn hyperdimensionale arrays met separatoren bestaande uit een rij index variabelen, de eerste van zijn geneste arrays.
We zagen in $.7.3.1 al hoe de rij indexen van Adam ook met aantallen komma's kan worden weergegeven en dan dezelfde ruimtes voor variabelen schept. Hier vervolgen we het dimensionale systeem IIa. van Eva en introduceren de enkele punt komma ;
als separator tussen de reeksen van komma's.
Definitie systeem Eva E. voor de eerste geneste rij IIb. met telbare komma's als hyperindexen. Pas die `=
regel toe, die een vorm selecteert die het meest links in de expressie begint.
De reductie van expressies verloopt dan zo.
a,b1,`,,;,,;,,2 4,2= a,1,`,;,,;,,ab 3= a,1,`,{a1};,;,,ab == a,c1,`,{a1};,;,,2 4,2= a,1,`,{a};,;,,ac == a,d1,`,,;,;,,2 4,2= a,1,`,;,;,,ad 3,2a= a,1,`,;,{a1}ad 3= a,1,`,{a1};,{a}ad
Er ontstaat een probleem. De komma reeksen in de separator worden steeds met de constante a opgeladen en niet met de groeiende subtotalen, hier met b<c<d
in de evaluatie trein aangegeven.
Want op het moment dat een komma index of aantal tot 1
wordt afgeteld, schuift het subtotaal naar de variabele erboven. De uitkomst blijft zodoende klein.
Het algoritme van Adam of Eva kopieert alleen de constante en nergens het subtotaal. Dit kan alleen werken, als een geneste array wordt opgeladen door de iterator of index, die rechts in de array erboven staat. De regel daarvoor moet duidelijk maken waar de separator structuur precies eindigt, wat niet triviaal is.
Bij meerdere niveau's van arrays zal de subtotaal waarde zich trapsgewijs naar binnen toe verplaatsen. Het geeft geen pas daar in Eva steeds de constante a bij op te tellen.
Voor geneste arrays in het algemeen in Eva stappen we over op het komma index systeem van Adam. Definitie Eva systeem E. voor geneste rijen III. met regels in volgorde.
..
We kiezen er bij het opladen in Bodhi systeem Bo. voor om subtotaal b te laten staan, om daarna de eventueel afgetelde indexen voor zijn rekening te nemen. Dit lijkt het simpelst, maar betekent dat er een kopie van b moet worden gemaakt om in te voegen.
De voorafgaande reeks afgetelde iteraties wordt daarna ook met het grote subtotaal b gevuld. Maar toch zijn Bodhi's uitkomsten niet significant groter dan die bij Bird of Birdy, waar de ruimte links met de kleine a wordt gevuld.
Regel voor het opladen van afgetelde variabelen ,1
op de eerste rij. Stel k>0
voor het aantal lege cellen, zodat c=1
als eerste kan opladen.
Herhaalde toepassing ==
van deze regel vult het hele afgetelde deel links in de rij stapsgewijs met kopies b>0
van het subtotaal.
== Bo(a,1b,1.b,..1X) :k = Bo(a,$.,b..,1X) :k
We kunnen in evaluatie voorbeelden de gebruikte regelnummers aangeven.
Ook expressies B(a,1,1)
en B(a,1,1,R)
waar regel 3. geen match voor vormt, kunnen onder regel 5. vallen.
B(a,1,1,2,3) 5= B(a,1,1,1,3) 5== B(a,1,1,1,1) 1== B(a) 2= a
Zulke expressies ontstaan nooit in de evaluatietrein en hebben als input weinig zin. Altijd is die expressie triviaal te herleiden tot a.
Vergelijk Birdy B. met Bodhi Bo.
B(a,b1,2,2) ~> Bo(a,b1,2,2) <- (a,3,..a..1) :b:
Omdat:
B(a,b1,2,2) = (a,(a,b,2,2),1,2) := (a,(a,b,2,2),(a,b,2,2)) <- (a,(a,a,(a,b,2,2)),(a,b,2,2)) =: (a,3,(a,b,2,2)1) == (a,3,..a..1) :b:
..