Grote Getallen Generatie

met Conway-Knuth superpijlen!

door Giga Gerard

“Opus est magnis numeris”
– Vladimir Poetin

Dag / Nacht

Fn · Gids

Aangevinkte Fn knoppen zijn klaar voor gebruik.
Vink ze uit om deze te blijven verbergen.

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