Boek 1:
_
Grote natuurlijke getallen
_
Boek 2:
_
Bovennatuurlijke getallen ψ
$ 1. Getallen
De "googologie" of wiskunde van de grote getallen
begint met eenvoudig tellen.
Op de vingers van een hand en zo maar voort.
$ 1.1. Tellen met 1 en basis 10
Voor natuurlijke getallen, tel 'een' 1
op tot het aantal 1.. enen.
Voor negatieve getallen,
zet links een factor 'min' -
of tel de minnen -.. van rechts op.
Tel in een repetitie, die 1 selecteert
en op zijn .. plaats een aantal :n
keer herhaalt, tot al die enen gelijk =
zijn aan getal n uit de 'rep' en het tellen stopt.
Of begin met het getal 'nul' 0
dat niets is, en stop zonder te tellen.
1.. :0 = 0
1.. :n = n
Schrijf de getallen van 'twee' tot 'tien'
met cijfers 2,3,4,.. en definieer ze met enen.
Zet deze ook om =>
in binaire notatie met 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
In een basis systeem of radix r
lopen de cijfers van 0 tot r-
en hebben aparte tekens.
Daarna komt 10 als de eigen basis
en de verdere samenstellingen.
De lengte van getallen in een basis
wordt door de extra tekens bekort.
Zo is ieder natuurlijk getal <r^k
op unieke wijze gegeven met maar <k cijfer plaatsen.
Schrijf een getal in basis r als een reeks digits d
en vertaal deze terug als factoren *
van oplopende machten ^ van r
die in serie worden opgeteld.
d_i.. k:0 <=
d_0.+d_i*r^i.. 1:k
De index i neemt elke volgende stap toe of af
met 1 zoals 'l-r' van links naar rechts
aangeduid in de 'rep'.
De waarde van de cijfer plaatsen loopt 'l-r' af
(het grootste cijfer getal vooraan),
maar de constructie van getallen via
herhaalde vermenigvuldiging van 10 moet wel oplopen.
Derhalve is behalve de historische herkomst
van de cijfers ook de 'r-l' richting
van decimale getallen Arabisch te noemen.
In basis 'zes' is het getal 555
hetzelfde als 215. in basis 'tien'.
Maar als de bases onbekenden zijn,
zou je die dan kunnen berekenen..?
$ 1.2. Fysieke getalgaten
Grote getallen zijn kort weer te geven
in wiskundige expressies, die met behulp van regels
te evalueren zijn tot een aantal enen.
Expressies bestaan uit speciale tekens
voor operaties of functies, en ook de definitie
van regels in een algoritme vereist een zekere notatie.
Ons reisplan is om wiskundige constructen
en hun relaties te herkennen
en te herhalen tot in het oneindige.
Doel van de googologie is om met een minimaal
aantal tekens en zo beperkt mogelijke regels,
zo groot mogelijke getallen te noteren.
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 ons 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 ons 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 ons reisverhaal over de getallen
is dus volstrekt nutteloos, hopelijk, duimen maar!
$ 1.3. Googol en googolplex
Als groot getal noemen we de "googol",
te schrijven als 10^100 met exponent,
of in onze 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 ons heelal 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.
$ 2. Supermacht operaties
De wiskunde stelt dat een supermacht de herhaling is
van een aantal vorige macht of supermacht operaties.
Hier telt ^{c>0} het aantal carets en onze 'rep'
herhaalt de text links van .. in totaal b keer.
a^{c+1}b = a^{c}..1 :b
Wat stapsgewijs als volgt kan worden gedefinieerd.
Waarbij *{c≥0} ook de vermenigvuldiging
tot een serie van directe optellingen kan reduceren.
a*{c1}b1 = a*{c}(a*{c1}b)
== a*{c}(..a*{c1}1..) :b:
≡ a*{c}..a :b
Supermacht operaties ^{c} of *{c1}
zijn rechts associatief, dus deze expressies
worden verder van rechts naar links uitgewerkt.
Hier evalueren we de supermachten
met onze nieuwe "popster" operaties.
Deze sluiten nauw aan bij een primitief recursieve
functie voor supermachten over een rij variabelen.
We zullen ons popster systeem langzaam opbouwen.
$ 2.1. Rekenoperaties
Met de eerste supermachten *{k<3}
kunnen we rekenen.
Dit zijn de operaties van optellen *{0}
en vermenigvuldigen *{1}
en machtsverheffen *{2}
waarvan ook de inversen en vele reële
en complexe getallen bekend zijn.
$ 2.1.1. Optellen is 0
Bij variabelen met natuurlijke getallen a en b
die naast elkaar staan, is meteen de som ab gegeven,
waarin alle enen 1.. bij elkaar optellen.
We plaatsen 'plus' + tekens tussen getallen
om optellen uit te stellen.
- +a+b =` +ab
- a+b = ab
Door deze regels • voor optellen
consequent vanaf rechts toe te passen,
komen de wachtende operaties beschikbaar
en kan hun + wegvallen.
Het "is gelijk" teken = drukt gelijkheid uit
en betreft de evaluatie van hele expressies
of subexpressies (binnen haakjes).
Het "is rechts" teken =`
selecteert vanaf rechts in de expressie.
Daarmee werken we operaties 'r-l' uit,
reducerend van rechts naar links.
Zo werken we een optelling tot getal stapsgewijs uit.
1+1+1+1 = 1+1+11
= 1+111 = 1111 ≡ 4
De actieve plus operatie is te beschouwen
als *{0} nulde superster, die leeg is.
Alle operaties rechts van een plus teken
krijgen voorrang, maar ook elke hogere operatie
die links ervan staat.
$ 2.1.2. Vermenigvuldigen is 1
Vermenigvuldigen is herhaald optellen
van een constant a.. getal.
Het keer of maal teken ertussen
schrijven we met een * ster.
Definitie van vermenigvuldigen voor gehele getallen.
Stel b>0 zodat de tweede regel in de laatste stap
de iteratie overneemt van de eerste regel.
- a*b1 =` a*b+a
- a*1 =` a
Vindt een match vanaf rechts =`
in de expressie voor de vorm links in de regel.
Iedere iteratie stap telt een constante a op bij de som.
Herhaal de reeks stappen ==
in combinatie met optellen, tot de laatste stap
de operator elimineert en de uitkomst levert.
a*b1 = a*b+a
== a*1+.a.. :b
= a.. :b1
De 'rep' :b herhaalt de tussen .
of terzijde van de punten ..
geselecteerde passage b maal.
Reps zijn beschrijvend bedoeld en niet regelgevend.
Een voorbeeld van vermenigvuldiging als optellen in stappen.
Neem de vertaling naar decimale getallen hier voor lief.
2*3 = 2*2+2 = 2*1+2+2
= 2*1+4 = 2+4 = 6
De iterator is hier 111
en in het algemeen een variabele b
waar elke stap 1 vanaf telt
om een kopie van a op te sommen.
De ster van vermenigvuldigen
is de eerste superster operator.
$ 2.1.3. Machtsverheffen is 2
Machtsverheffen ** of ^
is herhaald vermenigvuldigen.
Om machten stapsgewijs uit te werken,
met de lagere operaties eerst,
moeten we de hogere in de wacht zetten.
De 'pop' plus in popster *+ operaties
stelt vermenigvuldiging uit.
Alsof het tussen haakjes staat, met maar één plus teken,
tot het getal klaar is en de ster ontpopt.
Evalueer popster machten volgens deze speciale definitie,
waar b>0 .
- +a*+b =` +a*b
- a*+b = a*b
- a**b1 =` a**b*+a
≡ a*..a :b
- a**1 =` a
We hebben de regels in een volgorde gezet, die het mogelijk
maakt om deze definitie op twee manieren toe te passen:
hetzij door de bovenste toepasbare regel uit te voeren,
hetzij de regel die meest rechts in de expressie aangrijpt.
We gebruiken het equivalentie teken ≡ 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 ons popster systeem in a^b+1
één op bij een factor, maar in 1+a^b
gewoon bij het totaal.
Volgt een ster *+ met pop plus,
dan komt die gewoon als factor bij de reeks factoren.
Deze regels werken zonder precedentie
en evalueren strikt 'r-l' vanaf rechts,
wat vreemde resultaten geeft
als we ster operaties op elkaar schrijven.
2**3*2 = 2**3*1+3 = 2**3+3
= 2**2*+2+3 = 2**2*+5
= 2**1*+2*+5 = 2**1*+2*5
== 2**1*+10. = 2*+10.
= 2*10. == 20.
We kunnen het ook anders regelen:
om carets ^ met meerderheids-precedentie
op te lossen (hogere operaties met meer tekens eerst),
en daarna sterren * met minderheids-precedentie
(voorrang aan minder tekens).
Dan zou 2**3*2 = 2^6 groter zijn,
maar 2^3*2 = 8*2 kleiner.
$ 2.2. Popster supermachten
Door extra sterren * in de operator zetten,
of met een superfactor {c} weer te geven,
noteren we moeiteloos enorm grote getallen.
De macht operant b die groeit in de evaluatie,
drukt steeds een reeks vorige operaties
met constante a uit. In ons systeem
met popsterren worden die torens niet afgebouwd;
de top operaties komen apart te staan
en werken we eerst uit.
$ 2.2.1. Definitie
De volgende operatie met *** sterren of ^^ dakjes
heet "Tetratie" en geeft een aantal machtsverheffingen,
equivalent aan een toren van exponenten
die 'r-l' vanaf rechts moet worden opgelost.
a***b1 = (a***b)**a
== (..a^^1..)^a :b:
= a^..a :b
Operatie na operatie kunnen we zo supermacht expressies
bouwen met ieder aantal operator tekens.
In wezen een dubbel recursieve operatie
over twee variabelen, met als beginwaarden
iterator b=1 en *{c=0} voor direct optellen
(of nul dakjes voor historisch vermenigvuldigen).
Definitie om 'PopSter' supermachten
te evalueren tot natuurlijk getal.
Steeds geldt b>0
maar de operator *{c≥0} kan leeg zijn.
-PS.1a. +a*{c}+b =` +a*{c}b
-PS.1b. a*{c}+b = a*{c}b
-PS.2. a*{c1}b1 =` a*{c1}b*{c}+a
-PS.3. a*{c1}1 =` a
We voeren die regel uit, die een match geeft
op de meest rechtse =` positie in de expressie.
Maar in de evaluatie van een supermacht blijft dit
hetzelfde als voorrang geven aan de bovenste regels.
Variabelen zijn "gretig" naar enen,
zodat elke getal a in de regels compleet is,
zonder rest deel in de expressie.
Stap 2. ster operatie introduceert
kleinere popster met operant.
Trap 1. elimineert de plus
uit de rechts gelegen popster.
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.
Of als we een plus teken +X
voor alle popster expressies zouden zetten,
dan is een vierde regel +x = x
pas nodig bij de uitkomst.
$ 2.2.2. Evaluatie
Als voorbeeld werken we de macht 2**2
en de supermacht 2****3
uit met de 'PopSter' regels in stappen vanaf rechts.
We schrijven voor het gemak carets,
waarbij *{c1} en ^{c} gelijk zijn en strikt 'r-l'
rechts associatief met pops te evalueren.
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.
Alle supermacht expressies zijn met
twee type tekens, de 1 en * te noteren.
Tijdens de evaluatie komt daar de pop +
als solo haakje bij. Slechts drie tekens!
Dakjes ^ of carets en ^+ popcarets,
cijfers en tientallige getallen (met decimale punt)
nemen we erbij als afkortingen.
$ 2.2.3. Toepassingen
We kunnen sommige supermacht operaties
alleen ruwweg met elkaar vergelijken qua grootte.
In dit voorbeeld neemt het absolute verschil <
tussen twee ster supermachten bij grotere c toe.
Terwijl dit verschil in de context
van de hierdoor groeiende reeksen
klein begint met 1 en niet significanter zal worden.
2^{c}4 = 2*{j}..8 c:1 <
3^{c}3 = 3*{j}..9 c:1
De teller {c} geeft in krulhaakjes
het aantal tekens in de operator aan.
De repetitie c:1 noteert een reeks
waarin de indexen j naar rechts afnemen.
In de expressie a^{c}b1*{d}+e
ontpopt de iteratie van rechts als hoogste exponent
in de toren a*{c}..a*{d}e :b
wat significant kan zijn
en een aanvulling vormt op ons rekenapparaat,
om array functies nauwkeuriger te kunnen schatten.
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 zag de superoperator het licht,
met carets in de vorm van de pijlen ↑{c}
van Donald Knuth, in zijn essay
"Omgaan met eindigheid".
Maar dezelfde dubbele recursie φ_c(a,b)
inclusief Ackermann functie
was al te vinden bij David Hilbert, in zijn artikel
"Over het oneindige" uit 1925.
$ 2.2.4. Functie vorm
Evaluatie van supermachten kan makkelijker
met een functie!
Als we supermacht operaties a*{c}b
uitwerken volgens de 'PopSter' definitie
krijgen expressies deze vorm.
a*{c_i+1}b_i*{c_i}+..b_0 k:1
waar b>0 en c_i1>c_i≥0
Elke superster operatie telt daarbij een ster *
meer dan de erop volgende popster.
Deze sterparen nemen naar rechts af,
maar niet alle tussenliggende supersterren *{c}
hoeven in die reeks voor te komen.
Stel nu, dat we voor de ontbrekende supermachten
in die reeks een operant b=0 nemen
(een permanente nul), die zijn sterpaar reduceert
tot een wegvallende nul 01 = 1
(tegen de variabele erna) met een extra regel.
-PS.4. a*{c>0}0*{d}+ =` 0
Zo is de reeks van sterparen
die naar rechts toe aflopen compleet.
a*{i}b_i*{i-}+..b_0 k:1
En verloopt een uitwerking vanaf rechts
bijvoorbeeld via:
2^^^^1^^^+2^^^0^^+2^^2^+2^0*+2*0+1
= 2^^^^1^^^+2^^^0^^+2^^2^+1
== 2^^^^1^^^+2^^^0^^+4
= 2^^^^1^^^+4
= 2^^^+4 = 2^^^4
== 2^^65536. ≡ 2^..1 :65536
Omdat alleen de operanten b
en het aantal carets ^{c} of sterren *{c1}
variabel zijn en kenmerkend, is het overbodig
om de constante a voortdurend aan te halen.
Ook komt er van ieder sterpaar nu één voor,
in rangorde 'r-l' oplopend,
met de hogere supermachten links in de wacht.
Om tijdens de uitwerking een popster expressie op te slaan,
hoeven we dus enkel de constante a
en alle variabelen b_i in volgorde te noteren.
2^^^^2^^^+ 2^^2
2^^^^2^^^+2^^^0^^+2^^2^+2^0*+2*0+1
2^^^^2 ^^^0 ^^2 ^0 *0+1
2 2 0 2 0 0 1
2, 1,0,0,2,0,2
Alle essentiële data is hier met zeven getallen gegeven.
En we draaien de rij met zes variabelen ook om,
zodat de evaluatie 'l-r' in leesrichting kan verlopen.
De achterste pop +1 is eigenlijk alleen
voor de vorm en kan in de functie
door een andere regel worden ondervangen.
Getal 0 schrijven we zonder enen.
Dan toont deze popfunctie,
dat het aantal supermachten *{k}n steeds 1
verschilt met het corresponderende aantal
komma's ,{k1}n links in de rij.
2*{6}3 = 2*****2****+2***2
11,{7}111 = 11,,,,11,,11
Zo zetten we supermacht expressies om naar
een rij structuur, met nog maar twee tekens
en een veel kortere expressie lengte.
De regels voor de evaluatie
van een dergelijke functie zijn simpeler
en zien we in het volgende hoofdstuk.
$ 3. Rij functies
De systemen in dit hoofdstuk beperken zich tot
een eerste rij met variabelen,
als beginplan voor het maken van grote getallen.
We ontwerpen hier twee nieuwe primitief recursieve
functies, die de supermachten uitdrukken.
Ook bespreken we de bekende notatie systemen
van Conway's pijlketen en Bird's lineaire array.
In hun snelle recursieve functies
worden subexpressies meteen genest,
zodat supermachtsverheffen al met twee variabelen kan.
$ 3.1. Systeem Adam
Systeem 'A' voor "Adam" of "Amsterdam"
krijgt over zijn eerste rij de functie vorm
van de popster supermachten uit het vorige hoofdstuk.
Thema bij de constructie van Adam is,
dat iteratoren en structuren worden afgeteld tot 0
of eigenlijk tot deze leeg staan.
$ 3.1.1. Primitieve recursie
Om zo zuinig mogelijk te zijn met type tekens,
substitueren onze functies geen subexpressies (X)
maar getallen. Ronde haakjes zijn hierbij niet nodig
en de regels staan dus geen "functionele recursie" toe,
waarbij een afgetelde functie expressie
terugkeert in de input variabele.
Rij expressies bestaan uit getallen met tekens 1
en komma's , ertussen als separator.
Als variabelen afgeteld zijn, laten we de 0 weg.
Als "primitief" geldt het optellen van de constante a
en het opschuiven van de variabele b over de rij,
wat "opladen" heet. Dit is de getal opbouw.
Beide regels tellen 1 af van een hogere iterator
(of schrijf min - bij), rechts van de
in te vullen positie. Dit is de expressie afbouw.
We herhalen deze stappen "recursief", waarbij een
vorige herhaling het aantal volgende herhalingen bepaalt.
Tot een natuurlijk getal n wordt uitgedrukt,
als een serie enen 1.. :n van die lengte.
We kunnen alle supermacht expressies evalueren tot getal,
door slechts twee tekens te gebruiken
en drie primitief recursieve regels.
$ 3.1.2. Definitie 'A.I'
Definitie van "Adam" systeem 'A.' over structuur 'I.'
van een rij variabelen,
met regels voor de selectie en evaluatie
van supermacht expressies.
De variabele b≥0 en het aantal komma's ,{k≥0}
mag nul zijn, zonder teken, en ook text variabele R
voor het deel rechts kan leeg staan.
-A.I.1. a,b,1R = a,ab,R
-A.I.2. a,b1,,{k},1R = a,,1,{k}b,R
1= a,a,,{k}b,R
-A.I.3. a,b,{k} = b
Regels met = selecteren de hele expressie.
Gedurende de evaluatie is steeds precies één
van deze regels toepasbaar.
Expressies van 'A.I' blijven congruent
aan die bij de evaluatie van de popster operaties,
zodat functie variabelen links als het ware
op de top operatie rechts worden gestapeld.
Maar de regels werken anders.
Regel 1 telt de constante a op in variabele b .
Regel 2 verplaatst het somtotaal van b
om een afgetelde iterator op te laden, maar laat 1
slim achter, zodat a optelt in de volgende stap.
Regel 3 neemt getal b als uitkomst
en stopt de evaluatie.
De uitgetelde rij structuur rechts
mag tot op het laatst blijven staan.
Alleen expressies van de vorm a,,,{k>0}1R
zijn niet reduceerbaar en vallen buiten systeem 'A'.
We bieden daar een oplossing voor
met de volgende systeem varianten,
waarin ook de lege structuren rechts eerder wegvallen.
$ 3.1.3. Variant 'Aa.I'
In de uitgebreidere definitie 'Aa.I'
worden de resterende komma's van afgetelde variabelen
meteen vanaf rechts opgeruimd.
In plaats van een text variabele gebruiken we
het scan teken ` voor een passieve passage
tot op het eind rechts.
Stel b≥0 bij het somtotaal.
Waar :k>0 een aantal afgetelde variabelen ,0 tussenin
herhaalt, wat we hiervoor noteerden met lege ,{k} komma's.
-Aa.I.0. a,`,0 = a,`
-Aa.I.1. a,b,c1` = a,ab,c`
-Aa.I.2a. a,b1.,0..,d1` :k
= a.,0..,b1,d` :k
-Aa.I.2b. a.,0..,d1`
= a,a.,0..d` :k
-Aa.I.3. a,b = b
In systeem 'Aa' kiezen we ervoor om expressies
met waarde b=0 onder c=0 gelijk te houden
aan die waar b=1 zou staan.
In het strikte systeem 'A' vielen expressies a,{k>2}1R
gewoon niet onder de regels, maar hier worden deze handig
gebruikt om een supermacht mee uit te drukken.
a*{c>0}b = a,{c1}b
De extra regel verandert de evaluatie niet.
Regel 2a en 2b van 'Aa' na elkaar toepassen,
geeft hetzelfde resultaat
als opladen en optellen in systeem 'A'.
$ 3.1.4. Variant 'Ab.I'
Een ander type definitie scant `=
de expressie vanaf de linker kant naar rechts,
tot er een match gevonden is, of faalt.
En we benoemen alleen die variabelen en structuren,
die om te selecteren en te wijzigen nodig zijn.
Een spatie in een regel betekent
het einde van het linker gedeelte van de match,
waarna de expressie doorzocht wordt
naar een match voor het rechter gedeelte.
Op de spatie zal de 'l-r' scan dus elke
andere passieve text overslaan.
Bij deze definitie van systeem 'Ab.I'
worden de regels strikt in volgorde toegepast.
Stel alle b≥0 en ruim de komma's
pas op als de verdere rij leeggeteld is.
-Ab.I.1. a,b,1 `= a,ab,
-Ab.I.2a. a,b1, ,1 `= a,,1 b,
-Ab.I.2b. a,,, 1 `= a,1,,
-Ab.I.3a. a,b, `= a,b
-Ab.I.3b. a,b = b
Speciale expressie a,,{k>1}2R
evalueert nu tot a,a,{k}R
en telt dus een iteratie stap meer af
dan in systeem 'Aa'.
Dit is rekenkundig juister.
Schrijf in 'Ab' dus altijd b=1
om een standaard supermacht uit te drukken.
$ 3.2. Adam supermachten
We vergelijken de evaluatie in functie 'A.I' met de
popster
operaties. Na wat rekenen ermee volgt
de algemene vorm van zulke vergelijkingen.
$ 3.2.1. Tetratie in rij van vijf
Voorbeelden met drie tot vijf parameters
in systeem 'A.I', die equivalent zijn aan popsterren *
tot *** die tot tetratie komen.
Van functie regels `= tonen we de nummers
links van het evaluatie teken
en van de popster regels =` rechts.
Evaluatie van optellen en vermenigvuldigen.
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 machten in 'A.I' en popsterren.
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,, == a^d2
3= a^d2
Gebruik ster operaties in de variabelen
om het functie algoritme te begrijpen.
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^d*(a*c+b)
De iterator e van tetratie domineert
de kleinere rekenoperaties.
Als deze niet veel groter zijn dan a
dan telt dit ongeveer twee exponenten
erbij e2 op.
a,b,c,d,e
= a,a^d1*c1,,,e {b=a}
≡ a,1,,a^d2,e- {c1=a}
= a,a^a^a,,,e- {d2=a}
== a^^e2
Precies gesteld zo. Of als d~a dan ronden we
een rij van vijf in 'A.I' net zo af.
$ 3.2.1. De rij als reeks popsterren
Met een reeks lege komma's ,{k} op de Adam rij
drukken we direct het aantal sterren *{k}
van een supermacht uit.
a,1,{k1}2p_k
= a,a,{k1}1p_k
= a,a,{k}a-,p_k
== a,a*{k}a,{k1}p_k
= a*{k1}(p_k+2)
Elke voorliggende parameter p in de functie rij
is zelf een supermacht a*{k1}p ofwel a^{k}p
en vormt een popster operatie bovenop
de hoogste exponent van de supermacht
van een rechts volgende parameter.
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 superexponent.
a.,p_i.. 0:k
= a*{i}p_i*{i-}+..p_0 k:1
~ a*{k}(p_k+1)*{k-}+p_[k-]
~ a*{k}(p_k+2)
In het begin bij k<2
of als de voorlaatste p bijzonder groot is,
zal de afronding hiervan ~ afwijken.
Wat lastig is aan systeem 'A.I'
zijn de twee oplaadregels in serie:
het laag opladen van waarde a naar cel b
voordat hoog opladen van cellen weer mogelijk wordt.
Ook zou het zuiniger zijn om de tekenreeks ,{k>1}
in te zetten als dimensie separatoren
voor multidimensionale matrices.
Met de volgende functie lossen we dit op.
# 3.3. De rij van 'E.I.'
Systeem 'E.' staat voor "Eva" of "Eindhoven".
Het Eva systeem noteert zo groot mogelijke getallen
met zo min mogelijk tekens.
We tellen iteratoren en structuren niet leeg,
maar af tot "Een" 1 . Omdat die zo blijven staan,
kunnen we aantallen komma's later een eigen
betekenis geven als dimensie separatoren.
Definitie systeem 'E.I' voor de eerste rij,
met 2 tekens en 3 regels. Het ruimt de uiterst
rechts afgetelde variabelen meteen op.
-E.I.1. a,b = ab
-E.I.2. a,R,1 = a,R
-E.I.3. a,b.,1..,2R :k≥0
= a,a.,1..b,1R :k
Het 'E.' systeem drukt eveneens getallen uit
ter grootte van supermachten.
Maar de uitkomsten vallen niet precies samen met 'A.'
en lopen steeds verder uiteen.
Met de 4e regel wordt zowel de afgetelde iterator ,1
rechts opgeladen, als de andere wachtende ,1
links ervoor in de rij.
Eerst verladen we vanuit volle oorsprong a,b
de som ab en vervolgens
vanuit de lege oorsprong a,0 de constante a .
Met dezelfde expressie noteert functie 'E.I.'
wat kleinere uitkomsten dan de 'A.I.' rij,
maar dit is niet significant.
Regel 3 met :k=0 werkt zo dat a,b,c
vermenigvuldigt a*c+b en optelt.
a,b,1 2= a,b
1= a+b
a,b,c1 3= a,ab,c
== a,a*c+b,1
2= a,a*c+b
1= a*c1+b
Als we dezelfde regel aanhalen,
hoeven we die niet opnieuw te noemen.
a,b,1,d2 3= a,a,b1,d1
== a,a*b1,1,d1
= a,a,1+a*b1,d
== a,a*(a*b1+1),1,d
== a,.a*(..b..+1).,1,2 :d:
3,2= a,a,1+.a*(..b..+1) :d:
@= a,.a*(..b..+1). :d1:
~> a^d2 {b1=a}
Evaluatie met verwijzing @=
past een eerder resultaat toe.
Met :k=1 verwijdert Eva zich
herhaaldelijk van machtsverheffen.
a,b,c1,d 3= a,a+b,c,d
== a,a*c1,1,d {b=a}
@= a,.a*(..c..+1) :d:
~> a^d1 {c1=a}
Dus
a,b,1,1,e1 = a,a,a1,b,e1
@~ a,a^b1,1,1,e
~~ a,a^^e^+b1
~> a^^e1 {b1=a}
a,,1,1,e1 3= a,a,1,1,e
@~ a^^e
a,b,c,d,e {b=a c=a}
@~ a,a^d1,1,1,e
@~ a,a^^e^+d1
~> a^^e1 {d1=a}
De eerste rij 'E.I.' is uit te drukken als een reeks
popster operaties, waarbij elke variabele cel
een ster aan de operator toevoegt.
Hier geldt k≥0 .
a,.,1..,z :k = a*{k1}z
a.,p_i..,z 0:k =
a*{k1}z.*{j}+p_j.. k:0
~ a*{k1}z*{k}+p_k+1 met p_j~a
~ a^{k>0}z1
Met indexen i die van 0 tot k toenemen door 0:k
op variabelen in de functie, met indexen j
die van k tot 0 afnemen
door de k:0 rep van popsterren.
Deze volle rij kunnen we afronden ~ als hiervoor.
Een primitief supermacht algoritme kan ook in drie regels,
maar opladen telt dan steeds 1 bij.
Die uitkomsten nemen scheef toe
ten opzichte van de klassieke supermachten,
hoewel niet significant sneller.
Kies daarbij als derde regel:
- a,b.,1..1` :k1
= a.,1..,ab,1` :k of
- a,b.,1..1` :k>1
= a,..b,1` :k
Ons grote principe is om afgetelde hogere variabelen
consequent met lagere op te laden.
Ook bij Ackermann functies en in de grote getallen arrays
van Bowers en Bird (B&B) wordt dit principe toegepast.
Maar Ackermann verheft de constante a wat traag is.
En B&B verpakken somtotaal b
in een minimaal afgetelde expressie
alvorens die naar hogere regionen op te laden,
wat dan wel ingewikkelder is,
maar even maximaal snel als onze functies.
Rij lengte in 'E.I.' en 'A.I.' loopt gelijk
met de iterator c van een klassieke dubbele recursie
met functie substitutie in b en een constante a .
Door rij lengte vanuit de oorsprong op te blazen,
verlaten we de primitieve recursie en komen
op onze tweede rij al gelijk met Bird's lineaire array.
Over het array vlak zullen we zo
slechts 1 rij achterblijven.
Dit valt te bewijzen via de pijlketen van Conway,
die op de supermachten volgt.
# 3.4. Conway's pijlketens
Dubbele recursie is al gegeven in een functie
met één constante en twee variabelen
waarover die functie itereert.
Iedere iteratie stap substitueert
een minimaal afgetelde expressie,
waarmee de supermachten snel worden uitgedrukt
in drie variabelen.
Bij Conway's pijlketens vindt functie substitutie
vanaf rechts plaats, in de voorlaatste y variabele,
en bij Bird's lineaire array vanaf links
in de tweede b variabele.
Werk een reeks substituties in b uit,
samen 1 stap in de iteratie van c .
Laat het functie teken en de buitenste haken weg.
a,b1,c1 = a,(a,b,c1),c
== a,(..a,1,c1..),c :b:
= a,(..a..),c :b:
De eerste functie a,b,1 kan verschillen,
Hilbert
begint φ_1(a,b) met optellen
en de pijlketens van Conway a→b→1
met machtsverheffen.
In den beginne wordt steeds de constante a opgeteld.
Stel dat c=1 vermenigvuldigt,
en dat c=0 met a,b = ab optelt.
Dan werkt deze functie hetzelfde
als de linkse evaluatie van supersterren met haakjes.
a*{c1}b1 = a*{c}(a*{c1}b)
== a*{c}(..a..) :b:
Hier is 3,3,3 ofwel 3***3 het getal 7625597484987
al boven de biljoen (VS "trillion").
En dan loopt door substitutie het aantal subexpressies
wachtend tussen haakjes snel uit de hand.
- - - - - - - - - - - - - - - -
John H. Conway is de schepper van de pijlketen notatie,
die met twee enkele pijlen in a→y→z
dezelfde supermachten uitdrukt,
als Knuth a↑{z}y met al zijn pijlen.
De rechtse pijlen → zijn eigenlijk geen operatoren,
maar werken als separatoren ,
tussen de variabelen in een recursieve functie.
Stapsgewijze definitie van Conway's pijlketens,
met uitwerking == van 1 iteratie.
-CA.1. a→b = a^b
-CA.2. X→1 = X
-CA.3. X→1→z = X
-CA.4. X→y1→z1 = X→(X→y→z1)→z
== X→(..X..)→z :y:
Text variabele X staat voor a.→x_i.. :k≥0
het linker deel van de keten:
de constante a en een rij van iteratoren x_i .
Functie substitutie en aftelling
vinden plaats binnen in de voorlaatste cel y ,
terwijl van buiten de laatste iterator z aftelt.
Zo worden ketens diep genest,
terwijl de recursie over y→z
naar links schuift en uiteindelijk reduceert tot machten.
Scherp een voorbeeld aan uit het boek van
Conway en Guy.
Gardner's getal 3^{..3^{4}3..}3 :63:
van Graham ligt boven de 3→3→64→2
of 3→3→(..3^3..) :63: in pijlketen notatie,
maar onder 2→3→65→2
of 2→3→(..2→4→7..) :63:
zo te zien, omdat de top supermacht daarin
het grotere 3→3→7 vrijwel benadert
(zie sectie 1.2.c).
Bird's lineaire array gebruikt vier parameters
om even grote getallen te noteren
als Conway met zijn pijlketen rij.
Omdat we net als Bird het subtotaal
vanuit de oorsprong opladen, wat maximaal is,
komt er aan het begin van onze tweede rij een variabele,
die de lengte van Conway's hele keten zal benaderen.
- - - - - - - - - - - - - - - -
Systeem 'A.' kan op verschillende manieren
worden uitgebreid naar de tweede rij.
Neem als rij separator een komma met index ,[1]
tussen haakjes, tot [1] af te korten.
Een nieuwe regel kan met de eerstvolgende parameter m
gewoon de eerste rij lengte k vervangen,
of er bijvoorbeeld zo bij optellen.
- a,b,{k}[1]m = a,,{km}b
- a,b,{k}[1]m1 = a,,{k1}b[1]m
Direkt of in etappes, dat zal voor de grootte
van de uitgedrukte getallen weinig verschil maken.
Pas door [1]m,1 af te tellen tot [1],1
en op te laden met [1]b zal de rij lengte ervoor
door het somtotaal uit b worden opgeblazen.
Dat kan ook op een direkte manier, een parameter sneller,
met andere regels.
- a,b,{k}[1]c1
= a,,{b}a[1]c
= a,a*{b}a[1]c
== a*{..b..}a :c1:
- a,b,{k}[1]m1
= a,,{kb}2[1]m
= a,a*{kb}2,{kb}[1]m
De eerste regel werkt natuurlijker uit,
ongeveer als a→b→c1→2
en wordt hetzelfde genest als Graham's number.
Het bewaren van de lengte k van de bestaande rij
en opsommen ervan in het tweede voorbeeld
is minder relevant, omdat het subtotaal b domineert.
Definitie NB vlak,
waar b>0 en de lengte van de deelrij ` mag 0 zijn.
-NB.1. a,b = b
-NB.2.1. `, = `
-NB.2.2. `,[X] = `
-NB.3. a, ,1` `= a,a ,`
-NB.4. a,b, ,1` `= a,, b,`
-NB.5. ,,[X] `= ,[X]
-NB.6. a,b,[1]1` = a,,{b}a,[1]`
-MB.6. a,b1,[1]1` = a,b,,[1]1`
- Martin Gardner
Scientific American, Nov. 1977
# 3.5. Bird's lineaire array
# 4. Multidimensionale arrays
Een rij variabelen met natuurlijke getallen
noemen we de eerste dimensie, terwijl deze eigenlijk
bestaat uit rijen van rijen van enen.
Een reeks van rijen variabelen vormt dan een vlak
of tweede dimensie,
hoewel de rij lengtes daarin variabel zijn.
Herhaling van het vlak vindt plaats in een kubieke ruimte,
de derde dimensie.
We noteren al zulke array ruimtes op een lijn
in de expressie, waar ze van elkaar gescheiden worden
met specifieke separatoren.
We zouden door een aantal komma's na elkaar te zetten
simpel de dimensies kunnen aangeven.
a,b ,c_i..,,..,,,.. :d :e :f
Dit veronderstelt wel dat we variabelen
niet aftellen tot 0 maar tot 1 ,
anders zou de betekenis van opeenvolgende komma's
al vergeven worden op de eerste rij.
Alle ruimtes van een multidimensionale array
kunnen we door een aantal ,{k}
komma's laten scheiden, maar zou dat niet zonde zijn?
Het teken 1 hebben we gereserveerd voor variabelen.
Elk opeenvolgend aantal enen 1..
drukt een natuurlijk getal uit in de expressie, waarin
de functie van dat getal nader bepaald is
door zijn positie en het algoritme.
Stel nu dat de andere tekens die we toepassen,
zoals separatoren en haakjes paren, substituut staan voor
diverse aantallen van een ander wiskundig quantum,
ons "type teken" in abstracto, de nul 0 in concreto.
Bij de samenstelling van array elementen
zullen we steeds rekening houden met deze achterliggende
"array bit" notatie.
Die moet onze oplossing vormen
voor het Busy Beaver probleem,
althans ongeveer een maximaal getal schrijven
met twee (of meer) mogelijke tekens.
Vanuit de constructie van een evoluerend systeem,
zonder Gödelachtige alfabetisering,
maar gestaag groeiend.
Laat de komma , om getallen te scheiden
als variabelen, het ene 0 type zijn.
Er zijn verschillende manieren om ons systeem
economischer uit te breiden dan hierboven
met ,.. multipele komma's.
Maar welke is natuurlijker?
- - - -
Door op dubbele variabelen over te stappen .,c_i,q_i..
is het mogelijk om na elke even komma
rechts van de variabele c_i de dimensie overgang q_i
aan te geven, zonder extra 00 type teken.
Er links voor kan ook.
Om deze duo variabelen in de rij te herkennen,
geeft dit bij de expressie scan in het algoritme
helaas telproblemen.
Ook groeit zo'n systeem niet natuurlijk.
Het hinkt: eerst op één poot en dan op twee poten,
en later eventueel op duizend.
Door bij elke variabele
een vast aantal extra tellers te zetten,
behalen we de hyperdimensies in een rij.
Dit kennen we als de index rij bij de separator.
Of spreek net als Bird af, dat een getal tussen haakjes
de dimensie van de ruimte rechts ervan kenmerkt.
Door enkele komma's binnen de subarray te halen, breiden
Bird's multidimensionale uit tot hyperdimensionale arrays.
Zolang onze subarrays niet genest worden
en de scanner van eerste tot tweede teken kan tellen,
mag het beginhaakje dezelfde zijn als het sluithaakje.
Het bit type is dan 00 aan beide einden,
ook al gebruiken we in de expressie [ en ] .
En afgetelde subarrays [1]=,
evalueren meteen tot type 0 komma.
Bezwaar is hier, dat de tel bijhouden
niet echt een taak is voor de tekst scanner.
Een woord moet zonder de helft van de expressie
te doorlopen op elke plek herkend kunnen worden.
Lijkt op het voorbeeld hiervoor,
maar extra tellen kan hier niet,
omdat in elkaar nesten van gelijke haakjes verwarring geeft.
Juist is om twee typen haakje te gebruiken,
of hetzelfde type maar bij de opening
gebonden aan een separator teken.
Bird gebruikt krulhaken { en }
en breekt met het gebruik van enkele komma's ,
door te stellen dat deze in staan voor index 1 subarrays.
Zijn variabelen worden altijd tot 1
en niet tot 0 afgeteld,
zodat separator haakjes elkaar nooit zullen raken.
Zo bezien zijn Bird's haken van het type 0 en 00
en hij kan daar alle geneste arrays mee vormen.
Zijn afgetelde indexen worden steeds opgeladen
vanuit de oorsprong met subtotaal b wat optimaal is.
We mogen stellen dat gegeven deze beperkte tekens
de door Bird geneste getallen maximaal groot zijn.
De overgang van de komma uit Bird's lineaire arrays
naar zijn dimensie haakjes verloopt niet zo soepel.
We gaan liever van , naar ,[n]
met behoud van het separator teken,
waar het openingshaakje van de index array aan gekoppeld is,
ook al kan Bird ons een type voor blijven.
Onze opening ,[ telt als type 000
en sluit af ] met type 00 .
Schrijf eventueel de multidimensionale arrays
met een enkel haakje ,n]
om provisorisch even een type te besparen.
Na het vrije haakje ] dat de geneste array afsluit,
volgt de variabele die meter is van de ruimte ervoor.
We expanderen dit systeem
door binnen het separator construct
nieuwe en grotere array types te plaatsen.
Voor het type tellen we simpel 0..
de teken types na elkaar.
Vorm diepe arrays met overgangen ][
die als type 0000 scoren.
Het volgende diep [X][1Y] zal op die overgang
de afgetelde array ervoor tot grotere diepte nesten.
We maken dat ook staps-of druppelsgewijs mogelijk.
a,b1 ,[1][3]
`= a,a ,[1,[b1][2]2]
`= ,[1,[b][2]a,[b1][2]1]
`== ,[1,[1][2]a`]
`= ,[1,[1,[a][1]2]a`]
= ,[1,[1,[a]2]a`]
`== ,[1,[1,a`]a`]
`= ,[1,[a`]a`]
`== ,[a`]
`== a,a,a
Tussen reeksen [X_i]..
plaatsen we het teken ; als diepen separator.
We scoren deze als type 0 omdat ook de komma ,
kan worden hergebruikt.; mits in een optimaal systeem
dat strikt tot 1 aftelt.
Maar we introduceren een nieuw teken, om systemen
die tot 0 itereren in dezelfde structuur mogelijk te maken.
Deze overgang ];[ is van type 00000
en vermenigvoudigt de lege diepen links.
Zoek een gewoon haakje ] of 00 om te eindigen.
Onze opzet lijkt op de eerste rij variabelen 1..
waar het systeem mee begon.
a,b1 ,[1];[c1]
`= a,a ,[1][b1];[c]
`= ,[1,[a][b];[c]2]
`== ,[1,[1][b];[c]a`]
`= ,[1,[1,[a][b-];[c]2]`]
`== ,[1..,[1][1];[c]..`] :b:
`=` ,[1][1][a];[c-]
`= ,[1][1,[1][a][a-];[c-]2]
`==` ,[a][a-][a-];[c-]
`== ,.[a-]..;[1] :c1
= ,.[a-].. :c1
Maak "diepe dimensies" met de overgang ];[[
van het type 0{7} ertussen
(dus niet [[ bij de komma al),
lopend tot aan ]][ type 0{6}
die het dubbel diepe construct afsluit,
zodat het enkel diepe weer begint.
Reduceer ;[[1]] tot ;
en noteer de diepe dimensies met ;[[n]]
naar analogie van de multidimensionale arrays.
a,b1 ,[1];[[2]][3]
`= a,a ,[1];[[1]][b1];[[2]][2]
= ,[1];[b1];[[2]][2]
# 5. Geneste arrays
Als groot getal noemen we de "googol",
te schrijven als 10^100 met exponent,
of in onze 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 ons heelal 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.
$ 2. Supermacht operaties
De wiskunde stelt dat een supermacht de herhaling is
van een aantal vorige macht of supermacht operaties.
Hier telt ^{c>0} het aantal carets en onze 'rep'
herhaalt de text links van .. in totaal b keer.
a^{c+1}b = a^{c}..1 :b
Wat stapsgewijs als volgt kan worden gedefinieerd.
Waarbij *{c≥0} ook de vermenigvuldiging
tot een serie van directe optellingen kan reduceren.
a*{c1}b1 = a*{c}(a*{c1}b)
== a*{c}(..a*{c1}1..) :b:
≡ a*{c}..a :b
Supermacht operaties ^{c} of *{c1}
zijn rechts associatief, dus deze expressies
worden verder van rechts naar links uitgewerkt.
Hier evalueren we de supermachten
met onze nieuwe "popster" operaties.
Deze sluiten nauw aan bij een primitief recursieve
functie voor supermachten over een rij variabelen.
We zullen ons popster systeem langzaam opbouwen.
$ 2.1. Rekenoperaties
Met de eerste supermachten *{k<3}
kunnen we rekenen.
Dit zijn de operaties van optellen *{0}
en vermenigvuldigen *{1}
en machtsverheffen *{2}
waarvan ook de inversen en vele reële
en complexe getallen bekend zijn.
$ 2.1.1. Optellen is 0
Bij variabelen met natuurlijke getallen a en b
die naast elkaar staan, is meteen de som ab gegeven,
waarin alle enen 1.. bij elkaar optellen.
We plaatsen 'plus' + tekens tussen getallen
om optellen uit te stellen.
- +a+b =` +ab
- a+b = ab
Door deze regels • voor optellen
consequent vanaf rechts toe te passen,
komen de wachtende operaties beschikbaar
en kan hun + wegvallen.
Het "is gelijk" teken = drukt gelijkheid uit
en betreft de evaluatie van hele expressies
of subexpressies (binnen haakjes).
Het "is rechts" teken =`
selecteert vanaf rechts in de expressie.
Daarmee werken we operaties 'r-l' uit,
reducerend van rechts naar links.
Zo werken we een optelling tot getal stapsgewijs uit.
1+1+1+1 = 1+1+11
= 1+111 = 1111 ≡ 4
De actieve plus operatie is te beschouwen
als *{0} nulde superster, die leeg is.
Alle operaties rechts van een plus teken
krijgen voorrang, maar ook elke hogere operatie
die links ervan staat.
$ 2.1.2. Vermenigvuldigen is 1
Vermenigvuldigen is herhaald optellen
van een constant a.. getal.
Het keer of maal teken ertussen
schrijven we met een * ster.
Definitie van vermenigvuldigen voor gehele getallen.
Stel b>0 zodat de tweede regel in de laatste stap
de iteratie overneemt van de eerste regel.
- a*b1 =` a*b+a
- a*1 =` a
Vindt een match vanaf rechts =`
in de expressie voor de vorm links in de regel.
Iedere iteratie stap telt een constante a op bij de som.
Herhaal de reeks stappen ==
in combinatie met optellen, tot de laatste stap
de operator elimineert en de uitkomst levert.
a*b1 = a*b+a
== a*1+.a.. :b
= a.. :b1
De 'rep' :b herhaalt de tussen .
of terzijde van de punten ..
geselecteerde passage b maal.
Reps zijn beschrijvend bedoeld en niet regelgevend.
Een voorbeeld van vermenigvuldiging als optellen in stappen.
Neem de vertaling naar decimale getallen hier voor lief.
2*3 = 2*2+2 = 2*1+2+2
= 2*1+4 = 2+4 = 6
De iterator is hier 111
en in het algemeen een variabele b
waar elke stap 1 vanaf telt
om een kopie van a op te sommen.
De ster van vermenigvuldigen
is de eerste superster operator.
$ 2.1.3. Machtsverheffen is 2
Machtsverheffen ** of ^
is herhaald vermenigvuldigen.
Om machten stapsgewijs uit te werken,
met de lagere operaties eerst,
moeten we de hogere in de wacht zetten.
De 'pop' plus in popster *+ operaties
stelt vermenigvuldiging uit.
Alsof het tussen haakjes staat, met maar één plus teken,
tot het getal klaar is en de ster ontpopt.
Evalueer popster machten volgens deze speciale definitie,
waar b>0 .
- +a*+b =` +a*b
- a*+b = a*b
- a**b1 =` a**b*+a
≡ a*..a :b
- a**1 =` a
We hebben de regels in een volgorde gezet, die het mogelijk
maakt om deze definitie op twee manieren toe te passen:
hetzij door de bovenste toepasbare regel uit te voeren,
hetzij de regel die meest rechts in de expressie aangrijpt.
We gebruiken het equivalentie teken ≡ 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 ons popster systeem in a^b+1
één op bij een factor, maar in 1+a^b
gewoon bij het totaal.
Volgt een ster *+ met pop plus,
dan komt die gewoon als factor bij de reeks factoren.
Deze regels werken zonder precedentie
en evalueren strikt 'r-l' vanaf rechts,
wat vreemde resultaten geeft
als we ster operaties op elkaar schrijven.
2**3*2 = 2**3*1+3 = 2**3+3
= 2**2*+2+3 = 2**2*+5
= 2**1*+2*+5 = 2**1*+2*5
== 2**1*+10. = 2*+10.
= 2*10. == 20.
We kunnen het ook anders regelen:
om carets ^ met meerderheids-precedentie
op te lossen (hogere operaties met meer tekens eerst),
en daarna sterren * met minderheids-precedentie
(voorrang aan minder tekens).
Dan zou 2**3*2 = 2^6 groter zijn,
maar 2^3*2 = 8*2 kleiner.
$ 2.2. Popster supermachten
Door extra sterren * in de operator zetten,
of met een superfactor {c} weer te geven,
noteren we moeiteloos enorm grote getallen.
De macht operant b die groeit in de evaluatie,
drukt steeds een reeks vorige operaties
met constante a uit. In ons systeem
met popsterren worden die torens niet afgebouwd;
de top operaties komen apart te staan
en werken we eerst uit.
$ 2.2.1. Definitie
De volgende operatie met *** sterren of ^^ dakjes
heet "Tetratie" en geeft een aantal machtsverheffingen,
equivalent aan een toren van exponenten
die 'r-l' vanaf rechts moet worden opgelost.
a***b1 = (a***b)**a
== (..a^^1..)^a :b:
= a^..a :b
Operatie na operatie kunnen we zo supermacht expressies
bouwen met ieder aantal operator tekens.
In wezen een dubbel recursieve operatie
over twee variabelen, met als beginwaarden
iterator b=1 en *{c=0} voor direct optellen
(of nul dakjes voor historisch vermenigvuldigen).
Definitie om 'PopSter' supermachten
te evalueren tot natuurlijk getal.
Steeds geldt b>0
maar de operator *{c≥0} kan leeg zijn.
-PS.1a. +a*{c}+b =` +a*{c}b
-PS.1b. a*{c}+b = a*{c}b
-PS.2. a*{c1}b1 =` a*{c1}b*{c}+a
-PS.3. a*{c1}1 =` a
We voeren die regel uit, die een match geeft
op de meest rechtse =` positie in de expressie.
Maar in de evaluatie van een supermacht blijft dit
hetzelfde als voorrang geven aan de bovenste regels.
Variabelen zijn "gretig" naar enen,
zodat elke getal a in de regels compleet is,
zonder rest deel in de expressie.
Stap 2. ster operatie introduceert
kleinere popster met operant.
Trap 1. elimineert de plus
uit de rechts gelegen popster.
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.
Of als we een plus teken +X
voor alle popster expressies zouden zetten,
dan is een vierde regel +x = x
pas nodig bij de uitkomst.
$ 2.2.2. Evaluatie
Als voorbeeld werken we de macht 2**2
en de supermacht 2****3
uit met de 'PopSter' regels in stappen vanaf rechts.
We schrijven voor het gemak carets,
waarbij *{c1} en ^{c} gelijk zijn en strikt 'r-l'
rechts associatief met pops te evalueren.
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.
Alle supermacht expressies zijn met
twee type tekens, de 1 en * te noteren.
Tijdens de evaluatie komt daar de pop +
als solo haakje bij. Slechts drie tekens!
Dakjes ^ of carets en ^+ popcarets,
cijfers en tientallige getallen (met decimale punt)
nemen we erbij als afkortingen.
$ 2.2.3. Toepassingen
We kunnen sommige supermacht operaties
alleen ruwweg met elkaar vergelijken qua grootte.
In dit voorbeeld neemt het absolute verschil <
tussen twee ster supermachten bij grotere c toe.
Terwijl dit verschil in de context
van de hierdoor groeiende reeksen
klein begint met 1 en niet significanter zal worden.
2^{c}4 = 2*{j}..8 c:1 <
3^{c}3 = 3*{j}..9 c:1
De teller {c} geeft in krulhaakjes
het aantal tekens in de operator aan.
De repetitie c:1 noteert een reeks
waarin de indexen j naar rechts afnemen.
In de expressie a^{c}b1*{d}+e
ontpopt de iteratie van rechts als hoogste exponent
in de toren a*{c}..a*{d}e :b
wat significant kan zijn
en een aanvulling vormt op ons rekenapparaat,
om array functies nauwkeuriger te kunnen schatten.
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 zag de superoperator het licht,
met carets in de vorm van de pijlen ↑{c}
van Donald Knuth, in zijn essay
"Omgaan met eindigheid".
Maar dezelfde dubbele recursie φ_c(a,b)
inclusief Ackermann functie
was al te vinden bij David Hilbert, in zijn artikel
"Over het oneindige" uit 1925.
$ 2.2.4. Functie vorm
Evaluatie van supermachten kan makkelijker
met een functie!
Als we supermacht operaties a*{c}b
uitwerken volgens de 'PopSter' definitie
krijgen expressies deze vorm.
a*{c_i+1}b_i*{c_i}+..b_0 k:1
waar b>0 en c_i1>c_i≥0
Elke superster operatie telt daarbij een ster *
meer dan de erop volgende popster.
Deze sterparen nemen naar rechts af,
maar niet alle tussenliggende supersterren *{c}
hoeven in die reeks voor te komen.
Stel nu, dat we voor de ontbrekende supermachten
in die reeks een operant b=0 nemen
(een permanente nul), die zijn sterpaar reduceert
tot een wegvallende nul 01 = 1
(tegen de variabele erna) met een extra regel.
-PS.4. a*{c>0}0*{d}+ =` 0
Zo is de reeks van sterparen
die naar rechts toe aflopen compleet.
a*{i}b_i*{i-}+..b_0 k:1
En verloopt een uitwerking vanaf rechts
bijvoorbeeld via:
2^^^^1^^^+2^^^0^^+2^^2^+2^0*+2*0+1
= 2^^^^1^^^+2^^^0^^+2^^2^+1
== 2^^^^1^^^+2^^^0^^+4
= 2^^^^1^^^+4
= 2^^^+4 = 2^^^4
== 2^^65536. ≡ 2^..1 :65536
Omdat alleen de operanten b
en het aantal carets ^{c} of sterren *{c1}
variabel zijn en kenmerkend, is het overbodig
om de constante a voortdurend aan te halen.
Ook komt er van ieder sterpaar nu één voor,
in rangorde 'r-l' oplopend,
met de hogere supermachten links in de wacht.
Om tijdens de uitwerking een popster expressie op te slaan,
hoeven we dus enkel de constante a
en alle variabelen b_i in volgorde te noteren.
2^^^^2^^^+ 2^^2
2^^^^2^^^+2^^^0^^+2^^2^+2^0*+2*0+1
2^^^^2 ^^^0 ^^2 ^0 *0+1
2 2 0 2 0 0 1
2, 1,0,0,2,0,2
Alle essentiële data is hier met zeven getallen gegeven.
En we draaien de rij met zes variabelen ook om,
zodat de evaluatie 'l-r' in leesrichting kan verlopen.
De achterste pop +1 is eigenlijk alleen
voor de vorm en kan in de functie
door een andere regel worden ondervangen.
Getal 0 schrijven we zonder enen.
Dan toont deze popfunctie,
dat het aantal supermachten *{k}n steeds 1
verschilt met het corresponderende aantal
komma's ,{k1}n links in de rij.
2*{6}3 = 2*****2****+2***2
11,{7}111 = 11,,,,11,,11
Zo zetten we supermacht expressies om naar
een rij structuur, met nog maar twee tekens
en een veel kortere expressie lengte.
De regels voor de evaluatie
van een dergelijke functie zijn simpeler
en zien we in het volgende hoofdstuk.
$ 3. Rij functies
De systemen in dit hoofdstuk beperken zich tot
een eerste rij met variabelen,
als beginplan voor het maken van grote getallen.
We ontwerpen hier twee nieuwe primitief recursieve
functies, die de supermachten uitdrukken.
Ook bespreken we de bekende notatie systemen
van Conway's pijlketen en Bird's lineaire array.
In hun snelle recursieve functies
worden subexpressies meteen genest,
zodat supermachtsverheffen al met twee variabelen kan.
$ 3.1. Systeem Adam
Systeem 'A' voor "Adam" of "Amsterdam"
krijgt over zijn eerste rij de functie vorm
van de popster supermachten uit het vorige hoofdstuk.
Thema bij de constructie van Adam is,
dat iteratoren en structuren worden afgeteld tot 0
of eigenlijk tot deze leeg staan.
$ 3.1.1. Primitieve recursie
Om zo zuinig mogelijk te zijn met type tekens,
substitueren onze functies geen subexpressies (X)
maar getallen. Ronde haakjes zijn hierbij niet nodig
en de regels staan dus geen "functionele recursie" toe,
waarbij een afgetelde functie expressie
terugkeert in de input variabele.
Rij expressies bestaan uit getallen met tekens 1
en komma's , ertussen als separator.
Als variabelen afgeteld zijn, laten we de 0 weg.
Als "primitief" geldt het optellen van de constante a
en het opschuiven van de variabele b over de rij,
wat "opladen" heet. Dit is de getal opbouw.
Beide regels tellen 1 af van een hogere iterator
(of schrijf min - bij), rechts van de
in te vullen positie. Dit is de expressie afbouw.
We herhalen deze stappen "recursief", waarbij een
vorige herhaling het aantal volgende herhalingen bepaalt.
Tot een natuurlijk getal n wordt uitgedrukt,
als een serie enen 1.. :n van die lengte.
We kunnen alle supermacht expressies evalueren tot getal,
door slechts twee tekens te gebruiken
en drie primitief recursieve regels.
$ 3.1.2. Definitie 'A.I'
Definitie van "Adam" systeem 'A.' over structuur 'I.'
van een rij variabelen,
met regels voor de selectie en evaluatie
van supermacht expressies.
De variabele b≥0 en het aantal komma's ,{k≥0}
mag nul zijn, zonder teken, en ook text variabele R
voor het deel rechts kan leeg staan.
-A.I.1. a,b,1R = a,ab,R
-A.I.2. a,b1,,{k},1R = a,,1,{k}b,R
1= a,a,,{k}b,R
-A.I.3. a,b,{k} = b
Regels met = selecteren de hele expressie.
Gedurende de evaluatie is steeds precies één
van deze regels toepasbaar.
Expressies van 'A.I' blijven congruent
aan die bij de evaluatie van de popster operaties,
zodat functie variabelen links als het ware
op de top operatie rechts worden gestapeld.
Maar de regels werken anders.
Regel 1 telt de constante a op in variabele b .
Regel 2 verplaatst het somtotaal van b
om een afgetelde iterator op te laden, maar laat 1
slim achter, zodat a optelt in de volgende stap.
Regel 3 neemt getal b als uitkomst
en stopt de evaluatie.
De uitgetelde rij structuur rechts
mag tot op het laatst blijven staan.
Alleen expressies van de vorm a,,,{k>0}1R
zijn niet reduceerbaar en vallen buiten systeem 'A'.
We bieden daar een oplossing voor
met de volgende systeem varianten,
waarin ook de lege structuren rechts eerder wegvallen.
$ 3.1.3. Variant 'Aa.I'
In de uitgebreidere definitie 'Aa.I'
worden de resterende komma's van afgetelde variabelen
meteen vanaf rechts opgeruimd.
In plaats van een text variabele gebruiken we
het scan teken ` voor een passieve passage
tot op het eind rechts.
Stel b≥0 bij het somtotaal.
Waar :k>0 een aantal afgetelde variabelen ,0 tussenin
herhaalt, wat we hiervoor noteerden met lege ,{k} komma's.
-Aa.I.0. a,`,0 = a,`
-Aa.I.1. a,b,c1` = a,ab,c`
-Aa.I.2a. a,b1.,0..,d1` :k
= a.,0..,b1,d` :k
-Aa.I.2b. a.,0..,d1`
= a,a.,0..d` :k
-Aa.I.3. a,b = b
In systeem 'Aa' kiezen we ervoor om expressies
met waarde b=0 onder c=0 gelijk te houden
aan die waar b=1 zou staan.
In het strikte systeem 'A' vielen expressies a,{k>2}1R
gewoon niet onder de regels, maar hier worden deze handig
gebruikt om een supermacht mee uit te drukken.
a*{c>0}b = a,{c1}b
De extra regel verandert de evaluatie niet.
Regel 2a en 2b van 'Aa' na elkaar toepassen,
geeft hetzelfde resultaat
als opladen en optellen in systeem 'A'.
$ 3.1.4. Variant 'Ab.I'
Een ander type definitie scant `=
de expressie vanaf de linker kant naar rechts,
tot er een match gevonden is, of faalt.
En we benoemen alleen die variabelen en structuren,
die om te selecteren en te wijzigen nodig zijn.
Een spatie in een regel betekent
het einde van het linker gedeelte van de match,
waarna de expressie doorzocht wordt
naar een match voor het rechter gedeelte.
Op de spatie zal de 'l-r' scan dus elke
andere passieve text overslaan.
Bij deze definitie van systeem 'Ab.I'
worden de regels strikt in volgorde toegepast.
Stel alle b≥0 en ruim de komma's
pas op als de verdere rij leeggeteld is.
-Ab.I.1. a,b,1 `= a,ab,
-Ab.I.2a. a,b1, ,1 `= a,,1 b,
-Ab.I.2b. a,,, 1 `= a,1,,
-Ab.I.3a. a,b, `= a,b
-Ab.I.3b. a,b = b
Speciale expressie a,,{k>1}2R
evalueert nu tot a,a,{k}R
en telt dus een iteratie stap meer af
dan in systeem 'Aa'.
Dit is rekenkundig juister.
Schrijf in 'Ab' dus altijd b=1
om een standaard supermacht uit te drukken.
$ 3.2. Adam supermachten
We vergelijken de evaluatie in functie 'A.I' met de
popster
operaties. Na wat rekenen ermee volgt
de algemene vorm van zulke vergelijkingen.
$ 3.2.1. Tetratie in rij van vijf
Voorbeelden met drie tot vijf parameters
in systeem 'A.I', die equivalent zijn aan popsterren *
tot *** die tot tetratie komen.
Van functie regels `= tonen we de nummers
links van het evaluatie teken
en van de popster regels =` rechts.
Evaluatie van optellen en vermenigvuldigen.
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 machten in 'A.I' en popsterren.
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,, == a^d2
3= a^d2
Gebruik ster operaties in de variabelen
om het functie algoritme te begrijpen.
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^d*(a*c+b)
De iterator e van tetratie domineert
de kleinere rekenoperaties.
Als deze niet veel groter zijn dan a
dan telt dit ongeveer twee exponenten
erbij e2 op.
a,b,c,d,e
= a,a^d1*c1,,,e {b=a}
≡ a,1,,a^d2,e- {c1=a}
= a,a^a^a,,,e- {d2=a}
== a^^e2
Precies gesteld zo. Of als d~a dan ronden we
een rij van vijf in 'A.I' net zo af.
$ 3.2.1. De rij als reeks popsterren
Met een reeks lege komma's ,{k} op de Adam rij
drukken we direct het aantal sterren *{k}
van een supermacht uit.
a,1,{k1}2p_k
= a,a,{k1}1p_k
= a,a,{k}a-,p_k
== a,a*{k}a,{k1}p_k
= a*{k1}(p_k+2)
Elke voorliggende parameter p in de functie rij
is zelf een supermacht a*{k1}p ofwel a^{k}p
en vormt een popster operatie bovenop
de hoogste exponent van de supermacht
van een rechts volgende parameter.
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 superexponent.
a.,p_i.. 0:k
= a*{i}p_i*{i-}+..p_0 k:1
~ a*{k}(p_k+1)*{k-}+p_[k-]
~ a*{k}(p_k+2)
In het begin bij k<2
of als de voorlaatste p bijzonder groot is,
zal de afronding hiervan ~ afwijken.
Wat lastig is aan systeem 'A.I'
zijn de twee oplaadregels in serie:
het laag opladen van waarde a naar cel b
voordat hoog opladen van cellen weer mogelijk wordt.
Ook zou het zuiniger zijn om de tekenreeks ,{k>1}
in te zetten als dimensie separatoren
voor multidimensionale matrices.
Met de volgende functie lossen we dit op.
# 3.3. De rij van 'E.I.'
Systeem 'E.' staat voor "Eva" of "Eindhoven".
Het Eva systeem noteert zo groot mogelijke getallen
met zo min mogelijk tekens.
We tellen iteratoren en structuren niet leeg,
maar af tot "Een" 1 . Omdat die zo blijven staan,
kunnen we aantallen komma's later een eigen
betekenis geven als dimensie separatoren.
Definitie systeem 'E.I' voor de eerste rij,
met 2 tekens en 3 regels. Het ruimt de uiterst
rechts afgetelde variabelen meteen op.
-E.I.1. a,b = ab
-E.I.2. a,R,1 = a,R
-E.I.3. a,b.,1..,2R :k≥0
= a,a.,1..b,1R :k
Het 'E.' systeem drukt eveneens getallen uit
ter grootte van supermachten.
Maar de uitkomsten vallen niet precies samen met 'A.'
en lopen steeds verder uiteen.
Met de 4e regel wordt zowel de afgetelde iterator ,1
rechts opgeladen, als de andere wachtende ,1
links ervoor in de rij.
Eerst verladen we vanuit volle oorsprong a,b
de som ab en vervolgens
vanuit de lege oorsprong a,0 de constante a .
Met dezelfde expressie noteert functie 'E.I.'
wat kleinere uitkomsten dan de 'A.I.' rij,
maar dit is niet significant.
Regel 3 met :k=0 werkt zo dat a,b,c
vermenigvuldigt a*c+b en optelt.
a,b,1 2= a,b
1= a+b
a,b,c1 3= a,ab,c
== a,a*c+b,1
2= a,a*c+b
1= a*c1+b
Als we dezelfde regel aanhalen,
hoeven we die niet opnieuw te noemen.
a,b,1,d2 3= a,a,b1,d1
== a,a*b1,1,d1
= a,a,1+a*b1,d
== a,a*(a*b1+1),1,d
== a,.a*(..b..+1).,1,2 :d:
3,2= a,a,1+.a*(..b..+1) :d:
@= a,.a*(..b..+1). :d1:
~> a^d2 {b1=a}
Evaluatie met verwijzing @=
past een eerder resultaat toe.
Met :k=1 verwijdert Eva zich
herhaaldelijk van machtsverheffen.
a,b,c1,d 3= a,a+b,c,d
== a,a*c1,1,d {b=a}
@= a,.a*(..c..+1) :d:
~> a^d1 {c1=a}
Dus
a,b,1,1,e1 = a,a,a1,b,e1
@~ a,a^b1,1,1,e
~~ a,a^^e^+b1
~> a^^e1 {b1=a}
a,,1,1,e1 3= a,a,1,1,e
@~ a^^e
a,b,c,d,e {b=a c=a}
@~ a,a^d1,1,1,e
@~ a,a^^e^+d1
~> a^^e1 {d1=a}
De eerste rij 'E.I.' is uit te drukken als een reeks
popster operaties, waarbij elke variabele cel
een ster aan de operator toevoegt.
Hier geldt k≥0 .
a,.,1..,z :k = a*{k1}z
a.,p_i..,z 0:k =
a*{k1}z.*{j}+p_j.. k:0
~ a*{k1}z*{k}+p_k+1 met p_j~a
~ a^{k>0}z1
Met indexen i die van 0 tot k toenemen door 0:k
op variabelen in de functie, met indexen j
die van k tot 0 afnemen
door de k:0 rep van popsterren.
Deze volle rij kunnen we afronden ~ als hiervoor.
Een primitief supermacht algoritme kan ook in drie regels,
maar opladen telt dan steeds 1 bij.
Die uitkomsten nemen scheef toe
ten opzichte van de klassieke supermachten,
hoewel niet significant sneller.
Kies daarbij als derde regel:
- a,b.,1..1` :k1
= a.,1..,ab,1` :k of
- a,b.,1..1` :k>1
= a,..b,1` :k
Ons grote principe is om afgetelde hogere variabelen
consequent met lagere op te laden.
Ook bij Ackermann functies en in de grote getallen arrays
van Bowers en Bird (B&B) wordt dit principe toegepast.
Maar Ackermann verheft de constante a wat traag is.
En B&B verpakken somtotaal b
in een minimaal afgetelde expressie
alvorens die naar hogere regionen op te laden,
wat dan wel ingewikkelder is,
maar even maximaal snel als onze functies.
Rij lengte in 'E.I.' en 'A.I.' loopt gelijk
met de iterator c van een klassieke dubbele recursie
met functie substitutie in b en een constante a .
Door rij lengte vanuit de oorsprong op te blazen,
verlaten we de primitieve recursie en komen
op onze tweede rij al gelijk met Bird's lineaire array.
Over het array vlak zullen we zo
slechts 1 rij achterblijven.
Dit valt te bewijzen via de pijlketen van Conway,
die op de supermachten volgt.
# 3.4. Conway's pijlketens
Dubbele recursie is al gegeven in een functie
met één constante en twee variabelen
waarover die functie itereert.
Iedere iteratie stap substitueert
een minimaal afgetelde expressie,
waarmee de supermachten snel worden uitgedrukt
in drie variabelen.
Bij Conway's pijlketens vindt functie substitutie
vanaf rechts plaats, in de voorlaatste y variabele,
en bij Bird's lineaire array vanaf links
in de tweede b variabele.
Werk een reeks substituties in b uit,
samen 1 stap in de iteratie van c .
Laat het functie teken en de buitenste haken weg.
a,b1,c1 = a,(a,b,c1),c
== a,(..a,1,c1..),c :b:
= a,(..a..),c :b:
De eerste functie a,b,1 kan verschillen,
Hilbert
begint φ_1(a,b) met optellen
en de pijlketens van Conway a→b→1
met machtsverheffen.
In den beginne wordt steeds de constante a opgeteld.
Stel dat c=1 vermenigvuldigt,
en dat c=0 met a,b = ab optelt.
Dan werkt deze functie hetzelfde
als de linkse evaluatie van supersterren met haakjes.
a*{c1}b1 = a*{c}(a*{c1}b)
== a*{c}(..a..) :b:
Hier is 3,3,3 ofwel 3***3 het getal 7625597484987
al boven de biljoen (VS "trillion").
En dan loopt door substitutie het aantal subexpressies
wachtend tussen haakjes snel uit de hand.
- - - - - - - - - - - - - - - -
John H. Conway is de schepper van de pijlketen notatie,
die met twee enkele pijlen in a→y→z
dezelfde supermachten uitdrukt,
als Knuth a↑{z}y met al zijn pijlen.
De rechtse pijlen → zijn eigenlijk geen operatoren,
maar werken als separatoren ,
tussen de variabelen in een recursieve functie.
Stapsgewijze definitie van Conway's pijlketens,
met uitwerking == van 1 iteratie.
-CA.1. a→b = a^b
-CA.2. X→1 = X
-CA.3. X→1→z = X
-CA.4. X→y1→z1 = X→(X→y→z1)→z
== X→(..X..)→z :y:
Text variabele X staat voor a.→x_i.. :k≥0
het linker deel van de keten:
de constante a en een rij van iteratoren x_i .
Functie substitutie en aftelling
vinden plaats binnen in de voorlaatste cel y ,
terwijl van buiten de laatste iterator z aftelt.
Zo worden ketens diep genest,
terwijl de recursie over y→z
naar links schuift en uiteindelijk reduceert tot machten.
Scherp een voorbeeld aan uit het boek van
Conway en Guy.
Gardner's getal 3^{..3^{4}3..}3 :63:
van Graham ligt boven de 3→3→64→2
of 3→3→(..3^3..) :63: in pijlketen notatie,
maar onder 2→3→65→2
of 2→3→(..2→4→7..) :63:
zo te zien, omdat de top supermacht daarin
het grotere 3→3→7 vrijwel benadert
(zie sectie 1.2.c).
Bird's lineaire array gebruikt vier parameters
om even grote getallen te noteren
als Conway met zijn pijlketen rij.
Omdat we net als Bird het subtotaal
vanuit de oorsprong opladen, wat maximaal is,
komt er aan het begin van onze tweede rij een variabele,
die de lengte van Conway's hele keten zal benaderen.
- - - - - - - - - - - - - - - -
Systeem 'A.' kan op verschillende manieren
worden uitgebreid naar de tweede rij.
Neem als rij separator een komma met index ,[1]
tussen haakjes, tot [1] af te korten.
Een nieuwe regel kan met de eerstvolgende parameter m
gewoon de eerste rij lengte k vervangen,
of er bijvoorbeeld zo bij optellen.
- a,b,{k}[1]m = a,,{km}b
- a,b,{k}[1]m1 = a,,{k1}b[1]m
Direkt of in etappes, dat zal voor de grootte
van de uitgedrukte getallen weinig verschil maken.
Pas door [1]m,1 af te tellen tot [1],1
en op te laden met [1]b zal de rij lengte ervoor
door het somtotaal uit b worden opgeblazen.
Dat kan ook op een direkte manier, een parameter sneller,
met andere regels.
- a,b,{k}[1]c1
= a,,{b}a[1]c
= a,a*{b}a[1]c
== a*{..b..}a :c1:
- a,b,{k}[1]m1
= a,,{kb}2[1]m
= a,a*{kb}2,{kb}[1]m
De eerste regel werkt natuurlijker uit,
ongeveer als a→b→c1→2
en wordt hetzelfde genest als Graham's number.
Het bewaren van de lengte k van de bestaande rij
en opsommen ervan in het tweede voorbeeld
is minder relevant, omdat het subtotaal b domineert.
Definitie NB vlak,
waar b>0 en de lengte van de deelrij ` mag 0 zijn.
-NB.1. a,b = b
-NB.2.1. `, = `
-NB.2.2. `,[X] = `
-NB.3. a, ,1` `= a,a ,`
-NB.4. a,b, ,1` `= a,, b,`
-NB.5. ,,[X] `= ,[X]
-NB.6. a,b,[1]1` = a,,{b}a,[1]`
-MB.6. a,b1,[1]1` = a,b,,[1]1`
- Martin Gardner
Scientific American, Nov. 1977
# 3.5. Bird's lineaire array
# 4. Multidimensionale arrays
Een rij variabelen met natuurlijke getallen
noemen we de eerste dimensie, terwijl deze eigenlijk
bestaat uit rijen van rijen van enen.
Een reeks van rijen variabelen vormt dan een vlak
of tweede dimensie,
hoewel de rij lengtes daarin variabel zijn.
Herhaling van het vlak vindt plaats in een kubieke ruimte,
de derde dimensie.
We noteren al zulke array ruimtes op een lijn
in de expressie, waar ze van elkaar gescheiden worden
met specifieke separatoren.
We zouden door een aantal komma's na elkaar te zetten
simpel de dimensies kunnen aangeven.
a,b ,c_i..,,..,,,.. :d :e :f
Dit veronderstelt wel dat we variabelen
niet aftellen tot 0 maar tot 1 ,
anders zou de betekenis van opeenvolgende komma's
al vergeven worden op de eerste rij.
Alle ruimtes van een multidimensionale array
kunnen we door een aantal ,{k}
komma's laten scheiden, maar zou dat niet zonde zijn?
Het teken 1 hebben we gereserveerd voor variabelen.
Elk opeenvolgend aantal enen 1..
drukt een natuurlijk getal uit in de expressie, waarin
de functie van dat getal nader bepaald is
door zijn positie en het algoritme.
Stel nu dat de andere tekens die we toepassen,
zoals separatoren en haakjes paren, substituut staan voor
diverse aantallen van een ander wiskundig quantum,
ons "type teken" in abstracto, de nul 0 in concreto.
Bij de samenstelling van array elementen
zullen we steeds rekening houden met deze achterliggende
"array bit" notatie.
Die moet onze oplossing vormen
voor het Busy Beaver probleem,
althans ongeveer een maximaal getal schrijven
met twee (of meer) mogelijke tekens.
Vanuit de constructie van een evoluerend systeem,
zonder Gödelachtige alfabetisering,
maar gestaag groeiend.
Laat de komma , om getallen te scheiden
als variabelen, het ene 0 type zijn.
Er zijn verschillende manieren om ons systeem
economischer uit te breiden dan hierboven
met ,.. multipele komma's.
Maar welke is natuurlijker?
- - - -
Door op dubbele variabelen over te stappen .,c_i,q_i..
is het mogelijk om na elke even komma
rechts van de variabele c_i de dimensie overgang q_i
aan te geven, zonder extra 00 type teken.
Er links voor kan ook.
Om deze duo variabelen in de rij te herkennen,
geeft dit bij de expressie scan in het algoritme
helaas telproblemen.
Ook groeit zo'n systeem niet natuurlijk.
Het hinkt: eerst op één poot en dan op twee poten,
en later eventueel op duizend.
Door bij elke variabele
een vast aantal extra tellers te zetten,
behalen we de hyperdimensies in een rij.
Dit kennen we als de index rij bij de separator.
Of spreek net als Bird af, dat een getal tussen haakjes
de dimensie van de ruimte rechts ervan kenmerkt.
Door enkele komma's binnen de subarray te halen, breiden
Bird's multidimensionale uit tot hyperdimensionale arrays.
Zolang onze subarrays niet genest worden
en de scanner van eerste tot tweede teken kan tellen,
mag het beginhaakje dezelfde zijn als het sluithaakje.
Het bit type is dan 00 aan beide einden,
ook al gebruiken we in de expressie [ en ] .
En afgetelde subarrays [1]=,
evalueren meteen tot type 0 komma.
Bezwaar is hier, dat de tel bijhouden
niet echt een taak is voor de tekst scanner.
Een woord moet zonder de helft van de expressie
te doorlopen op elke plek herkend kunnen worden.
Lijkt op het voorbeeld hiervoor,
maar extra tellen kan hier niet,
omdat in elkaar nesten van gelijke haakjes verwarring geeft.
Juist is om twee typen haakje te gebruiken,
of hetzelfde type maar bij de opening
gebonden aan een separator teken.
Bird gebruikt krulhaken { en }
en breekt met het gebruik van enkele komma's ,
door te stellen dat deze in staan voor index 1 subarrays.
Zijn variabelen worden altijd tot 1
en niet tot 0 afgeteld,
zodat separator haakjes elkaar nooit zullen raken.
Zo bezien zijn Bird's haken van het type 0 en 00
en hij kan daar alle geneste arrays mee vormen.
Zijn afgetelde indexen worden steeds opgeladen
vanuit de oorsprong met subtotaal b wat optimaal is.
We mogen stellen dat gegeven deze beperkte tekens
de door Bird geneste getallen maximaal groot zijn.
De overgang van de komma uit Bird's lineaire arrays
naar zijn dimensie haakjes verloopt niet zo soepel.
We gaan liever van , naar ,[n]
met behoud van het separator teken,
waar het openingshaakje van de index array aan gekoppeld is,
ook al kan Bird ons een type voor blijven.
Onze opening ,[ telt als type 000
en sluit af ] met type 00 .
Schrijf eventueel de multidimensionale arrays
met een enkel haakje ,n]
om provisorisch even een type te besparen.
Na het vrije haakje ] dat de geneste array afsluit,
volgt de variabele die meter is van de ruimte ervoor.
We expanderen dit systeem
door binnen het separator construct
nieuwe en grotere array types te plaatsen.
Voor het type tellen we simpel 0..
de teken types na elkaar.
Vorm diepe arrays met overgangen ][
die als type 0000 scoren.
Het volgende diep [X][1Y] zal op die overgang
de afgetelde array ervoor tot grotere diepte nesten.
We maken dat ook staps-of druppelsgewijs mogelijk.
a,b1 ,[1][3]
`= a,a ,[1,[b1][2]2]
`= ,[1,[b][2]a,[b1][2]1]
`== ,[1,[1][2]a`]
`= ,[1,[1,[a][1]2]a`]
= ,[1,[1,[a]2]a`]
`== ,[1,[1,a`]a`]
`= ,[1,[a`]a`]
`== ,[a`]
`== a,a,a
Tussen reeksen [X_i]..
plaatsen we het teken ; als diepen separator.
We scoren deze als type 0 omdat ook de komma ,
kan worden hergebruikt.; mits in een optimaal systeem
dat strikt tot 1 aftelt.
Maar we introduceren een nieuw teken, om systemen
die tot 0 itereren in dezelfde structuur mogelijk te maken.
Deze overgang ];[ is van type 00000
en vermenigvoudigt de lege diepen links.
Zoek een gewoon haakje ] of 00 om te eindigen.
Onze opzet lijkt op de eerste rij variabelen 1..
waar het systeem mee begon.
a,b1 ,[1];[c1]
`= a,a ,[1][b1];[c]
`= ,[1,[a][b];[c]2]
`== ,[1,[1][b];[c]a`]
`= ,[1,[1,[a][b-];[c]2]`]
`== ,[1..,[1][1];[c]..`] :b:
`=` ,[1][1][a];[c-]
`= ,[1][1,[1][a][a-];[c-]2]
`==` ,[a][a-][a-];[c-]
`== ,.[a-]..;[1] :c1
= ,.[a-].. :c1
Maak "diepe dimensies" met de overgang ];[[
van het type 0{7} ertussen
(dus niet [[ bij de komma al),
lopend tot aan ]][ type 0{6}
die het dubbel diepe construct afsluit,
zodat het enkel diepe weer begint.
Reduceer ;[[1]] tot ;
en noteer de diepe dimensies met ;[[n]]
naar analogie van de multidimensionale arrays.
a,b1 ,[1];[[2]][3]
`= a,a ,[1];[[1]][b1];[[2]][2]
= ,[1];[b1];[[2]][2]
# 5. Geneste arrays