Grote Getallen Generatie

$ 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.. :k≥0 Index i neemt elke volgende stap toe of af met 1 zoals dit van links : op rechts is aangeduid in de 'rep'. De waarde van cijfer plaatsen neemt 'l-r' af, van links naar rechts, terwijl de constructie van getallen bij herhaalde vermenigvuldiging van 10 op moet lopen. Naast de historische herkomst van de cijfers is dus ook de opbouw van de decimale getallen 'r-l' in de richting van het Arabische schrift. Voordeel is dat 'l-r' lezers het belangrijkste cijfer van de grootste macht nu vooraan zien staan. - - - - - - - - - - - - - - - - Vraag: In basis 6 is het getal 555 hetzelfde als 215. in basis tien. Maar als de bases onbekenden zijn, zijn die dan te berekenen..? Valt te bewijzen, dat geen enkel ander basis paar voldoet..? En als dit in het algemeen onmogelijk is, voor welk soort getallen kan het wel..? $ 1.3. Getalgaten Getallen kunnen bestaan uit eenheden of units, of verkort geschreven worden met operaties of functies in een wiskundige expressie. Expressies voor natuurlijke getallen zijn met behulp van regels te evalueren tot een uitkomst bestaande uit een aantal enen. Om structuur toe te voegen aan de expressie zetten we extra tekens in. En ook het algoritme, met de definitie van de regels voor evaluatie van expressies, zorgt voor een uitbreiding van ons wiskundig taalapparaat. Doel van de googologie is om met een minimaal aantal tekens en zo beperkt mogelijke regels, zo groot mogelijke getallen te noteren. Om hogere wiskundige structuren te herkennen en daarover dan te itereren tot in het oneindige. Hoe sneller de functie, hoe meer getallen tussenin gemist worden in de notatie. Zulke grote gaten liggen dieper verborgen dan de grote getallen zelf, die als vuurtorens boven hun eiland van naburige kenbare getallen uitsteken, terwijl de random zee van getallen eromheen onkenbaar is. Vrij snel in dit verhaal zijn de meeste natuurlijke getallen door geen enkel praktisch getalsysteem meer te bevatten. Want de systemen die in ons fysisch heelal mogelijk zijn, zijn beperkt door het aantal te observeren quantum bits. We kunnen stellen dat binaire getallen met een lengte van ongeveer 10^81 (Vopson 2019) tot wel 10^90 (Lloyd 2001) zich nog in het zicht bewegen. Daarboven wonen de goden. In elk wiskundig systeem is de expressie lengte van de meeste gehele getallen groter dan in een radix met evenzoveel tekens. Hoewel dit verschil niet meer dan een luttele basismacht 10 kan bedragen in totaal, omdat al die expressies uiteindelijk tot 1.. evalueren in de systeem output. Al de getallen die de mens kan gebruiken zijn relatief "klein". Het vervolg van dit reisverhaal in de getallen zal bijgevolg volstrekt nutteloos zijn, hopelijk... $ 1.4. Googols Een beroemd groot getal is de "googol", geschreven als 10^100 met exponent, of in basis tien als een 1 gevolgd door 100 nullen. De Babyloniërs zouden hier in basis 60 een reeks van 57 spijkerschrift tekens voor nodig hebben. In de digitale radix 256 neemt dit 42 bytes in beslag. Voor de googoloog, die net als Google zijn naam dankt aan dit getal, geeft een basis notatie erge rompslomp. Cijfers zijn handig om getallen mee af te korten, maar googologen tellen net zo goed weer enen als onbenullen nullen. Een "googolplex" is een 1 met googol nullen, ofwel 10^10^100 met dubbele exponent. Dit getal zou in de hypothetische basis "googol" met 10^98 nullen geschreven worden. Als elke 0 daarin de maat van een bacterie heeft vullen die de gehele ruimte van het heelal, een voorbeeld van de onmacht van radix systemen. Om een random getal verborgen in de zee rondom het googolplex uit te drukken met quantum bits, hebben we tot wel 10^20 keer zoveel van die deeltjes nodig dan er in dit heelal te vinden zijn. Zelfs bij een vrije keuze om elke mogelijke wiskundige expressie te evalueren met elk mogelijk wiskundig systeem, weer te geven als input (uitrekenen hoeft niet) op onze ene universum quantum tablet, is het nog onzeker of elk getal opgevist zou kunnen worden. Met een hogere exponent erbij de meeste random getallen zeker niet! Googolplex is al een onbegrijpelijk groot getal. Het eerste vuurtoren eiland dat we aandeden op onze ontdekkingsreis naar het oneindige. - - - - - - - - - - - - - - - - Vraag: Googol is 10^100 . Vind een benadering voor de tetratie wortel t , zodat t^^t dicht in de buurt komt van googol. Stel t is een exact reëel getal, niet fundamenteel fuzzy of onkenbaar, hoort t thuis in een nieuwe klasse..? Sneller en dieper verzonken in de getallenlijn dan de eindeloze rij breuken, waarmee we algebraïsche en transcendente reële 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 Donald Knuth definieerde supermacht operaties als reeksen. We beschrijven hoe dit in stappen kan, in plaats van Knuth's ↑_^[..]_ oppijlen met ^_^[..] carets of voor supersterren *_^[..] die terugkeren op *{0} unair optellen. De rest van dit hoofdstuk evalueert supermachten met onze nieuwe "popster" operaties. We bouwen het systeem van regels voor popsterren langzaam op, en beginnen met de elementaire operaties van het rekenen. De algemene uitwerking van popster supermachten zal nauw aansluiten bij onze primitief recursieve functie Adam voor supermachten over een rij parameters. $ 2.1. Supermacht reeksen Een supermacht operatie a^{c1}b is gedefinieerd als een reeks voorgaande operaties, met operatoren ^{c} tussen een b aantal constanten a . Hierin telt c>0 het aantal carets, met als basis ^ machtsverheffen, wat zelf een reeks vermenigvuldigingen * inhoudt We schrijven supermacht operatoren hier met carets of sterren, waarbij we voor dezelfde supermacht een ster meer *{c1} tellen dan met ^{c} carets. Gelijke supermacht operaties zijn rechts associatief en een reeks van dezelfde operaties wordt exponent op exponent 'r-l' van rechts naar links uitgewerkt. Definieer caret supermachten stapsgewijs door links ervan de voorgaande operatie af te splitsen, tot na herhaling == de reeks compleet is. Omdat de grotere caret operatie voorrang geniet, kan dit zonder haakjes. a^{c1}b1 = a^{c}a^{c1}b == a^{c}..a^{c1}1 :b = a^{c}..a :b Dit lukt niet door de lagere supermacht rechts te plaatsen, omdat dat een ander en lager getal uitdrukt. We werken bijvoorbeeld a^a^^3 door a^a^(a^a) uit, terwijl de tetratie in a^^3^a apart (a^a^a)^a van de rechts volgende macht staat, waardoor dit gelijk is aan a^a^a1 met een kleinere tweede exponent. Substitueren van top exponenten pakt een stuk groter uit dan in de basis links. Bij caret supermachten krijgt de operator met de meeste carets prioriteit. Om de top operatie rechts helemaal te kunnen evalueren, moeten die lager wordende operaties afgescheiden blijven van de reeks hogere a^{c}.. die links nog wacht. Dat kan door vooraf toch haakjes te plaatsen. ^{c}a^{c}a =` ^{c}(a^{c}a) Dat de operatie rechts in de reeks het eerst aan bod komt, geeft aanzienlijk grotere getallen. De exponent van de top supermacht is veruit dominant. Operator prioriteit wijkt af bij ster supermachten *{c} omdat we minder sterren voorrang geven. Maar dan moet de grotere operatie gelijk afgeschermd worden bij de operatiestap, wat kan door haakjes te introduceren. a*{c1}b2 = a*{c}(a*{c1}b1) == a*{c}(..a*{c1}1..) :b1: = a*{c}(..a..) :b1: = a*{c}(..a*{c}a..) :b: := a*{c}..a :b1 Hier geldt c≥0 voor de ster teller. Supersterren zijn primitief recursief, omdat vermenigvuldiging * een serie directe optellingen *{0} geeft. Als de reeks klaar is, kunnen we de haakjes om al de operaties daarin laten wegvallen. Als we verder gaan om de top operatie a*{c}a tot reeks uit te werken, scheidt de minoriteit precedentie deze vanzelf af van de toren links. We zouden supermachten ook rechts ervan in stappen kunnen uitwerken. Door met een + teken aan te geven dat de kleinere operaties wachten tot de grotere klaar is, waarna ze van rechts als reeks gestapeld worden. Bijvoorbeeld zo. a^{c1}b1 = a^{c1}b+^{c}a == a^{c1}1.+^{c}a.. :b = a.+^{c}a.. :b = a+^{c}..a^{c}a :b- == a^{c}..a :b De 'rep' :b na de expressie geeft aan dat de passage, die rechts van de enkele . punt begint of zonder punt aan de linker kant, op het enzovoort teken .. ook wel "ellips" genoemd, in totaal b keer is herhaald. Voorbeeld hoe een 'rep' ook in stappen te maken valt, met tekst variabele X . X.. :3 = X..X :2 = X..XX :1 = XXX Repetitie notatie is als uitleg bedoeld, om herhaalde evaluatie te tonen op een standaard manier. We gebruiken deze niet regelgevend, want regels beschrijven in onze systemen slechts een enkele stap. Hoe we Knuth's oppijl operaties ↑{c} strikt vanaf rechts per stap evalueren, wordt in hoofdstuk 4.1 uitgelegd. $ 2.2. Popster rekenen Met de eerste supermachten *{k<3} is nog goed te rekenen. Dit zijn de operaties van optellen *{0} en vermenigvuldigen * en machtsverheffen ** waarvan er ook inversen en hun (oneindige) functie series bekend zijn: de breuken en de algebraïsche, transcendente en complexe getallen. $ 2.2.1. Ster 0 optellen Als variabelen met natuurlijke getallen a en b naast elkaar staan, is meteen de som ab gegeven, doordat alle enen 1.. bij elkaar optellen. Plaatsen we dus een 'plus' teken + tussen variabelen om optellen uit te stellen. - a+b = ab - +a+b =` +ab Het "is gelijk" teken = stelt dat de hele expressie of subexpressie (die binnen haakjes) aan beide kanten gelijk is. Vervang in de evaluatie de vorm links ervan door de vorm rechts. Het "is rechts" teken =` selecteert zijn vorm aan of vanaf de rechter kant in de expressie (of subexpressie). Door de • regels voor optellen consequent vanaf rechts toe te passen, komen wachtende operaties vrij en kan hun + wegvallen. Zo reduceren we alle popster operaties 'r-l' met als uitkomst een getal. Voorbeeld van optellen in stappen tot getal. 1+1+1+1 = 1+1+11 = 1+111 = 1111 = 4 Operaties rechts van een willekeurig plus teken krijgen voorrang. Normaal komen ook alle operaties met hogere prioriteit eerder, zoals ^ en * als die links staan. Maar popsterren evalueren we strikt van rechts naar links. Om duidelijk te maken dat steeds de popster regels 'r-l' van toepassing zijn, kunnen we dat aangeven met een plus +X aan het begin van de expressie. Dit verandert alleen de basisregel voor optellen. - +a = a De betekenis van de plus operator is het uitstellen van de optelling tot beide zijden klaar zijn: een mono-haakje dus. Maar links genoteerd zou een plus aangeven, dat hogere operaties in de expressie volgens de regels moeten wachten op de lagere rechts. In het kader van popster operaties is optellen met de nulde superster *{0} leeg, waarmee unaire variabelen direct samenvallen. $ 2.2.2. Ster 1 vermenigvuldigen Herhaald optellen a.. van een getal heet vermenigvuldigen. We schrijven het keer of maal teken ervan met een * ster. Definitie van vermenigvuldigen voor gehele getallen. Stel b>0 zodat de eerste regel in de laatste stap de iteratie overneemt van de tweede regel. - a*1 =` a - a*b1 =` a*b+a Selecteer vanaf rechts =` in de expressie de vorm links in de tweede regel en evalueer die passage naar de vorm rechts. Zo telt iedere iteratie stap een constant getal a op bij de som rechts. Voorbeeld van vermenigvuldigen als optellen in stappen. +2*3 = 2*2+2 = 2*1+2+2 = 2*1+4 = 2+4 = 6 De iterator is hier het getal 3 of unair 111 en in het algemeen een variabele b . De operatie regel telt daar 1 stap vanaf en telt rechts een kopie van a op. Herhaal in stappen == en tel op, tot in de laatste stap de eerste regel de ster * operator elimineert, waarna basis optellen de uitkomst levert. +a*b2 = a*b1+a = a*b+a+a = a*b+aa == a*1+.a.. :b1 = a+.a.. :b2 = a.. :b2 Een 'rep' :k herhaalt de tussen . of terzijde van de punten .. geselecteerde passage k maal. De ster van vermenigvuldigen is *{1} de eerste superster operator. $ 2.2.3. Ster 2 machtsverheffen Machtsverheffen ** of ^ is herhaald vermenigvuldigen. In de uitwerking van machten tot vermenigvuldigen en optellen komen de lagere operaties rechts aan bod, terwijl we de hogere links in de wacht zetten. De 'pop' plus in de popster *+ operator stelt vermenigvuldiging uit. Dit werkt alsof de ster operatie tussen haakjes staat tot deze kan worden "ontpopt". Evalueer machten met een popster volgens deze speciale regels, waarbij b>0 in de exponent. - +a*+b =` +a*b - a**1 =` a - a**b1 =` a**b*+a Primitievere regels staan eerst vermeld in onze definities. Maar dat geeft niet meteen ook de volgorde van uitvoering. Voorrang in de evaluatie krijgt die regel, waarvan de vorm het eerst in de expressie overeenkomt. En bij regels met =` bepaalt de eerste positie rechts van de match de prioriteit. Selecteren twee regels dezelfde passage, gebruik dan de eerdere regel uit de definitie. Als de vorm a**1 een match geeft, kunnen vaak meer enen volgen, en dan geldt de regel voor de iteratie stap, want die grijpt rechts het hele getal. We kunnen ervan uitgaan dat voor elke popster expressie aan de linker kant een plus teken +X staat (ook al schrijven we die niet). Dan zijn onze drie regels voor machten voldoende. Anders zou a*+b = a*b een hulpregel kunnen vormen, hier onder. +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*4 == 8 := 2*2*2 We gebruiken het toewijzingsteken := voor een stap in de evaluatie, die niet normaal volgens de regels is, maar wel een handige vertaling geeft. Zoals hier naar een reeks factoren, want normaal werken we factor na factor uit tot getal. Hoewel dit geval niet vanzelf tijdens de evaluatie ontstaat, gegeven +a^b+1 dan telt het popster systeem die 1 op bij de eerste factor, maar in 1+a^b gewoon bij de machtsverheffing. Het eerste geval is dus groter. De regels voor popsterren werken zonder precedentie en evalueren strikt 'r-l' de meest rechtse selectie. Dit geeft vreemde resultaten, als we ster operaties na elkaar schrijven in de input expressie. +5**3*2 = 5**3*1+3 = 5**3+3 = 5**2*+5+3 = 5**2*+8 = 5**1*+5*+8 = 5**1*+5*8 == 5**1*+40. = 5*+40. = 5*40. == 200. Volgt op de macht een ster *+ met pop plus, dan geeft dit gewoon een factor erbij. Zo komt 5**3*+2 via 5^2*+5*2 uit op 250. Strikt rechts rekenen in de popster context geeft vaak ongebruikelijke resultaten. Terwijl we carets ^ oplossen met majoriteit precedentie (hogere operaties eerst), en daarna pas sterren * met minoriteit (lagere operaties eerst). Zo wordt a^b*c groter als a>b1 geldt, maar is normaal a**b*c nog groter, in vergelijking met +a**b*c uitgewerkt als popsterren. $ 2.3. Popsterren Popster supermachten zijn primitief recursieve operaties, die we stapsgewijs uitwerken zonder haakjes te gebruiken, met een plus *+ of "pop" teken in de ster operator. Hoe meer sterren in de operator *_^[..] hoe groter de uitgedrukte getallen. $ 2.3.1. Definitie "Tetratie" is de eerste echte supermacht, aangegeven met drie *** sterren of twee ^^ carets in de operator. De tetratie operatie herhaalt de elementaire machten ** of ^ met als mogelijk resultaat een toren van exponenten, die 'r-l' van de top macht naar beneden moet worden opgelost. Zoals Knuth liet zien bij supermachten in reeksen, waar we een toren bouwden van voorgaande operaties met de constante a en b verdiepingen. a***b1 = a**..a :b In ons popster systeem nemen we de top operatie eerst apart en werken deze met voorrang uit. De reeksen of torens krijgen we dus niet in hun geheel te zien. De supermacht iteratie breekt elke stap op rechts een volgende verdieping af. Definitie voor de evaluatie van 'PopSter' supermachten. Door de eerst aansluitende vorm van rechts =` te selecteren en die regel uit te voeren, geldt vanzelf steeds dat b>0 positief is. Maar de operator *{c≥0} kan leeg zijn. -PS.0. +a = a -PS.1. +a*{c}+b =` +a*{c}b -PS.2. a*{c1}1 =` a -PS.3. a*{c1}b1 =` a*{c1}b*{c}+a Een operatie met popster *{c}+ wordt dus pas actief, als links ervan een plus geschreven wordt. Deze "pop plus" regel is ook nodig om op te tellen en staat daarom eerder in de lijst. Variabelen zijn "gretig" naar enen, zodat elk getal a in de regels compleet is, zonder rest deel in de expressie. Stop '0.' elimineert de pop systeem plus voor de uitkomst. Stop '1.' elimineert plus uit de tweede popster van rechts. Stop '2.' elimineert de ster operatie bij basis exponent 1 . Stap '3.' introduceert vermindere popster en exponent a . Stapsgewijze evaluatie van popster supermachten kan toe met vier regels, zonder gebruik van haakjes. De definitie in dit hoofdstuk lijkt het eenvoudigst. Als we de optie plus +X aan het begin van popster expressies zouden weglaten en de operatie a*{c}+b komt in de evaluatie alleen te staan, dan is er een regel nodig om die enkele pop plus te elimineren. Of anders kunnen we dat misschien voorkomen door regel twee aan te passen, zodat a*{c1}1*{c}+b meteen tot a*{c}b reduceert. We kunnen voor het gemak in de uitwerking van pop expressies ook carets gebruiken, waarbij de operaties *{c1} en ^{c} gelijk zijn en strikt rechts associatief 'r-l' als popster supermachten worden uitgewerkt. $ 2.3.2. Evaluatie Om de supermacht 2^^^3 versneld uit te werken, prepareren we eerst twee tussenresultaten. De "superkwadraten" gebruiken we als afgeleide regel '4a' van popsterren. a^{c}2 := +a*{c1}2 =3 +a*{c1}1*{c}+a =2 +a*{c}+a =1 +a*{c}a := a*{c}a Bij evaluatie van rechts schrijven we de toegepaste regel nummers aan de rechter kant van het is = teken als subscript, voor extra informatie. De reductie van supermachten 2^{c}2 tot getal 4 noemen we de afgeleide regel '4b'. +2*{c1}2 =4a 2*{c}2 == 2*2 =3 2*1+2 =2 2+2 =1 4 Omdat 2*{c1}2 tot 2*{c}2 uitwerkt, itereren we dit verder == tot 2*2 of zelfs tot 2*{0}2 wat de uitkomst 4 optelt. De pop plus eliminatie van regel '1.' volgt in de evaluatie na een superster regel en zo'n duo kan dan ook = ineens. Een complete iteratie van duo stappen met regel '3.' eindigend met regel '2.' geven we wel als reeks == aan. +2****3 := 2^^^3 =3 2^^^2^^+2 =3,1 2^^^1^^+2^^2 =4b 2^^^1^^+4 =2,1 2^^4 =3 2^^3^+2 =3,1 2^^2^+2^2 =4b 2^^2^+4 =3,1 2^^1^+2^4 ≡2 2^+2^4 = 2^+2*+2*4 = 2^+2*+2+6 =1 2^+2*8 == 2^16. == 65536. Als bij a^{c}1 de exponent tot 1 beperkt is, kunnen we dit in elke positie ≡ in de expressie vervroegd tot a reduceren. Op dezelfde wijze als hierboven leiden we voor simpele supermachten 2^{c}3 een hele reeks met afnemende pop operatoren af. Maar in de evaluatie neemt bij elke supermacht van rechts op links de exponent toe. 2*{c1}3 = 2*{c}4 = 2.*{i}+2..4 c:1 Een ander voorbeeld, de tetratie 3^^3 uitgewerkt met popsterren, geeft nog net geen groot getal. +3****2 := 3^^3 = 3^^2^+3 = 3^^1^+3^+3 = 3^+3^3 = 3^+3*+3*3 = 3^+3*+3+6 = 3^+3*9 == 3^+27. = 3^27. == 7625597484987. De grens van wat grote getallen zijn, is ongeveer wel bij de tweede exponent te trekken. We stellen voor om de uitkomst van a*{c}b waar a≥2 en b>2 bij tetratie of hoger c>2 en som abc>9 om precies te zijn, "groot" te noemen. Input supermachten zijn met twee type tekens: enen 1 en sterren * te noteren. Tijdens de evaluatie van popsterren komt daar de plus + als solo haakje bij. In het verloop van popster supermacht tot getal 1.. kan elke expressie worden opgeslagen met slechts drie type tekens. Dakjes ^ of carets en ^+ popcarets, cijfers en decimale getallen (met punt) zijn secundair en beschouwen we als substituut of afkorting. Welke tekens voor de definitie van een werkend popster systeem essentieel zijn is onduidelijk. De taak om de trinaire evaluatie van binaire supermachten in een Busy Beaver algoritme te emuleren laten we over aan de wiskundigen… $ 2.3.3. Vergelijking We kunnen de grote supermachten alleen nog ruwweg met elkaar vergelijken. In dit voorbeeld neemt het absolute verschil < tussen twee minoriteit superster operaties bij grotere c toe. Terwijl dit verschil in de exponent van de uitgewerkte reeksen toch niet bijster significanter kan 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 deze reeks is bij de factor * het verschil 1 , bij de macht exponent ** wordt dit 11. en de tetratie exponent verschilt al bijna 10^13. afgerond. Maar op de schaal van hun superoperatie blijven deze verschillen dus insignificant. In de expressie a^{d}c*{d}+b ontpopt de supermacht rechts als hoogste exponent van de supertoren a*{d}..b :c wat wel significant kan zijn. De extra resolutie van die popster in de weergave van grote getallen vormt een aanvulling op ons rekenapparaat, waarmee we de evaluatie bij array functies nauwkeuriger kunnen volgen. Zo helpen popsterren om de oceaan van supermachten en de naburige eilanden met supermachtige getallen in kaart te brengen. Pas in 1976 werden de supermacht operaties uitgevonden door Donald Knuth, met als teken oppijlen ↑{c} in zijn essay "Omgaan met eindigheid". Dezelfde dubbele recursie φ_c(a,b) inclusief Ackermann functie was al te vinden bij David Hilbert in zijn artikel "Over het oneindige" uit 1925. De Ackermann functie is in wezen een functie die de superoperator teller met een parameter bepaalt (dus niet met het aantal van zijn functie parameters, wat nog primitief recursief zou zijn). De hoogte van een supermacht *{S} kan ook met een subexpressie worden aangeven, met name als een supermacht die dan eerst uitwerkt. En dit nesten van suboperaties kunnen we itereren, niet in de exponent dus, maar door substitutie in de ster of caret teller van de operator. Een voorbeeld hiervan vormt het grootste getal uit de wiskunde, zoals Martin Gardner dit publiceerde als het beroemde Getal van Graham. Door supermachten te nesten met Knuth's oppijlen, tellend als carets. 3↑{..3↑↑↑↑3..}3 :63: = 3^{..4..}3 :64: = 3*{..4..+1}3 :64: De duorep :d: herhaalt de selecties aan beide kanten van de expressie. Plaats elke selectie naast 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. Het nesten van supermacht operatoren werkt zoals recursie van de Ackermann functie. Zo maken we grote getallen die we "hypermachten" zouden noemen, of de "getallen van Graham". $ 2.3.4. Functie vorm Evaluatie van supermachten kan makkelijker in een functie, die we hier langzaam opbouwen vanuit de operatie vorm van popsterren. Om de popster definitie erbij te houden, klik op zijn icoon @ en de box koppelt los aan het venster. Popster operaties zijn relatief economisch. Afgezien van de grootte van de variabelen blijft het aantal wachtende operaties in de uitwerking beperkt. Dat is het voordeel van popsterren boven evaluatie van supermachten met reeksen. a2*{k1}2 = a2*{k1}a2 = a2*{k1}a*{k}+a2*{k}a2 == a2*{i1}a*{i}+..aa4 k:0 In dit voorbeeld was de expansie maximaal, met alle ster en popster operaties 'r-l' op elkaar volgend, maar er kunnen ook sterduo's ontbreken. Dan hebben de operaties a*{c}b die we uitwerken volgens de 'PopSter' definitie gedurende de evaluatie deze formule. a*{c_i+1}b_i*{c_i}+..b_0 k:1 elke b>0 en c_i1>c_i≥0 Elke aanwezige superster heeft een ster * meer dan de erop volgende popster, en de grootte van deze duo's loopt af naar rechts. Stel nu, dat de ontbrekende supermachten in deze reeks een operand b_i=0 hebben, wat een hard nul teken blijft, zolang deze tussen sterren staat. Maar dat in de evaluatie dit hele sterduo reduceert tot een nul, die vanzelf wegvalt 01 = 1 tegen het erop volgende getal. De invoeging van nul exponenten passen we toe als een nieuwe hulpregel. - a*{c>0}0*{d}+ =` 0 De volgende inclusieve formule geeft in de evaluatie expressie elk sterduo in sequentie weer. Met exponenten b≥0 die leeg kunnen zijn. a*{i}b_i*{i-}+..b_0 k:1 Als voorbeeld een versnelde uitwerking daarmee. 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^^^2^^+4 = 2^^^1^^+2^^4 == 2^^65536. Alleen de superexponenten b en het aantal carets ^{c} of sterren *{c1} zijn variabel en kenmerkend. Het is overbodig om in de evaluatie expressie de constante a voortdurend aan te halen. Ook komt ieder sterpaar nu erin voor, in volgorde 'l-r' aflopend, zodat de hogere supermachten links wachten. Om de informatie die een popster expressie tijdens evaluatie bevat op te slaan, hebben we een constante a nodig en al de variabelen b_i in een volgorde. De positie in de variabelen rij geeft dan het aantal sterren van de operator. 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 De essentie van deze popster expressie is hier tot zeven getallen gereduceerd. We draaiden de volgorde van de exponenten ook om, zodat de evaluatie van de rij 'l-r' in leesrichting zal verlopen, in aanvang de minder significante variabelen. De poptelling +1 rechts is in feite alleen voor de vorm en kan in een functie met een andere regel worden ondervangen. Getal 0 schrijven we zonder enen. De superoperator in a*{k}b telt 1 ster minder, dan het corresponderende aantal komma's a,{k1}b dat tussenin staat in onze poprij functie. 2*{6}3 = 2*****2****+2***2 11,{7}111 = 11,,,,11,,11 Zo zetten we superster expressies met pop plus in de evaluatie om naar een functie rij, die met twee tekens toe kan en een kortere lengte geniet. Ook de regels voor de evaluatie van zulke functie expressies zijn simpeler. Het van popsterren afgeleide functie algoritme "Adam" zien we hierna. $ 3. Rij functies De systemen in dit hoofdstuk zijn beperkt tot een enkele rij variabele getallen. We ontwerpen de primitief recursieve functies Adam en Eva, die rij expressies tot een getal 1.. evalueren in de orde van grootte van de a*{k}f supermachten. $ 3.1. Systeem Adam In systeem 'A.' van "Adam" worden iteraties op rij 'l-r' uitgewerkt, zoals popster exponenten van top-down toenemende supermacht operaties. Ons motief bij de constructie van Adam is natuurlijkheid. Cellen voor iteraties tellen we af tot 0 en hun structuren kunnen leeg komen te staan. $ 3.1.1. Primitieve recursie Om zo zuinig mogelijk te zijn met type tekens, introduceert systeem Adam geen ronde haakjes in de uitwerking, maar telt steeds een kopie van de constante a bij de som in b en schuift die subtotalen door naar rechts om afgetelde iteraties opnieuw op te laden. Zonder substitutie van subexpressies (X) is er geen functie recursie, die een parameter overschrijft met een hele expressie, zoals bij Bird of Conway. Daarom komt Adam wat langzamer op gang. Adam's expressies op de rij bestaan uit tekens 1 voor de variabele getallen, met een enkele komma , als separator ertussen, links van elke cel. Voor iteraties die afgeteld zijn, kunnen we naar keuze een cijfer 0 schrijven of deze gewoon leeg laten. Meerdere komma's ,.. op rij stellen in Adam dus geen dimensionale overgangen voor, maar een serie lege cellen. Over de structuur van de eerste rij zal de functie snelheid van Adam significant achterblijven bij die van Conway's pijlketens en Bird's lineaire array. Maar gezien de beperking van twee tekens valt de expressieve kracht van Adam reuze mee. Wat we "primitief recursief" noemen in Adam is het herhaaldelijk optellen van een kopie van a en het opschuiven of opladen van subtotalen b naar lege iteraties ,0 rechts in de rij. Ondanks dat de eerste iteratie over c alleen maar vermenigvuldigt, bouwt Adam over de hele rij supergrote getallen op. Evaluatie van array functies is te beschouwen als een doorlopend proces van expressie afbouw en getal opbouw. Adam reduceert elke reeks in de rij apart tot een subtotaal. Tel 1 af van de iterator na die reeks en laadt het subtotaal op als het aantal volgende iteraties ervan. Tot alle iteraties zijn afgeteld en de uitkomst een natuurlijk getal n is, een serie enen 1.. :n van die lengte. $ 3.1.2. Definitie 'A.I' De Adam functie evalueert supermacht expressies met alleen de tekens 1 en , en drie primitieve regels, toe te passen op een rij parameters. Een afgeteld rij deel met lege iteraties kan tot op het laatst rechts blijven staan. Definitie van Adam's systeem 'A.' over rij structuur 'I.' voor elk aantal variabelen. De som variabele b≥0 en het aantal komma's ,{k≥0} kan nul zijn, dus leeg. -A.I.1. a,b,{k} = b -A.I.2. a,b,1R = a,ab,R -A.I.3. a,b1,,{k},1R = a,,1,{k}b,R 2= a,a,,{k}b,R De evaluatie regel met teken = geeft aan beide zijden de hele expressie. Links staat de selectie vorm en rechts ervan de vorm na evaluatie. Voor het expressie deel rechts, dat ongewijzigd blijft bij toepassing, gebruiken we de tekst variabele R die ook leeg (zonder tekens) mag zijn. Gedurende de evaluatie is steeds precies één van de regels toepasbaar. Regel '1.' neemt totaal som b als uitkomst en stopt de evaluatie. Regel '2.' telt een kopie van a op bij de som variabele b . Regel '3.' verplaatst de som b om rechts een afgetelde iterator op te laden. Laat daarvan slim 1 achter in eerste iterator c om daarna a bij de lege som te tellen. De Adam functie rij en zijn evaluatie regels zijn congruent aan die van de popster supermachten. Maar Adam sommeert de lage supermachten aan linker zijde, terwijl lagere popster operaties op de top rechts worden gestapeld. De rij structuur blijft bij Adam onveranderd, terwijl de reeks popster operaties pulseert, hoewel niet zo sterk als bij de expansie van Knuth's supermachten. Toch wijken de regels voor popsterren beduidend af van die voor Adam. Een hele andere verbeelding van wat stap na stap in precies dezelfde dubbele recursie resulteert, zoals we aantonen in sectie $.3.2. hieronder. Merk op dat expressies van de vorm a,,,{k>0}1R buiten deze regels voor systeem 'A.' vallen en derhalve niet reduceerbaar zijn. We presenteren daar nu een oplossing voor met twee varianten op Adam, waarmee we ook de lege cellen van rechts kunnen opruimen. $ 3.1.3. Variant 'Aa.I' In deze uitgebreide definitie van Adam laten we de resterende komma's van afgetelde variabelen vanaf rechts wegvallen. Om een regel toe te passen scannen we de expressie vanaf links. Het passieve expressie deel dat rechts nog kan volgen wordt in de regels niet weergegeven, maar zal gelijk blijven in de evaluatie. Het "scan" teken ` staat voor een passieve passage die we overslaan. Stel b≥0 bij de som variabele. Een reeks :k afgetelde ,0 variabelen tussenin bestaat eigenlijk uit ,{k} lege cellen. -Aa.I.0. a,`,0 = a,` -Aa.I.1. a,b = b -Aa.I.2. a,b,c1 = a,ab,c -Aa.I.3. a,b1.,0..,f1 :k1 = a,a.,0..,b,f :k De laatste regel functioneert als de twee stappen van opladen en optellen uit de primitievere definitie 'A.I' van Adam en verandert het systeem niet. Door deze regel alsnog te splitsen worden expressies van de vorm a,,R ook reduceerbaar. Na regel '3a.' moet steeds '3b.' worden toegepast, zodat de volgende oplading met de constante a kan plaatsvinden. -Aa.I.3a. a,b1.,0..,f1 :k>0 = a.,0..,b1,f :k -Aa.I.3b. a.,0..,b1 :k>0 = a,a.,0..b :k Hier stellen we de expressie met waarde b=0 onder c=0 gelijk aan waar b=1 zou staan. In het compacte systeem 'A.' viel deze niet onder de regels. In systeem 'Aa.' kunnen we deze formule gebruiken om de supermachten rechtstreeks uit te drukken. a*{c>0}b = a,{c1}b Het aantal komma's in Adam staat dan gelijk aan een type superoperator, die met ,{2} tekens vermenigvuldigt en met ,{1} teken de variabele b kiest. We zullen deze formule bewijzen in een lange vergelijking van de Adam array functie met popster operatoren, na de variant hieronder. $ 3.1.4. Variant 'Ab.I' In een nieuw definitie format benoemen we hier alleen die variabelen en tekens, die voor de selectie in de expressie en de wijziging ervan nodig zijn. We proberen de regels uit de definitie in volgorde uit, tot er een complete match van de selectie vorm(en) gevonden wordt. Evaluatie reduceert de expressie dan een stap verder, in de richting van de uitkomst tot 1.. getal. Scan bij regels met `= de gegeven expressie vanaf de linker kant naar rechts. In het geval dat twee 'l-r' regels van toepassing zijn, gebruiken we ofwel de eerdere regel in de definitie lijst, ofwel de regel met de selectie die eerder links in de expressie begint of eindigt. In een correcte definitie blijft die regel dezelfde. Een spatie in een regel beduidt het einde van het linker gedeelte van de vorm. Zoek dan 'l-r' verder naar de eerstvolgende match voor het rechter gedeelte. Over de spatie slaat de scan elke mogelijke andere passage over. Deze blijft passief en de tekst ervan wordt onveranderd overgenomen. Maar deze kan ook leeg zijn, als beide vormen op elkaar aansluiten in de expressie. Een toegevoegd vraagteken =? geeft aan dat de regel in de evaluatie een lagere prioriteit krijgt. Deze komt pas aan bod, als de andere regels uit de definitie geen match meer geven. Pas bij de definitie van systeem 'Ab.I' de regels in volgorde toe, maar ruim de rest komma's pas op als alle iteraties zijn afgeteld. Vooraf is b≥0 gesteld. -Ab.I.0. a,b, `=? a,b -Ab.I.1. a,b = b -Ab.I.2. a,b,1 `= a,ab, -Ab.I.3. a,b1, ,1 `= a,a, b, We breiden systeem 'Ab.' uit met expressies a,0,0,R door regel '3.' in drie regels te verdelen. Zo nemen expressies met lege b onder lege c een stap extra van de iteratie(s) rechts, om via b=1 kopie a te substitueren. -Ab.I.3a. a,,, 1 `= a,1,, -Ab.I.3b. a,b1,,1 `= a,,1b, 2= a,a,b, -Ab.I.3c. a,b1,, ,1 `= a,1,, 1b, == a,1,,1 b, 3b= a,,1, b, 2= a,a,, b, De speciale expressie a,,{k>1}2d evalueert dus tot a,a,{k}d en telt een stap meer af dan in systeem 'Aa.' Dit lijkt rekenkundig juister en geeft wat extra getallen simpel weer. Dan moeten we een expressie van de standaard supermachten in 'Ab.' met een basiswaarde b=1 schrijven; maar beginnend met de ** macht operator. - ab = a,b,1 - a*b = a,,b - a*{c>1}b = a,1,{c}b Dezelfde formule als in het compacte systeem Adam 'A.' Dit is een speciaal geval uit de vergelijking van de Adam rij met popster supermachten die nu volgt. $ 3.2. Popster Adam We vergelijken hier de evaluatie van de Adam rij functie 'A.I' met een stapeling van popster supermachten. Na wat rekenwerk tot aan tetratie in vijf parameters volgt vanzelf de algemene vergelijking voor een hele rij parameters. $ 3.2.1. Tetratie op rij van vijf Expressies met drie tot vijf parameters in systeem 'A.I' zijn equivalent aan de eerste popster operaties van * tot *** tetratie. In de voorbeelden noteren we voor Adam de regel nummers links van het = evaluatieteken en voor popster operaties de regel nummers rechts ervan. Hoe optellen en vermenigvuldigen parallel in beide systemen verloopt. a,b,1c = +a*c1+b 2= a,ab,c =3,1 +a*c+ab 2== a,a*c+b,1 == +a*1+a{c}b 2= a,a*c1+b, =2,1 +a{c1}b 1= a*c1+b =0 a{c1}b Evaluatie van een macht met vier parameters in Adam en met popster operaties. Bij het aanhalen van dezelfde regel of herhalen van een bewezen afleiding laten we regel nummer(s) hier weg. Ook de start plus van het popster systeem houden we snel voor gezien. a,1,,2d = +a**d2*+1 3= a,,1,1d =3,1 a**d1*+a*1 2= a,a,,1d =2 a**d1*+a 3= a,,a,d =3,1 a**d*+a*a 2== a,a*a,,d == a**d*+a{a} == a,a^d1,,1 == a**1*+a^d1 3= a,,a^d1, =2,1 a*a^d1 2== a,a^d2,, 1== a^d2 We zetten popster operaties in in Adam's parameters om de evaluatie op de rij precies te kunnen volgen. En geven alleen de langste herhaling met == aan. a,b,c,d2 2= a,a*c+b,,d2 3= a,,a*c+b,d1 2= a,a*+a*c+b,,d1 3,2= a,a**2*+a*c+b,,d == a,a**d2*+a*c+b,, 1= a^d3*c1 {b=a} = a^d4 {c1=a} De iterator e van tetratie domineert de kleinere operaties. Zolang met name d niet significant groter is dan a of triviaal klein, tellen de voorliggende parameters ongeveer twee etages bij de toren e2 met machten op. a,b,c,d,e = a,a*c+b,,d,e = a,a^d1*c1,,,e {b=a} := a,1,,a^d2,e- {c1=a} = a,a^a^d2,,,e- == a,.a^..d2,,,1 :e = a^^e1^+d2 = a^^e2 {d2=a} Precies gesteld zo. Maar voor alle d~a mogen we Adam's rij van vijf zo afronden. Want de hogere supermacht is steeds dominant. $ 3.2.1. Supermachten over de rij We reduceren Adam arrays trapsgewijs. Elke deelrij van links werkt apart uit tot een tot een popster subtotaal, dat op de superexponent van de rechts volgende iteratie wordt genoteerd. We hergebruiken resultaten uit de vorige sectie, om ineens van parameter trede op trede te stappen. In dit voorbeeld volgt de getrapte "pentatie" supermacht. a,b,c,d,e,f = a,a*c+b,,d,e,f = a,a^d*+a*c+b,,,e,f = a,a^^e^+a^d*+a*c+b,,,,f = a,.a^^..e^+a^d*+a*c+b :f1 = +a^^^f^^+a^^e^+a^d*+a*c+b = +a****f***+a***e**+a**d*+a*c+b In deze popster expressies, die we strikt 'r-l' uitwerken, wisselen de supermacht en popmacht operaties elkaar af. Door majoriteit precedentie te gebruiken, waar grotere caret operatoren voorrang krijgen, kunnen we dit pentatie resultaat vereenvoudigen tot: a^^^f1+^^e1+^d1+*c+b Bij een iterator ,1 in de Adam rij zal die exponent variabele *{k}p uit de formule wegvallen. De expressie a,b,1,1,1,1 is dan bijvoorbeeld gelijk aan de getrapte popster expressie +a^^+a^+a*+a+b wat we met minoriteit precendente sterren als a***a**a*ab noteren. Bij een lege iterator cel ,0 in de Adam rij ontbreekt het hele betreffende ster popster construct a*{k1}p*{k}+ in de vergelijkingsformule. Als we onder een iterator in Adam de hele lagere trap leeg laten, dan geeft het aantal komma's ,{k>0} dat op basis a,1 volgt, direct het aantal sterren *{k} aan van de uitgedrukte supermacht. a,1,{k1}p2 = a,a,{k1}p1 = a,a,{k}a-,p == a,a*{k}a,{k1}p == a,a.*{k}a.. :p1 = a*{k1}p2 Algemene vergelijkingsformule van expressies 'A.I' met getrapte popsterren. Beide kanten in 'rep' notatie, met het resultaat afgerond tot supermacht, door de insignificante p_i~a op te tellen als 1 bij de volgende superexponent. a,b.,p_i.. 1:k = a*{i}p_i*{i-}+..b k:1 ~ a*{k}(p_k+1)*{k-}+p_k- ~ a*{k}(p_k+2) Als de superfactor p_k- relatief groot is, dan kan de bijtelling ervan in de superexponent afwijken. Beschouw b=p_0 hierbij. Lastig aan Adam 'A.I' zijn de twee regels in serie: met de substitutie van kopie a in cel b die volgt op het opladen van een iteratie. Ook zou het systeem zuiniger kunnen omgaan met komma reeksen ,{k>1} door die in te zetten als separatoren voor multidimensionale array ruimtes. Het volgende systeem van Eva lost die problemen op. $ 3.3. Systeem Eva Met systeem 'E.' van "Eva" zullen we de grootste getallen getallen noteren met zo min mogelijk type tekens en regels. Ook telt Eva iteraties steeds tot rest 1 af, zodat de separatoren zelf gescheiden blijven. $ 3.3.1. Definitie 'E.I' Eva's rij systeem 'E.I' opereert net als Adam's rij 'A.I' in het gebied van de supermachten. Dit staat in de theorie van recursieve functies bekend als de Grzegorczyk hierarchie. De uitgedrukte getallen lopen in Eva gestaag bij de gewone supermachten van Knuth en Adam vandaan, wat een exacte vergelijking compliceert. Eva zal bij gelijke expressies enigszins kleiner zijn, maar dit verschil blijft insignificant. Definitie van Eva's systeem 'E.' over een rij 'I.' van variabelen. -E.I.1. a,b.,1.. = ab -E.I.2. a,b1.,1..1R :k>0 = a.,1..ab,1R :k Elke lineaire array in Eva is op te lossen met deze twee regels: Stop regel '1.' geeft de uitkomst als er geen iteratie rechts meer volgt. Stap regel '2.' telt ab1 op in de som variabele, of laadt hiermee de afgetelde iterator variabelen op. Pas deze regel voortdurend toe tot de expressie klaar is voor de uitkomst. Prioriteit van regels speelt in de evaluatie van Eva geen rol. Opladen met regel '2.' gaat als volgt in zijn werk. Verschuif ab uit de basis naar de cel ,1 rechts, laatste in de afgetelde reeks. Door dit te herhalen wordt die hele reeks ,1.. in de evaluatie naar links toe gevuld. De eerste oplading schuift het som totaal ab1 nog mee, waarvan na aftelling ab overblijft. Van de volgende substituties == houden we in de reeks alleen de constante ,a over. Tot links met a1 de volgende som trein weer vertrekt. a,1b,.1,..2R :k == a,1.a,..ab,1R :k Om afgetelde variabelen van rechts te elimineren, passen we de extra regel '0.' toe; naar wens eerder of later in de evaluatie. De specifieke regel '1a.' is dan genoeg om de uitkomst te geven; in plaats van regel '1.' voor onopgeruimde expressies. -E.I.0. a,R,1 = a,R -E.I.1a. a,b = ab Ook hiermee is regel volgorde voor het resultaat onbelangrijk. Een opruimregel geven we altijd het nummer '0.' en als er meerderen zijn ook een letter. Het levert wel mooiere expressies op, door wanneer mogelijk meteen van rechts op te ruimen. In Eva hebben parameters minimaal waarde 1 en blijven komma's in de rij dus altijd apart staan. Dit biedt ruimte om een andere betekenis aan series komma's ,.. geven. Als we het Eva systeem 'E.II' uitbreiden, zullen meervoudige komma's dienst doen als separatoren om ruimtes tussen dimensies te scheiden. In deze array ruimtes kunnen expressies record grote getallen uitdrukken. Zo wordt Eva kampioen in de discipline die evaluatie beperkt tot twee type tekens. $ 3.3.2. Rekenen in Eva Rekenen in het scheeflopende systeem Eva verschilt sterk met de rechtzinnige Adam. Zo is een enkele vermenigvuldiging meteen al lastig in een natuurlijke Eva expressie te noteren. Vergelijk wat simpele gevallen. Optellen werkte in systeem Adam van A(a,b,1) naar A(a,ab) naar ab met de uitkomst gegeven door de keuze regel. Ondanks de gelijke input en output, verloopt de evaluatie in Eva anders. Zowel met de twee regels uit haar definitie, als bij gebruik van de extra regels. E(a,b,1) 1= E(ab) -= ab a,b,1 0= a,b 1a= ab Eliminatie van de functie notatie nummeren we hier met minus -= als een voorliggende regel. Gewoonlijks vergeten we functie tekens E() en het verwijderen ervan, als de aangehaalde systeem definitie bekend is. Vermenigvuldig in Eva door regel '2.' te herhalen == over drie parameters. a,b,c1 2= a,ab,c == a,a*c+b,1 1= a*c1+b Door de voorwaarde dat we de tekens in de regel selectie tot 1 beperken, geldt voor de som variabele b>0 in Eva, terwijl deze in Adam leeg kan zijn. Elke grote getallen functie zal vele tussenliggende getallen moeten missen, dus dat vermenigvuldigen altijd een optelling erbij krijgt is onbelangrijk. Maar systeem Eva kan uitgebreid worden met minus units - en 0 teken. Zodat we expressies met een som variabele b=0 kunnen noteren en regel '2.' uit de selectie vorm b1 de negatieve waarde b=- haalt voor de evaluatie vorm. Zo kunnen we stellen dat de expressie a,0,c in Eva tot a*c vermenigvuldigt. De match voor b in de regel vorm is dan een min - ofwel -*1 negatief een. Anders is bijvoorbeeld 3*3 natuurlijk als E(3,3,2) te noteren. We moeten maar accepteren, dat Eva samengestelde getallen eenvoudiger beschrijft. Het loopt al snel cummulatief scheef door de extra enen. a,b,c1,d2 = a,ab,c,d2 = a,a*c+b,1,d2 = a,1,a*c1+b,d1 = a,1+a*(a*c1+b-),1,d1 = a,1,1+a*(a*c1+b),d = a,1+a*a*(a*c1+b),1,d = a,1,1+a*(1+a*(a*c1+b)),d- == a,1,.1+a*(..a*c1+b..) :d: = 1+a*(..a*c1+b..) :d1: = a*(..c2..)+1 :d2: {b=a1} ~> a^d2*c2 = a^d3 {c2=a} Vergelijk Eva met systeem Adam, waar expressies A(a,b,c,d) exact op de popmacht a^d*+a*c+b uitkomen. Dit scheelt ongeveer een factor. E(a,1,1,d1) = a,1,a1,d = a,a1,a,d <~ a^d*a2 < A(a,1,1,d1) = a,a1,,d1 = a,a,a,d = a^d1*+a1 <~ A(a,a1,a,d) We verwachten dat bij gelijke expressies de superexponent in de uitwerking bij Eva 1 minder is als bij Adam. Maar omdat de som in Eva 1 extra oplaadt, loopt zij steeds verder uit de pas met de getrapte popsterren van Adam. $ 3.3.3. Eva is supermachtig Verder in Eva systeem 'E.I' met de hogere cellen op de rij. Haar eerste vijf parameters drukken een rommelige tetratie uit. a,b,c,d,e {b~a c=a} ~> a,a^d1,1,1,e ~> a,1,1,a^d1,e- ~> a,a^a^d1,1,1,e- ~> a,a^^e^+d1 ~> a^^e1 {d1=a} Eva stapelt herhaaldelijk een exponent minder dan systeem Adam, waar dezelfde expressie ongeveer tot a^^e1^+d2 uitwerkt. Maar de minimale expressie met tetratie E(a,1,1,1,e) in Eva is vrijwel gelijk aan de exacte tetratie A(a,1,0,0,e) in Adam, iets groter zelfs. a,1,1,1,e1 = a,1,1,a1,e = a,a1,a,a,e ~> a^^e^+a1 ~> a^^e1 Expressies van Eva zijn alleen bij benadering uit te drukken in Adam of met popsterren. De complexiteit van deze vergelijking neemt op fractal-achtige wijze toe. We zouden dit "supermachtige getallen" kunnen noemen. Waarvoor de dichtstbijzijnde Knuth supermachten alleen als ongeveer en groter ~> of ongeveer en kleiner <~ bepaald kunnen worden. Benader systeem 'E.I' met popster supermachten, zodat elke cel meer op de rij een operator ster bijtelt. a.,1..,p1 :k = a,1.a,..p :k ~> a*{k}p*{k-}+a1 ~> a*{k}p1 Of in het algemeen voor een rij met lengte k1 die in Eva begint door a+p_0 op te tellen met een lege *{0} ster operatie. a.,p_i.. 1:k ~> a*{k}p_k*{k}+p_k- ~ a*{k}(p_k+1) De hoogste superexponent van de parameter p_k rechts is dominant. Alle voorgaande iteraties tellen daar in Eva ongeveer 1 stap bij op, tegen 2 in Adam. Maar de positie ervan, dat is de rij lengte, die het aantal supermacht sterren telt, wordt in het vervolg het dominantst. In onze systemen 'A.I' en 'E.I' loopt de hele rij gelijk met een dubbel recursieve functie, waarvan de tweede iteratie onze rij lengte aftelt. We vergroten de eerste rij recursief, lengte op lengte, met als uitkomst de "getallen van Graham". En dit is nog maar het begin van een klasse van hogere functies met tripel en meervoudige recursies. Door subtotaal b op te laden naar de tweede rij, zouden de variabelen daar gelijk moeten gaan lopen met die van Bird's lineaire array, die maximaal is. Dit zullen we bewijzen met behulp van Conway's pijlketen, die ontstond uit Knuth's supermacht pijlen en daarmee op natuurlijke wijze uit te breiden is. $ 4. Pijlfuncties Doel is om de rechtse pijlen → van Conway uit te breiden met oppijlen ↑ van Knuth, in een nieuw systeem van superpijlen. En om hiermee getallen te maken die net zo groot kunnen worden als met Bird's lineaire array. $ 4.1. Supermacht pijlen De oppijlen van Donald Knuth drukken de supermacht operaties uit, die in het verlengde liggen van optellen, vermenigvuldigen en machtsverheffen. Deze functie recursie stond bij John H. Conway model voor zijn pijlketen notatie. $ 4.1.1. Dubbele oppijl Gegeven de operator ↑ van machtsverheffen schreef Knuth de erop volgende operatie van tetratie ↑↑ met twee oppijlen. Die tetratie verandert bij Knuth ineens in een toren van exponenten. Vervolgens wordt elke macht ervan van de top rechts op links uitgewerkt. Wij reduceren tetratie in stappen, door links ervan macht na macht in te voegen. a↑↑b1 = a↑a↑↑b == a↑..a↑↑1 :b = a↑..a :b Door dit dan weer operatie ↑{c1} na operatie ↑{c} te herhalen, kunnen we alle hogere supermachten uitdrukken: als een reeks of toren van voorgaande pijloperaties, die 'r-l' van boven naar onder wordt uitgewerkt. We kiezen ervoor om oppijlen met voorrang en strikt van rechts op links uit te werken, ook al staat er links een hogere operatie. Bij dakjes of carets ^{c>0} passen we de gewone majoriteit precedentie toe. Daarna volgt evaluatie van minoriteit supersterren *{c1>0} waarbij operaties met minder sterren voorrang hebben (vermenigvuldiging eerst). Dit brengt variatie aan in het gebruik van supermacht operatoren. Het lege optellen *{0} is direct bij unaire getallen, maar plus + optellen komt laatst. Voor nu kunnen we voor oppijlen ↑_^[..] een gelijk aantal carets ^_^[..] gebruiken, dan blijft de operatie dezelfde. Of noteer bij supersterren *_^[..] een extra ster. Tetraties worden al gauw onbegrijpelijk groot. 4^^^2 = 4^^4 = 4^4^256 = 2^2^513 ~ 10^10^154. ~ 80.59^^3 ~ (79.8^^2)^^2 ~ 2^2^2^2^3.17 ~ 2.3279574277^^5 Het getal in dit voorbeeld is fysisch niet meer decimaal weer te geven. Ook niet als elk kleinste deeltje in ons heelal een cijfer voor zou stellen. Toch konden we er bij benadering ~ een beetje mee rekenen. Grotere supermacht operaties kunnen we alleen nog algoritmisch vergelijken. $ 4.1.2. Knuth's oppijlen In onze stapsgewijze definitie zijn de oppijl operaties strikt rechts associatief. Steeds moet die regel met rechts accent =` worden uitgevoerd, waarvan de selectie vorm op de meest rechtse positie in de expressie eindigt. Als twee regels dezelfde vorm selecteren, voer dan de eerste regel in de lijst uit. We tonen ook de hele reeks, na alle stappen te herhalen == van een recursie, wat Knuth zelf ineens noteerde. Definitie voor Knuth's oppijlen 'Kn.' in stappen, gebaseerd op vermenigvuldigen. Stel b>0 en c>0 zodat er na evaluatie een exponent waarde blijft staan. -Kn.1. a↑b1 =` a*a↑b == a*..a :b -Kn.2. a↑{c}1 =` a -Kn.3. a↑{c1}b1 =` a↑{c}a↑{c1}b == a↑{c}..a :b Geef ook de regels voor de operaties die vooraf gaan. -Kn.0a. a+b =` ab -Kn.0b. a*1 =` a -Kn.0c. a*b1 = a+a*b == a+..a :b Net als Conway's pijlketens en popster supermachten kunnen we Knuth's oppijlen ↑{c>0} strikt rechts associatief reduceren tot een toren van machten en uiteindelijk tot een unair getal. 3↑↑↑3 = 3↑↑3↑↑↑2 = 3↑↑3↑↑3↑↑↑1 = 3↑↑3↑↑3 = 3↑↑3↑3↑3↑↑1 = 3↑↑3↑3↑3 = 3↑↑3↑27. = 3↑↑7625597484987. == 3↑..3 :7625597484986 Dit lukt geheel zonder haakjes, door de rechts geselecteerde operatie tot een toren uit te werken, ook al staan links nog grotere oppijl operaties te wachten. $ 4.1.3. Oppijl varianten We zouden oppijlen ook anders kunnen beginnen. Bijvoorbeeld door in de eerste regel direct en vanaf rechts op te tellen. Als de enkele oppijl ↑ door eliminatie wegvalt en optelt zou dit een "foppijl" zijn, die immers niets toevoegt. - a↑b =` ab Zulke foppijlen gaan langzamer van start, wat 2 supermacht tekens ** in de operator scheelt. Zodra het aantal oppijlen zichzelf recursief bepaalt, wordt dit verschil insignificant. Dat gebeurt bij wat we Graham's getallen noemen. Bij de tweede dubbele recursie in Conway's vierde keten maakt het niet meer uit wat voor operatie we in de oorsprong bij regel '1.' namen. De rechtse oppijl a#↑ is wezenlijk een methode om links ervan een kopie van de constante a en de voorgaande operator # af te splitsen, wat we in regel '3.' van de Knuth recursie stap zagen. Dat de enkele koppijl de lege operatie invoegt en de kopie a direct optelt klopt daarbij beter. Iedere stap verdubbelt zo de operand links en het resultaat van a↑b1 is ook een macht a*2^b maar nu van twee. Dit wordt voor a>2 wat kleiner dan de oppijl a^b1 van Knuth. Onze unaire definitie 'Ko.' voor koppijlen, waar c≥0 en zonder haakjes, zodat de operatie a↑b in de recursie stap tot links optellen a↑{0} reduceert. -Ko.1. a↑{c1}1 =` a -Ko.2. a↑{c1}1b =` a↑{c}a↑{c1}b Hier noteren b en c een variabel aantal tekens: het unaire getal b van het 1 teken en de operator teller c van het ↑ teken. Voorwaarden voor b≥0 of c≥0 zijn in de definitie niet nodig. Voldoende is dat bij gelijke selectie in de expressie de eerdere regel uit de definitie prioriteit krijgt bij de evaluatie. We kunnen bedenken dat a↑↑1 tot a↑a↑↑0 reduceert en zo a↑↑0 tot 1 herleiden, maar dat valt buiten de unaire definitie. Zo zijn twee regels in de definitie en twee expressie tekens tijdens de evaluatie afdoende om deze binaire supermacht operaties uit te werken tot getal. Primitief recursieve supermachten gaan strikt genomen terug op de successor functie. Deze koppijl operaties die zonder operator beginnen met optellen of concateneren kunnen we unair recursief noemen, of losjes primitief. Als we getallen in het binaire stelsel schrijven, of digitaal opslaan in bits, dan is de koppijl macht a↑b1 simpel en snel te evalueren door getal a gewoon b plaatsen naar links te schuiven, terwijl de plaatsen rechts opvullen met nullen. Een "left shift" operatie van bits, die a.0.. :b geeft als resultaat. Werkend in eindeloze bit registers is de koppijl operatie zelf uiterst primitief. We hebben nu de keuze welke oorspronkelijke operatie we voor de enkele oppijl operatie a↑b gebruiken: machtsverheffen, optellen of herhaalde verdubbeling. Belangrijk voor de uitbreiding in een supersysteem voor Conway's pijlketens is, dat oppijlen rechts associatief worden uitgewerkt tot een voorgaande reeks. $ 4.2. Conway's pijlketen De geniale Engelse wiskundige John H. Conway bedacht een pijlketen, die veel grotere getallen noteert dan met Knuth's oppijlen mogelijk is. Deze array functie, die een rij dubbele recursies vanaf rechts reduceert zonder heropladen, werd in 1996 gepresenteerd in Conway en Guy's Book of Numbers. $ 4.2.1. Definitie Uitgangspunt voor Conway was om in zijn pijlketen a→b→c met drie parameters de supermachten a↑{c}b van Knuth's oppijlen uit te drukken. De derde parameter →c is als de supermacht operator ↑{c} in een dubbel recursieve functie. Met elke stap afgeteld van c wordt een reeks van b subexpressies genest, wat dezelfde recursie geeft, als een toren van vorige supermacht operaties a over a stapelen van b verdiepingen. Verschil is dat de rechtse pijl → geen operator is en bij Conway niet telbaar, maar net als de functie komma , een plaats aangeeft voor een parameter. Onze stapsgewijze definitie van Conway's pijlketen notatie. -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 tekst variabele X het linker deel a.→p_i.. :k van de keten voor, met een k≥0 aantal parameters p_i maar op zijn minst de constante a basis. In het algemeen kan bij dubbel recursieve functies het eerste trio a,b,1 verschillend zijn gedefinieerd. De functie recursie van Hilbert telt in de basis φ_1(a,b) op, maar de Ackermann functie φ(a,b,1) vermenigvuldigt. Beide functies gaan primitief recursief uit de startblokken. Conway's pijlketen neemt een aanloop. De eerste pijl a→b waar a→b→1 op terugvalt, staat voor machtsverheffen a^b bij Conway. Door onze herdefinitie van a↑b als "foppijl" met direct optellen, of als "koppijl" met herhaalde verdubbeling, kunnen we dezelfde pijlketen notatie ook unair primitief funderen, in de stijl van Hilbert. De vier regels van 'Co.' reduceren de hele pijlketen uiteindelijk tot een reeks oppijl operaties. De hoogte van die toren wordt recursief bepaald, zodat die laatste waarde b al groot kan zijn. Haakjes vallen weg als ze niet nodig zijn. a→b1→2 4= a→(a→b→2)→1 2= a→(a→b→2) == a→(..a→1→2..) :b: 3= a→(..a..) :b: 1= a.↑a.. :b =: a↑↑b1 Daaruit volgt via herhaling van machten, rechts op links, die elk de constante a herhaald vermenigvuldigen en dat steeds vaker, een erg groot getal. Maar we zouden de reeks oppijlen ook kunnen optellen a.. :b1 of herhaald verdubbelen van a*2^a tot en met a*2^(..a..) :b omdat het resultaat vrijwel gelijk blijft bij lange pijlketens. Dit laatste is ongeveer 2^^b1++a waarin de pop a wacht om opgeteld te worden als a2 in de hoogste exponent. $ 4.2.1. Evaluatie In Conway's pijlketens vindt in de voorlaatste cel y buiten de subexpressie substitutie plaats, terwijl binnen de recursie van y aftelt. Ook de dubbele recursie van z telt af, maar alleen rechts buiten, niet van binnen. Bij herhaalde stappen == met hoofdregel '4.' telt de steeds dieper geneste waarde van y af tot 1 waarna regel '3.' de bodem subexpressie X→1→z reduceert tot X en de dubbele recursie ervoor vrij komt. Deze hele recursie van y met een stap in alle z gaven we als dubbelzijdige herhaling weer X→(..X..)→z met hun 'rep' aantal :y: in de definitie. Gaan we door de geneste keten X te reduceren, steeds dubbele schakels af van rechts, dan levert dit in het diepste nest met a of via a→b een getal op. En kruipen we met een keten van drie a→a→c of vier a→b→a^b→d een subexpressie niveau naar boven. Als de dubbele recursie is afgeteld X→(..a..)→1 vallen schakels →1 rechts af door regel '2.' Dan reduceren die binnenste ketens via tetratie a→(..a..) of Graham superiteratie a→b→(..a^b..) tot subtotaal getal. Zo komen de getallen omhoog uit elke subexpressie, terug in de voorliggende stap van de evaluatie. Steeds grotere y borrelen op uit de diepte naar steeds verder naar rechts wachtende expressies. Alle geneste X worden van links naar rechts opgerold, totdat de top expressie X→y→z weer uit getallen bestaat. Terwijl z afneemt, bewegen in de evaluatie de geneste ketens heen en weer, omlaag en omhoog, tot ook de top pijlketen X→y→1 aan lengte verliest. Op dat moment is het subtotaal in cel y enorm en schuift terug als de nieuwe dubbele recursieve z rechts. Elke nieuw subtotaal in z overtreft de eerdere in grootte, tot de laatste hoge toren van machten uiteindelijk evalueert tot getal. Maar er zijn ook triviale ketens. Als er links te kleine ≤2 getallen staan, is dat nooit meer van rechts op te blazen. 2→2→R = 2→2→c = 2^{c}2 = 4 L→1→R = L→1→r = L En komt ergens een schakel →1 voor, dan kan deze schakel samen met de keten rechts ervan worden afgekapt. $ 4.2.3. Recreatie Het beroemde Guinness recordgetal van Graham werd door Gardner met een serie geneste oppijl tellers van Knuth aangegeven. De vergelijking ervan met pijlketens, die Conway gaf in zijn getallenboek met Guy, scherpen we hier aan. Gardner's getal 3↑{..3↑{4}3..}3 :63: van Graham ligt ongeveer: boven 3→3→64→2 is 3→3→(..3↑3..) :63: in pijlketen notatie, maar onder 2→3→65→2 is 2→3→(..2→4→7..) :63: waarin de diepste supermacht een goede benadering is van 3→3→7 (zie § 2.3.3). Zodat dit getal van Graham in de 64ste iteratie slechts drie ↑↑↑ supermachten verwijdert ligt van onze benadering (onder of boven) met Conway's pijlketens. De hoofdregel van Conway's pijlketens, die de afgetelde expressie kopie in cel y plaatst, vormt bij herhaling de "enkele recursie". De twee iteraties rechts →y→z vormen samen de "dubbele recursie" over de keten. In de supermacht functie gaat aan dit dubbel alleen het getal a vooraf. Conway verlengde dit linker gedeelte tot de keten a.→x_i.. die in elke herhaalstap onveranderd onder de dubbele recursie wordt meegenomen. X→y1→2 "recursie" = X→(X→y→2) == X→(..X..) :y: X→y1→z1 "dubbele recursie" = X→(..X..)→z :y: We nesten het passieve deel X van de expressie met het actieve deel →y→z er rechts op. Het zou dus elk mogelijke passage kunnen bevatten en de functie recursie zou hetzelfde blijven. In Conway's pijlketen eindigt deel X altijd met een variabele. En in een non-triviale pijlketen zal die variabele x>1 altijd aftelbaar zijn. Met meerdere schakels wordt die X op de bodem van de recursie actief, omdat de voorliggende dubbele recursie vrij komt op de rij, zoals eerder beschreven. Over de hele rij van in de evaluatie afwisselend recursieve en dubbel recursieve iteratoren noemen we Conway's pijlketen functie "tripel recursief". a.→x_i.. :k>2 "tripel recursie" De dubbele en tripele recursies werken hetzelfde, van rechts op links, indien een mogelijke operator die vooraf gaat in L#x_0.→x_i.. eindigt op het oppijl teken ↑ van een hogere superpijl, in onze uitbreiding van deze pijlketens. $ 4.2.4. Variatie Conway had voor de eerste schakel in zijn keten ook een oppijl a↑b kunnen nemen. Met daarbij deze alternatieve regel voor de pijloperatie →c die 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 daarbovenop een dubbele recursie. a↑y1→z1 = a↑(..a..)→z :y: Zelfs als de resterende pijlketen a↑b→1 reduceert tot a↑b en als ab optelt, zal dit evalueren tot a*{c}b supermacht. Zowel met de aparte regel voor de eerste rechtse pijl hier, als met de dubbele recursie erbovenop. Uit de herhalende oppijl ↑ volgt de equivalentie *↑ ≡ ** in de supermacht operator. Onze alternatieve oppijlen vragen wat fijnafstemming, tot in het gebied van Graham's getallen, voor de rest maakt het weinig uit. We nemen nu een voorschot op het volgende hoofdstuk, waar we a→↑z tot een lange pijlketen van Conway a→..1 :z evalueren. Om te zien welke valkuilen we in de constructie van ons vervolg systeem moeten vermijden. $ 4.2.5. Experimentatie Stel dat de rechtse pijl →c1 een aantal ↑{c} oppijlen zou toevoegen aan elke andere voorafgaande pijloperator. Als we deze hypothetische superatoren 'r-l' uitwerken zonder ze af te schermen, ontspringt er een onstopbare loop. 3→↑3→2 = 3→↑↑3→1 = 3→↑↑3 < 3→↑3→↑3 = 3→↑3→3→3 Een dergelijke regel voor de rechtse pijl → na een superpijl operatie is alleen mogelijk, als we in de evaluatie van oppijlen haakjes erbij noteren, die de superpijl exponent nesten. a→↑3→2 = a→↑↑3→1 = a→↑↑3 = a→↑(a→↑↑2) = a→↑(a→↑a) = a→a→↑(a→a→↑a-)- == a→..1 :a→..1 :a Dit zou dus een manier zijn om de lengte van Conway's pijlketen recursief uit te drukken. a→↑b1→2 = a→↑↑b1 = a→↑(a→↑↑b) == a→↑(..a..) :b: De superpijl →↑ die de ketenlengte opblaast, met de vervolgpijl → die die superpijl operatie dubbel recursief maakt, lijken snel van start te gaan. Toch wordt hiermee niet meer dan de volgende schakel op de pijlrij aangegeven. Maar met grotere superpijlen →↑{q>1} kunnen we niet op dezelfde manier superketens maken, zonder tegenspraak te veroorzaken, de onstopbare loop. Om dit te vermijden kunnen we telbare rechtse pijlen →{p}↑{q} inzetten. 3→→↑2→3 = 3→→↑↑2→2 = 3→→↑↑↑2→1 = 3→→↑↑↑2 = 3→→↑↑3 = 3→→↑(3→→↑3) = 3→→↑(3→→3→→↑2) = 3→→↑(3→↑3→↑3) = 3→↑..1 :3→↑3→3→3 Hoewel de uitgedrukte getallen significant groter worden, zouden we met deze methode onze systeem tekens danig verspillen. Onze conclusie luidt, dat de rechtse pijl operatie na een superpijl beter geen oppijlen erbovenop stapelt. Alleen de tweede pijl →c in Conway's keten is dubbel recursief over een constante en kan daarom door Knuth's oppijlen ↑{c} worden vervangen. Superpijlen →↑{c} zijn van een toenemend hogere, multidimensionale orde. We trekken het bouwen van pijlketens naar een hoger plan, door met a→↑↑b1 en de stap a→↑a→↑↑b een superketen a→↑..a :b te vormen in de tweede dimensie. Zonder nieuwe haakjes substituties, in een groots vervolgsysteem van Conway-Knuth superpijlketens. Eerdere verwarde pogingen om ketens met superpijlen te bouwen: ¶ 1. EN - Conway's row of chained arrows ¶ 2. EN - Arrows quarters (draft) ¶ 3. EN - Big Arrows Compass ¶ 4. EN - Growing Numbers in all Dimensions (draft) ¶ 5. EN - Big Arrows Compass I & II (draft) ¶ 6. EN - Conway's down arrows (draft) ¶ 7. EN - Birth of the Superdeep (arrays) ¶ 8. NL - Conway-Knuth hyper-recursieve pijlen $ 4.3. Conway-Knuth superpijlketens We construeren een hogere klasse van getallen, door aan Conway's pijlketen een separator einde toe te voegen met een lengte teller en een nieuwe regel, die werkt door herhaling met oppijlen. Knuth's oppijlen waren alleen betrokken op hun eigen reeks, maar we kunnen ze op elke separator operator toepassen. Zo breiden we Conway's pijlketen arbitrair en recursief uit met schakels. Uit de toegevoegde oppijlen in deze superatoren ontstaat een multidimensionale structuur, met daarin de volgende rijen en de verdere pijlketen dimensies. Op hun beurt kunnen superatoren recursief worden vergroot met dimensie tellers. $ 4.3.1. Superpijl begin We zijn toe aan de tweede rij bovenop Conway's pijlketen. Eerst volgt een lengte teller, die na evaluatie de eerste pijlketen rij verlengt met een reeks schakels: per stap een rechtse pijl en parameter erbij. Die lengte teller wordt daarna recursief vergroot door cellen in rijen rechts ervan te noteren. De regel voor introductie van schakels telt per stap 1 af van de lengte teller en voegt links ervan een schakel →a toe, terwijl de voorliggende rij blijft wachten. Stap na stap bouwen we de pijlketen ervoor verder op. Dit werkt zoals de oppijl van Knuth, die rechts zijn voorganger operatie herhaalt. Wat onze keuze verklaart om rijen op het einde met een superpijl →↑ af te sluiten. Hiermee bepalen we de eerste dimensies, die binnen het vlak van de superpijl dimensies liggen. De superpijl →↑ voegt een teller t aantal schakels →a vanaf rechts =` toe. Niet gescheiden door haakjes, maar in zijn geheel == als pijlketen. a→↑t1 =` a→a→↑t == a→..a→↑1 :t = a→..a :t Als op die rij teller een schakel →2 volgt, wordt de ketenlengte al recursief uitgedrukt, door de functie substitutie regel van Conway. 3→↑3→2 = 3→↑(3→↑2→2)→1 = 3→↑(3→↑2→2) = 3→↑(3→↑(3→↑1→2)) = 3→↑(3→↑3) = 3→↑(3→3→↑2) = 3→↑(3→3→3→↑1) = 3→↑(3→3→3) = 3→↑3↑↑↑3 p = 3→..1 :3↑↑↑3 Met Knuth oppijlen die voor caret supermachten staan, levert dit een pijlketen rij op met lengte van een dubbele tetratie. Maar liever nemen we de primitieve oppijlen van ons systeem 'Ko.' als basis voor superpijlketens. De enkele koppijl ↑ herhaalt een verdubbeling, door elke stap links een nieuwe kopie te maken en dit getal op te tellen. 3↑3 = 6↑2 = 12↑1 = 12 3↑↑3 = 3↑12 = 3*2^11 = 6144 3↑↑↑3 = 3↑↑6144 = 3↑..3 :6143 == 3*2^(..3..-) :6143: ~ 2^^6141^+2^12.6 -> 3^^6143 -> 2^^6144 -> 3^^3^^2 Het verschil tussen Knuth's oppijlen en de koppijlen van systeem 'Ko.' is de reeks van exponenten a versus exponenten 2 in de torens van machten. Als we nu de koppijl tetrant a↑↑b uitwerken naar een toren waar alleen de hoogste exponent afwijkt van Knuth's oppijlen, dan scheelt dit met ^a afgerond een relatief kleine pop factor a^^b*+aL2 waar aL2 een logaritme log(2)/log(a) voorstelt. Een factor, die afnemend (2^c)L2 de top exponent ^(2^c/c) vermindert. De toren a↑↑↑b van koppijl tetranten uit het voorbeeld hierboven, verschilt zelfs minder dan een tel 1 met de hoogste tetratie bij Knuth. Omdat bij beide oppijl varianten de superexponenten gelijk al de waarde a hebben, zal de top exponent bij hun hogere supermachten nog minder verschillen. De lengte van pijlketen p uitgedrukt met onze recursief verdubbelende koppijlen 3↑↑↑3 verschilt op deze schaal nog wel van de supermachten. Maar in het vervolg met recursie over pijlketens, is een systeem begin a↑b met oppijlen of koppijlen (of foppijlen die als ab optellen) geen onderscheid meer van belang. $ 4.3.2. Superpijl dimensies Recursie van ketenlengte over ketenlengte gaat al gauw pijlketens diep. Benoem met p de pijlketen uit de vorige sectie, met zoveel schakels als een forse tetratie. 3→↑3→3 = 3→↑(3→↑2→3)→2 = 3→↑(3→↑3→2)→2 = 3→↑p→2 = 3→↑(..1..) :p: Met dubbele recursie over ketenlengte begint de tweede rij van Conway-Knuth, waarmee een nieuwe generatie van grote getallen uitdrukking vindt. a→↑y1→z1 = a→↑(a→↑y→z1)→z == a→↑(..a..)→z :y: Nog "sneller" wordt deze array functie met meerdere superpijlen, maar complete evaluatie ervan zou onvoorstelbaar lang duren. Het aantal heelal tijdperken dat ervoor nodig is om zulke expressies alleen nog maar tot een pijlketen van Conway uit te werken, is ongeveer gelijk aan het uitgedrukte getal zelf. 3→↑↑↑2 = 3→↑↑3 = 3→↑3→↑3 = 3→↑3→3→3 "tweede rij" = 3→↑3→(3→↑3→2→3)→2 = 3→↑3→(3→↑3→(3→↑3)→2)→2 = 3→↑3→(3→↑3→(3↑↑↑3)→2)→2 = 3→↑3→.(3→↑3→..1..).→2 :3↑↑↑3: Als een waarde in een cel met carets is aangegeven, zoals 3^^6143 dat zou zijn, dan hoeven we daar geen haakjes omheen te zetten, want de caret ^ maakt geen deel uit van ons superpijl systeem. Maar we moeten oppassen met oppijl operaties, zoals 3↑↑↑3 hier, die zonder haakjes rechts associatief uitwerken. Dan zou de rechtse operand opeens als parameter y in de pijlketen fungeren. De superatoren →↑{c1} in onze superpijlketens bestaan uit de rechtse pijl van Conway, gevolgd door oppijlen van Knuth. Deze dienen als hogere separator, waarbij het aantal oppijlen de dimensie van de voorliggende array ruimte telt. a→↑{c1}b2 = a→↑{c}a→↑{c1}b1 == a→↑{c}..a :b1 = a→↑{c}..a→↑{c-}..1 :b :a == V_i..a→..a c:1 :a- with V_c = a→↑{c}.. :b else V_i = a→↑{i}.. :a-- De reeks superatoren →↑{c} in de dimensie ervoor wordt helemaal uitgewerkt. Hiervan blijft de maat van de subdimensies links voorlopig onbepaald, totdat de subdimensie rechts is uitgewerkt tot getal. Vergeleken met de ineens en volledig uitgewerkte multidimensionale arrays van Bird, passen we hier in de dimensie ruimtes "luie evaluatie" toe. Dat kan, omdat we superpijlketens van rechts reduceren en nooit opnieuw van links opladen. $ 4.3.3. Superpijl systeem Multidimensionale pijlketens zijn onderscheiden (of worden onderling verbonden) met een tweede lichting →↑{c} oppijlen. Samen met het rechts substituerende algoritme vormt de dimensionale structuur een quadrupel recursie, na de tripel recursie van Conway's pijlketen. Elke oppijl erbij schept ruimte voor een extra dimensie en voegt daarin een reeks van de vorige dimensie ruimtes toe. Zoals Knuth's oppijlen de dubbele recursie vormen over de enkele recursie die torens van operaties maakt. Later zullen we de uitkomsten van deze rechts gestapelde en geordende recursie ruimtes vergelijken met de door Bird van links te herladen arrays. De getallen van Bird's lineaire arrays zullen dan net zo groot blijken te zijn als die van de →↑{c} pijlketen arrays, wat we noemen quadrupel recursief. Definitie van Conway-Knuth superpijlketens. -CK.1. X#1 = X -CK.2. y#_0↑z1 =` y#_0y#_0↑z -CK.3. a#_0→b = a#_0↑b -CK.4. X#1→z = X -CK.5. X#y1→z1 = X#(X#y→z1)→z == X#(..X..)→z :y: Hier staat het "hek" teken # voor een hele superator, operator of separator, en bevat elke mogelijke, niet-lege combinatie van pijlen. De andere teken variabele #_0 die "hek nul" heet, is mogelijk leeg of geeft het passieve linker deel van de operator of superator. Regel '1.' elimineert de hangende waarde 1 en de operator of separator: zowel de pijl van Knuth en Conway, als onze afgetelde superatoren. Regel '3.' heeft betrekking op een enkele overblijvende operatie met de rechtse pijl → van Conway of een rechtse pijl rechts van →.. een aantal vervolgpijlen. Dus niet als onderdeel van een grotere keten. Tekst variabele X staat voor een deelketen, maar eindigt rechts zeker met een variabel getal, omdat de hek superator # gretig is naar pijlen. Elke variabele is compleet, want die vorm is gretig naar getaltekens (enen). Regels met = selecteren de hele expressie, en hier de enkele operatie. Regels met =` zijn rechts associatief en matchen hier steeds vanaf het uiteinde van de expressie. Regel '2.' herhaalt normaal de vorige operatie, maar werkt anders als het hek deel leeg is, door de linker operand te verdubbelen. We kunnen dat in een regel '2a.' en regel '2b.' uitwerken, tot hun reeks met verschillend rep aantal. - y↑z1 =` yy↑z = y.. :2^z - y#↑z1 =` y#y#↑z = y#..y :z Na de laatste oppijl stap lieten we de afgetelde schakel ↑1 of #↑1 afvallen door regel '1.' toe te passen. Als resultaat uit de oppijl recursie krijgen we dus een getal y*2^z of een verder van rechts te evalueren sequentie. $ 4.3.4. Vervolgpijlen Een teller is een variabel getal, dat rechts volgt op een compleet construct, zoals de constante a of een pijlketen rij of de telbare dimensies in het Conway-Knuth pijlsysteem. De teller en de regel ervoor herhalen en breiden het construct niet direct uit, maar doen het in stappen toenemen in grootte. Hoe een teller de oppijlen in de superator a→↑{c}b stapsgewijs kan bijtellen is op voorhand niet duidelijk. We nemen aan dat de vervolgketen a→→b→→c de superoperatie a→↑{c}b aangeeft, waarmee we de luie dimensies van de superpijlketen uitrollen. Want dit weerspiegelt de equivalentie van a→b→c en de supermachten a↑{c}b waarmee Conway ooit begon. Voor rechtse "vervolgpijlen" →→z en in het algemeen voor alle superatoren met vervolgpijl #→z aan de rechter kant, presenteren we deze regels, om met elke tel van z een oppijl ↑ aan de superator links ervan toe te voegen. -CK.6. ↑y#→z1 =` ↑↑y#→z -CK.7. →y#→z =` ↑y#→z == ↑{z}y De hek variabele # van de superator vorm is niet leeg. Teller z voegt stap na stap een reeks ↑{z} oppijlen links ervan toe, en wel zodanig dat de expressie reduceerbaar blijft. Na regel '7.' herhalen we regel '6.' totdat we bij restwaarde z=1 de laatste schakel met regel '1.' af laten vallen. Dit aantal oppijlen kan weer recursief worden vergroot, met de bestaande regels, door een pijlketen deel rechts van de teller te noteren en die 'r-l' te evalueren tot nieuwe teller waarde. Enkele recursie volgt met y→2 en dubbele recursie met y→z en door zo een rij schakels toe te voegen doen we er een tripel recursie bovenop. Drie evaluatie voorbeelden. In aanvang wordt 3↑3 met de verdubbelende koppijl tot 12 gereduceerd. De eerste expressie geeft een elf-dimensionale pijlketen, een enorm getal. Wend dit getal aan voor het aantal dimensies van de pijlketen in het tweede voorbeeld. Herhaal ten derde deze aanwending van getal naar pijlketen dimensie 11 keer. 3→→2→→2→2 5;4= 3→→2→→(3→→2)→1 1;3= 3→→2→→(3→↑2) 2,1= 3→→2→→(3→3) 3,2,1= 3→→2→→12 7= 3→↑2→→12 6== 3→↑{12}2→→1 1= 3→↑{12}2 2,1= 3→↑{11}3 3→→2→→3→2 = 3→→2→→(3→↑{12}2) = 3→↑{3→↑{11}3}2 3→→2→→2→3 = 3→→2→→(3↑3)→2 == 3→↑{..12..}2 :11: Een dergelijke iteratie van de oppijl teller zagen we eerder bij supermachten in het getal van Graham, waar de pijlketen 3→2→65→2 een bovengrens voor is. Latere vervolgpijlen gaan ook zo, voor iedere twee schakels met →→ komt een schakel met →↑{k} superpijlen in de plaats. Dat is een beetje verspillend, maar deze keten structuren groeien in de evaluatie zo enorm lang, dat wegvallen van de helft van het aantal schakels insignificant is. Ons principe voor bouwen van grote getallen is: zodra een construct telbaar is gemaakt, kan het recursief worden herhaald. Een ander principe is zuinigheid. Maar in de regels voor vervolgpijlen werkt de algemene vorm y#→z hetzelfde uit als de eerste y→→z vervolgpijl. Dit lijkt de expansie mogelijkheden te verspillen die de laatste superator in zich heeft. Want als deze hoger is zou deze ook een hoger construct kunnen achterlaten. Bij oppijlen lukte dit wel en die blijven effectief. Maar het bleek niet mogelijk om deze rechtse pijlen →{m>2} aan het einde van de superketen een eigen rol te geven, en tegelijk ervoor te hoeden dat de evaluatie regels stapsgewijs zijn. Van belang is de voorlaatste schakel. Bij Conway bestaat de pijlketen uit een reeks dubbele recursies, met het nesten van subexpressies in de voorlaatste schakel →y→z van elk dubbel. Bij een reeks vervolgpijlen neemt in de laatste schakel de teller ook eenvoudig af, maar krijgt de voorlaatste schakel →→y→→z de dimensionale oppijlen erbij. Hogere schakelparen →{m1}y→{m1}z stapelen de hyperdimensies, die worden afgebakend met oppijlen →{m}↑{z}y in voorliggende vervolgpijlketens. Hoe groot dit vervolgpijl systeem is zal nog moeten blijken uit een vergelijking met de arrays van Bird of Birdy. Met afwisselende reeksen pijltekens →{m_i}↑{k_i}.. zou de superator zelf een dimensionale matrix structuur krijgen. Maar onze huidige vervolgpijl regels maken zulke superatoren plat, door ze tot een optelsom →{.m_i..} te reduceren, zodat de beoogde resolutie verloren gaat. Telbare vervolgpijlen →{m} zijn sowieso het dominante construct. Om hun aantal m met een hogere teller recursief aan te sturen, hebben we een nieuw type pijl ↓ nodig. Of hoger, als opener gepaard aan een sluitteken ← en daartussen variabelen als "pijl type" indexen binnen een geneste ↓M← matrix structuur. $ 5. Lineaire array Lineaire arrays zijn functie expressies bestaande uit een rij parameters: eerst de constante a en de som b met een wisselend subtotaal, gevolgd door een reeks iteratoren c_i die stapsgewijs aftellen in de evaluatie. Door links subexpressies te substitueren en die te verschuiven naar rechts om de afgetelde iteraties weer mee op te laden, wordt deze eerste array rij van Bird maximaal. $ 5.1. Birdy rij De Engelse wiskundige Christopher Bird publiceerde in 2006 een vijftal opeenvolgende array systemen, waarmee hij officieus een wereldrecord vestigde in het maken van grote getallen. Bird's eerste systeem is zijn lineaire array notatie, die in dit hoofdstuk de functie omschrijving Bird() meekrijgt. Dus zonder zijn krulhaken, die we al gebruiken voor de repetitie van tekens. Omdat de evaluatie regels voor grotere array ruimtes bij Bird steeds moeilijker worden, vereenvoudigen we zijn algoritme tot een systeem "Birdy". Dit wordt onze functie B() en zal makkelijk te vergelijken zijn met het origineel, zodat het duidelijk is dat Birdy ongeveer even grote getallen oplevert als Bird. Uit de eerste rij zijn bij Birdy de overbodige substituties verwijderd, die aan de grootte van de uitkomst vrijwel niets bijdragen. Deze simpeler regels komen pas vanaf de vierde parameter in het spel. $ 5.1.1. Optel duo We bouwen een systeem Birdy met de regels 'B.I' over een eerste rij parameters. Met licht aangepaste expressies noteert dit even grote getallen als Bird's lineaire array. Sommige regels blijven ook in hogere Birdy systemen geldig. Basaal zijn twee eliminatie regels van Birdy: om de uitkomst op te leveren en om een afgetelde iteratie ,1 aan het einde van de expressie rechts te verwijderen. -B.I.0. B(a) = a1 "successie" -B.I.1. B(X,1) = B(X) "afval" Dit reduceert a,1 via de successor functie B(a) tot uitkomst a1 wat in feite 1 optelt. Birdy begint hier hetzelfde als David Hilbert met zijn primitief recursieve functie. Zo maken we slim optellen met duo a,b mogelijk, terwijl de afval regel voor het afgetelde array uiteinde geldig blijft. Alleen uitkomst selectie als bij Bird kan ook, dat is 1 minder en als functie inert. - Bird(a) = a Regel '1.' om afgetelde uiteindes ,1 te verwijderen, gaat voor elke expressie van Bird of Birdy gelden, in het laatste rij deel. De vorm term X bevat in de expressie a,1 alleen de a en bij uitbreiding een rij a.,p_i.. met :k≥0 variabelen. Voor separator index arrays ,[X]1 kan dit principe om afgetelde indexen aan het einde van de subarray X op te ruimen van kracht blijven. Maar we zien af van Bird's selectie apparaat om zulke hangende variabelen en lege structuren ook uit voorafgaande rijen en ruimtes te elimineren. Bird neemt als basis operatie B(a,b) het machtsverheffen, net als Conway deed met a↑b in zijn pijlketen. Dit vooronderstelt een vermenigvuldiging stap: een herhaling buiten de array functie, die vervolgens == wordt herhaald. - Bird(a,b1) = (a,b).. :a = a*(a,b) == a*..(a,1) :b = a*..a :b = a^b1 Jonathan Bowers, een amateur die aan de oorsprong staat van het idee voor Bird's arrays, begint zijn array functie met de operatie van a+b optellen. Optellen kan eenvoudig door de ene komma te elimineren en de uitkomst uit de functie te tillen. Dit maakt regel '0.' van de successor uitkomst alsnog overbodig. -B.I.2. B(a,b) = ab "optellen" Alternatief is om primitief het parameter duo in Birdy stapsgewijs op te tellen. -B.I.2a. B(a,b1) = B(a1,b) "tellen" Door met regel '2.' verder te tellen tot B(ab,1) en met regel '1.' de iteratie te elimineren B(ab) en de successor met regel '0.' geeft dit ab1 als uitkomst. Hier tellen we om op te tellen: de enen worden stuk voor stuk van cel b naar cel a overgeheveld. Een pure functie regel met de tussenstap B(B(a),b) in onze regel '2a.' telt het duo ook op. Dit is hoe Hilbert het zichzelf voorstelde. Met in cel b de iterator, die de successor functie recursief in cel a substitueert. Optellen van a,b kost het Birdy systeem twee supermachten ** ten opzichte van Bird's macht. Dat is voor arrays a,b,c met drie parameters wel significant, maar wordt hoe langer hoe minder relevant over de rij. $ 5.1.2. Supermacht trio De motor van Bird's lineaire array systeem is de stap van functie substitutie. Dit telt de derde parameter c van buiten af en substitueert in cel b een subexpressie die binnen in b is afgeteld. Herhaald aftellen van b tot 1 nest een hele recursie. Werk dit nest uit tot getal en de volgende functie stap kan worden gezet. De hele iteratie over c vormt een "dubbele recursie", die met aftellen van een volgende parameter links ervan opgeladen wordt. Met drie parameters in Bird(a,b,c) worden exact de supermacht operaties a^{c}b uitgedrukt. Maar in ons simpele Birdy systeem begint B(a,b,1) met optellen. Bij de c in het Birdy trio geven we dus 2 extra voor dezelfde uitkomst. Bij dubbele recursies over langere rijen verschilt dit minder. Nadat de laatste recursie stap zijn subexpresssie tot b=1 heeft afgeteld, reduceren we die subexpresssie op de bodem tot getal a met deze regel. -B.I.3. B(a,1,2X) = a "opheffen" Tekst variabele X staat voor de rij rechts c.,d_i.. met nul of meer parameters. Bij uitbreiding naar hogere arrays blijft deze regel geldig en kan X staan voor elke mogelijke passage. Op de bodem van de functie recursie kan nooit een afgetelde iteratie c=1 volgen in de rij. Oneigenlijke expressies a,1,1,R laten we onder de latere regel voor opladen vallen. De stap van functie recursie is essentieel in het algoritme van Bird. Het kopieert de hele expressie, telt de kopie af in waarde b en substitueert deze in cel b van het origineel. Gegeven dat a constant moet blijven en de expressie altijd reduceerbaar, is de subexpressie slechts minimaal kleiner en zijn positie in de rij maximaal groter. De regel voor de stap van functie recursie in Birdy werkt hetzelfde als in Bird. -B.I.4. B(a,b1,2X) "substitutie" = B(a,(a,b,2X),1X) De voorwaarde hier is dat b>0 omdat cellen in Birdy nooit leeg mogen staan. Expressies a,1,2X worden eerder opgelost door regel '3.' op de bodem van de subexpressie recursie. De tekst variabele X≥0 begint eventueel met de rest van parameter c≥0 en rechts daarvan c.,d_i.. :k≥0 kunnen meerdere cellen volgen. Maar X kan ook leeg zijn. Later omvat de X in deze regel ook alle mogelijke hogere arrayruimtes, dezelfde recursie over de hele expressie blijft van kracht. Zo evalueert de supermacht B(a,2,c1) tot een superkwadraat B(a,a,c) door subexpressie substitutie op de bodem. Hier is c>0 omdat regel '1.' het uiteinde ,1 laat afvallen. In het algemeen is een regel van toepassing, als zijn vorm wordt gevonden in de expressie en als niet een eerdere regel dezelfde vorm selecteert. In B(a,b,c) met aftelbare parameters b>1 en c>1 is dat regel '4.' voor dubbele recursie. Met drie parameters produceren we de supermachten, waarbij we een toren van supermachten uitdrukken door een reeks van b subexpressies te nesten tot constante a is opgeheven van de bodem. Alle derde parameters c in die reeks tellen zo 1 stap of ster * af van de dubbele recursie. B(a,b1,c1) 4= B(a,(a,b,c1),c) == B(a,..(a,1,c1)..,c) :b: 3= (a,..a..,c) :b: We kunnen het functie voorschrift weglaten, hier de letter 'B.' voor Birdy en ook de top expressie haakjes, wanneer het gebruikte systeem duidelijk is. Na optellen ab met B(a,b) en vermenigvuldigen a*b met B(a,b,2) en machtsverheffen a**b met B(a,b,3) drukt het Birdy trio B(a,b,c1) exact de supermachten a*{c}b uit van hoofdstuk $.2. Dubbele recursie is Bird's startmotor, die getallen razendsnel groot maakt. De grote getallen van de arrays of "akkers" in Birdy lopen parallel aan die van Bird. We zorgen dat input expressies met c2 in Birdy eerst nog gelijk en later insignificant groter zijn als die van dezelfde input met c in Bird, nooit kleiner. $ 5.1.3. Opladen op de rij Gegeven een aftelbare expressie (a,1Z) van een Bird type array functie, krijgt in de volgende evaluatie stap de subexpressie de afgetelde vorm (a,Z) die we hier verkort weergeven met een dollar $ teken. Dezelfde subexpressie zagen we in systeem Birdy in regel '4.' met de functie recursie stap. Bird substitueert de subexpressie $ eveneens in zijn regel voor het herladen van een reeks afgetelde cellen ,1 op de rij, in de meest rechtse cel ervan. - Bird(a,b1.,1..,2R) :k>0 = Bird(.a,..$,1R) :k1 Als k=0 het geval zou zijn, volgt er bij Bird de regel voor functie substitutie uit. In Birdy is de oplaadregel simpeler. We substitueren niet de subexpressie, maar verschuiven het subtotaal uit b naar de rechts wachtende cel ,1 en slaan de cellen ,1 ertussen over. Alleen bij de achtergelaten cel b=1 tellen we meteen een kopie van constante a op. Regel voor het opladen van afgetelde cellen ,1 op de eerste rij. Stel dat k het aantal lege cellen aangeeft, zodat parameter c=1 als eerste opgeladen wordt als k=1 onder een langere rij. -B.I.5. B(a,b1.,1..1X) :k1 "opladen" = B(a,a1.,1..b,1X) :k>0 Herhaalde toepassing == van deze oplaadregel in Birdy vult het afgetelde deel van de expressie van rechts naar links. Het resultaat daarvan lijkt sterk op Bird's complete oplaadregel, waar de voorliggende afgetelde cellen ,1 allen door ,a zijn vervangen. B(a,b1.,1..,1X) :k1 5= a,a1.,1..,1b,X :k == a,a1,1.a,..b,X :k 4= a,$.,a..,b,X :k Bij Birdy krijgt de tweede cel na de recursie stap een subexpressie $ ingeladen, maar bij Bird is dat de cel rechts in de afgetelde deelrij, wat groter is. Door vooraf bij c een extra 1 tellen, kunnen we een subexpressie voorladen, waarmee herhaling van opladen in Birdy bijna gelijk komt met opladen bij Bird. B(a,b1,2.,1..X) :k1 4= a,$,1.,1..X :k1 == a,a1,1.a,..$-,X :k De dominante variabele $- blijft toch 1 stap kleiner dan bij Bird. Maar het resultaat telt wel 1 extra in de tweede en derde cel van Birdy. Dit is de beste benadering van een lineaire array van Bird door Birdy. Zouden we bij de input waarde van b ook 1 extra tellen, dan wordt het resultaat in Birdy juist "minimaal groter". Duidelijk is, dat dit -> verschil met Bird in de evaluatie vanzelf gehandhaaft blijft. Als we de functie substitutie van regel '4.' uitbreiden naar hogere cellen rechts op de rij, dan kan dat niet voor significant grotere getallen zorgen. Het werd door Rózsa Péter in haar boek "Rekursive Funktionen" uit 1950 al bewezen, dat in een primitief recursieve rij variabelen met meerdere functie substituties tegelijk, de uitkomst toch primitief recursief blijft. Substitutie van $ in cellen rechts is dus algoritmisch kleiner dan de sprong naar Ackermann functies en de getallen van Graham. Enkel het verschuiven van subtotaal waarden uit b naar afgetelde iteraties rechts is dermate dominant, dat ook het stapelen van dubbele recursies van rechts over links op de rij, wat Conway's pijlketen groot maakt, hier niet veel toevoegt. Dat blijft beperkt tot Bird's vierde parameter d om precies te zijn. Als variant op regel '5.' kunnen we ook eerst de waarde uit b opladen en de resterende cel b=1 daarna pas met a1 vullen. Een manier van opladen in twee stappen, waar bij b>1 het subtotaal enkel verschuift. - B(a,b.,1..1X) :k1 "schuiven" = B(a,1.,1..b,1X) :k>0 - B(a,1.,1..1Y) :k "vullen" = B(a,a1.,1..Y) :k>1 Deze alternatieve evaluatie is door de primitievere regels algoritmisch wel fraai, maar rekenkundig is het vreemd dat we met b=1 en c=2 reduceren tot a en de tussenstop expressies met c=1 na uitwerking veel groter zijn. Bij opladen in hogere arrays werken we ons met die a kopie in b in de nesten, omdat het eerdere subtotaal uit b niet meer beschikbaar is om op te laden binnen afgetelde index arrays. Zo blijven de uitkomsten al te klein. Om dit te verhelpen kunnen we bij geneste arrays het subtotaal in b laten staan door er een kopie van op te laden. Of anders kunnen we de zojuist opgeladen teller rechts van die index array een nest niveau omlaag laten zakken. $ 5.2. Vergelijk rij systemen Chris Bird bewees hoe zijn array met vier parameters ongeveer even grote getallen uitdrukt als Conway's pijlketen over de gehele lengte. Vergelijk in dit hoofdstuk verschillende notatie systemen met de hele eerste rij. Om met aanpassing van input expressies even grote getallen uit te drukken. $ 5.2.1. Bird en Birdy rij Vergelijken we Bird's lineaire array met de eerste rij van ons Birdy systeem 'B.I.' Te bewijzen is dat, ondanks de afwijkende regels, de uitkomsten over de hele rij genomen niet significant van elkaar verschillen. Birdy begint dezelfde dubbele recursie wat eerder, met optellen van B(a,b,1) via B(a,b) tot ab en ligt meteen twee supermachten achter. Bird(a,b,1) = a**b = B(a,b,3) Bird(a,b,c) = a*{c1}b = B(a,b,c2) In het vervolg stellen we Bird's arrays "minimaal groter" -> of anders "minimaal kleiner" <- dan expressies in Birdy. Rechts in de vergelijking met -> heeft de Birdy expressie een minimaal kleinere en na <- een minimaal grotere uitkomst. Door aanpassing van de input in eerste cel a draait dit verschil al om. We tonen steeds die input waarden in Birdy, die het dichtst de uitkomst van Bird's array benaderen, hetzij kleiner, hetzij groter dan. Bird(a,b1,1,2) = Bird(a,a,(a,b,1,2)) == Bird(a,a,..a..) :b: <- B(a2,b1,2,2) = (a2,(a2,b,2,2),1,2) := (a2,a3,(a2,b,2,2)) == (a2,a3,..a2..) :b: Hier is bij Bird de substitutie na = volgens de regels, terwijl bij Birdy met := de subexpressie wordt opgeladen nog voor deze tot getal is uitgewerkt. Gegeven een b aantal substituties op dezelfde plaats, dan bepaalt de laatst geneste 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 daarin. In deze expressies waar d1>2 hoeven we het verschil van opladen tussen de systemen al minder te compenseren. Bird(a,b1,1,d1) = (a,a,(a,b,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 om Birdy gelijk te trekken. Bird(a,b1,c1,d) == (a,..a..,c,d) :b: -> B(a,b1,c2,d) == (a,..a..,c1,d) :b: Dat de hiermee uit te drukken getallen al even groot zijn als die van Conway's hele pijlketen, wordt bewezen in de sectie "Pijlketen versus Birdy" hierna. - - - - - - - - - - - - - - - - Om opladen naar vierde parameter d te vergelijken, krijgt Birdy behalve 1 extra bij c ook 1 extra bij de a input, omdat we op de bodem van de subexpressie recursie de opgeheven waarde a1 weer - aftellen. Bird(a,b1,1,1,e1) == (a,a,a,..a..,e) :b: <- B(a1,b1,2,1,e1) := (a1,a2,1,(a1,b,2,1,e1),e) = (a1,a2,a2,$-,e) == (a1,a2,a2,..a1..-,e) :b: Voor opladen naar de derde parameter blijft 1 extra bij cel a in Birdy 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: Dezelfde aanpassingen zijn in vergelijkingen vanaf de vijfde parameter geldig, ongeacht de rest R van de rij. B(a,b,c,R) <~ Bird(a,b,c,R) <- B(a1,b,c1,R) Bij een langere rij is een expressie in Birdy algoritmisch "iets kleiner" <~ dan dezelfde in Bird, omdat parameters a en c insignificant zijn onder de hogere. - - - - - - - - - - - - - - - - De subexpressie opladende lineaire arrays van Bird en ons subtotaal opladende rij systeem Birdy zijn hiermee vergeleken. Ook voor hogere systeem structuren met een eerste rij kan dit zo blijven gelden. Zowel Bird als Birdy drukken, gegeven een rij parameters waar functie substitutie is toegestaan, maximaal grote getallen uit. Daarbij is, behalve de snelle start door functie substitutie in b links, vooral het opladen van subtotalen uit b naar de hoogst afgetelde iteraties belangrijk. Of die opgeladen b steeds verpakt wordt in een subexpressie $ zoals bij Bird, is voor de uitkomst insignificant. Tel 1 extra bij input parameter c in Birdy, dan geeft dit een substitutie $ stap extra, die het verschil vrijwel compenseert. Ruim genomen geldt over de hele rij de vergelijking, dat Birdy B(a,b,1R) altijd iets kleiner <~ is dan Bird(a,b,R) qua input. Terwijl Birdy B(a,b,2R) iets groter of gelijk ≈> is aan die input van Bird. Hoewel de getal output natuurlijk gigantisch kan verschillen. Om precies te zijn, beide systemen lopen door c+2 in Birdy nog gelijk bij de supermachten, maar daarna maakt dit Birdy een geneste recursie in b groter. Het input verschil blijft op het oog beperkt en wordt insignificant als hogere recursies over de rij domineren. We kunnen andere systemen voor grote getallen nu met Birdy expressies vergelijken, wat handig is, omdat de vergelijking met Bird daarmee gegeven is. $ 5.2.2. Pijlketen versus 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 functie recursie stap telt een kopie van de expressie af en substitueert deze subexpressie $ op de plek van de afgetelde variabele. Bij Conway gebeurt dat in voorlaatste variabelen y rechts, bij Bird in de tweede variabele b links. Na een hele recursie is er een reeks met een y of b aantal subexpressies genest. Dat ziet er zo uit. Letters L en R staan voor de rest, hetzij links de lagere parameters in Conway's keten, hetzij rechts de hogere iteraties op de rij van Birdy, de versimpelde array van Bird. 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. Bij Birdy komt elke subexpressie recursie uit op de constante a die klein is. De dubbel recursieve parameter telt af en het subtotaal in y of b groeit. Conway kapt de schakel z=1 van het einde →y→1 van de keten af. Terwijl in de Birdy B(a,b,1,R) het subtotaal uit b naar rechts wordt opgeladen. Naar de dubbel recursieve iteratie van c=1 maar uiteindelijk ook naar de voorlaatste cel, als die rechts in de reeks ,1.. wacht. Dit schept het grote verschil tussen de met deze systemen uitgedrukte getallen. - - - - - - - - - - - - - - - - Birdy telt B(a,b,1) = (a,b) = ab direct op. Terwijl Bird en Conway's pijlketen sneller beginnen met a^b machtsverheffen. Om Conway-Knuth superpijlen primitief te funderen gaven we de koppijl a↑b een herdefinitie als optellen. In deze systemen werkt elke stap van de dubbele recursie over c hetzelfde, namelijk als reeks subexpressie substituties in b . Met drie parameters loopt systeem 'B.' van Birdy steeds 2 van die recursies achter. a→b→1 = a→b = a↑b = B(a,b,3) B(a,b,c) = a→b→c2 Vergelijk de vierde parameter in Conway's pijlketen met Birdy. Eerst met recursie over de supermacht teller. a→a→b1→2 = a→a→(a→a→b→2) == a→a→(..a↑a..) :b: -> B(a,b1,2,2) = (a,(a,b,2,2),1,2) := (a,a1,(a,b,2,2)) == (a,a1,..a..) :b: Hou Conway's pijlketen -> minimaal groter, zodanig dat de Birdy expressie meer groter zou worden door 1 stap bij recursie parameter b op te tellen. Hoewel algoritmisch "minimaal" zijn de verschillen hierbij natuurlijk enorm. B(a,2,3,2) = (a,a,2,2) <- a→a→2→3 = a→a→a↑a→2 <- B(a^a,2,3,2) <- B(a,3,3,2) De tweede recursie over de supermacht teller, met het verschil op de bodem. a→a→b1→3 = a→a→(a→a→b→3)→2 == a→a→(..a↑a..)→2 :b: -> B(a,b1,3,2) = (a,(a,b,3,2),2,2) == (a,..a..,2,2) :b: Zo gaat de hele dubbele recursie over de supermacht teller. a→a→b1→c1 == a→a→(..a↑a..)→c :b: -> B(a,b1,c1,2) == (a,..a..,c,2) :b: De vierde schakel in Conway's keten komt dus overeen met de derde parameter onder d=2 in Birdy. - - - - - - - - - - - - - - - - Conway's vijfde schakel begint weer met recursie over de vorige. a→a→a→b1→2 == a→a→a→(..a↑{a}a..) :b: -> B(a,b1,2,3) := (a,a1,(a,b,2,3),2) == (a,a1,..a..,2) :b: Net zo werkt de volgende dubbele recursie uit. a→a→a→b1→c1 == a→a→a→(..a↑{a}a..)→c :b: -> B(a,b1,c1,3) == (a,..a..,c,3) :b: De vijfde pijlketen parameter past precies onder d=3 in Birdy. We zetten dit voort over de hele keten. Vanaf de eerste recursie over de vorige dubbel recursieve variabele, die wordt opgeladen in Birdy, wat een stap van d aftelt. Conway's keten L op de bodem tegen a in Birdy maakt het verschil. L→b1→2 & L = a→..a :d == L→(..L..) :b: -> B(a,b1,2,d1) == (a,a1,..a..,d) :b: Schakels a→ kunnen ook verschillende waarden hebben, als deze "normaal" zijn (niet al te groot of triviaal klein) blijft de pijlketen minimaal groter. Steeds drukt de nieuwe variabele rechts in Conway's keten een hogere dubbele recursie uit. Terwijl Birdy onder de derde parameter c de subexpressies nest en de vierde parameter d de lengte van de pijlketen aangeeft. L→b1→c1 & L = a→..a :d == L→(..L..)→c :b: -> B(a,b1,c1,d1) == (a,..a..,c,d1) :b: Getallen die Birdy 's rij met vier parameters uitdrukt, zijn ongeveer zo groot als die met Conway's hele pijlketen. Beiden substitueren afgetelde subexpressies, de algoritmes verschillen omdat Birdy subtotalen uit b oplaadt naar c=1 onder aftellen van d . Waarna c de volgende en grotere dubbele recursie oplevert. Op twee manieren vindt er hier een herhaling van dubbele recursies plaats: over de van rechts af te wikkelen rij in Conway's pijlketen, en met de steeds opnieuw met subtotaal b op te laden dubbel recursieve variabele c in Birdy. Dit volgende type recursie noemen we "tripel recursie". $ 5.3. Superpijlen versus Birdy Vergelijk de Conway-Knuth superpijlketens, die we definieerden in hoofdstuk $.4.3, met onze simpele Birdy versie van de array notatie van Bird. $ 5.3.1. Tweede pijlketen bij e=2 Breng de tweede pijlketen bovenop de lengte van Conway's keten aan. In Birdy onder vijfde parameter e=2 valt ook die tweede rij samen met variabele d . Begin met het opladen van de lengte variabele voor Conway's pijlketen met het subtotaal uit b in Birdy. Dat kan enorm worden! a1→↑b2 -> a→..a1→a1 :b -> B(a,b1,1,1,2) = (a,a1,a1,b) -> a→..a1 :b1 -> a→↑b2 = a→..a :b1 Eerste recursie over pijlketen lengte, of in Birdy's variabele b en voortijdig := opgeladen naar de vierde parameter met een - aftel. B(a,b1,2,1,2) := (a,a1,a1,..a..-) :b: -> a→↑b1→2 = a→↑(..a..) :b: Verdere stappen van c in de dubbele recursie over pijlketen lengte. B(a,b1,c1,1,2) = (a,..a..,c,1,2) :b: -> a→↑b1→c1 = a→↑(..a..)→c :b: Volgt het opladen van de dubbele recursie in Birdy c voor de tweede pijlketen. B(a,b,1,2,2) = (a,a1,b,1,2) -> a→↑a1→b In de verdere recursies krijgt elke superpijlketen een grotere subexpressie op de bodem dan de a bij Birdy. Nu is dit Conway's super-Ackermann keten met een a aantal parameters a , die de vergelijking bepaalt die hier met <- van richting wisselt. B(a,b1,2,2,2) := (a,a1,..a..,1,2) :b: <- a→↑a→b1→2 = a→↑a→(..a→↑a..) :b: De tweede dubbele recursie in de tweede pijlketen, die door Birdy gewoon vanaf links in c wordt geteld. B(a,b,c,2,2) <- a→↑a→b→c De tweede pijlketen is in zijn geheel tripel recursief over de tripel recursieve pijlketen van Conway. Birdy gebruikt hier weer de vierde variabele d voor. B(a,b,c,d1,2) <- a→↑.a→..b→c :d Hierbij is d>0 omdat anders Birdy -> minimaal groter uitkomt; zie hierboven. En ook c>1 want in geval c=1 is de vergelijking anders na opladen. B(a,b,1,d1,2) = (a,a1,b,d,2) -> a→↑.a→..b :d Dat een enkele stap in e een tripel recursie hoger springt, toont de kracht van Bird's lineaire array voor het maken van grote getallen. $ 5.3.2. Pijlketens onder e Voeg hierna de volgende pijlketen rijen toe, wat op details in de vergelijking na hetzelfde werkt. Rij op rij vormt zich zo een pijlketen vlak. Begin weer met opladen naar d in Birdy, nu voor de tweede pijlketen lengte. B(a,b1,1,1,3) = (a,a1,a1,b,2) -> a→↑.a→..a1 :b -> a→↑a→↑b1 In de eerstvolgende recursie blijft de bodem a van Birdy meteen achter bij de bodem subexpressie voor de pijlketen lengte. Dat we het verschil tussen beide expressies aangeven als minimaal kleiner <- komt, omdat Birdy met 1 extra recursie stap in b consequent meer verschil biedt. B(a,b1,2,1,3) = (a,..a..,1,1,3) :b: <- a→↑a→↑b1→2 = a→↑a→↑(..a→↑a..) :b: <- (a,b2,2,1,3) = B(a,..a→↑a→↑a..,1,1,3) :b: De rest van de vergelijkingen onder Birdy's e verlopen op dezelfde wijze. De subexpressie op de bodem van gelijke recursies blijft kleiner in Birdy. Voor de verdere op voorgaande rijlengte gestapelde pijlketens geldt algemeen. B(a,b,c,d1,e1) <- a→↑..a→..b→c :e :d Met een uitzondering bij opladen naar c of d in de richting van de vergelijking. B(a,b,1,d1,e1) = (a,a1,b,d,e1) -> a→↑..a→..b :e :d B(a,b1,1,1,e2) = (a,a1,a1,b,e1) -> a→↑..a→..a1 :e :b -> a→↑..b1 :e1 De vaststelling of expressies minimaal kleiner of groter zijn, is niet significant op deze schaal. Zelfs de waarde van de subexpressie recursie teller b in de input expressie doet er niet veel meer toe. Waar Bird's vijfde variabele e een aantal tripel recursies stapelt over de lengte van de pijlketen rij, vormt dat een groot recursief vlak van pijlen. Een vierde type recursie in een tweede pijlketen array dimensie! $ 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 1:k & T_i = a→↑{i-}.. :d_i Hier is k>1 want bij k=0 geldt a→b→c voor de a↑{c}b supermachten en bij Conway's pijlketen k=1 geeft de vierde Birdy parameter d_1 een pijl meer aan, die onder een hogere parameter 1d_i>1 ontbreekt. B(a,b,c,d) <- a→..b→c :d Bird's lineaire array gaat hetzelfde, maar tel in c- een recursie minder, omdat ons Birdy systeem niet de subexpressie maar alleen het subtotaal b oplaadt. In de multidimensionale arrayruimte die Knuth superpijlen →↑{c} bovenop de pijlketen rij van Conway afzetten, worden gewone recursies naar binnen toe genest en hogere recursies consequent van rechts naar links afgewikkeld. Vereenvoudigde vergelijking van Conway-Knuth superpijlen met de Birdy rij, met uiterste iterator b en rij lengte c3 als dominante waarden. Eerst een voorbeeld. a→↑↑b1 = a→↑..a :b <- B(a,a,a,a,b) a→↑{c>1}b1 <- B(.a,..b) :c2 <- a→↑{c>0}b2 Zo zijn de maximale getallen die in een lineaire array functie met een links oplaadbare rij parameters te maken zijn, vergelijkbaar met die van de eerste serie Conway-Knuth superpijlen. Ook bij andere waarden voor parameters a hier, mits niet op schaal te groot of triviaal klein, blijft de vergelijking geldig. Iedere Conway-Knuth superpijl bouwt met het voorgaande type recursie een hogere reeks recursies. Recursie typen zijn hier telbaar geworden. De enumeratie van recursies komt veel langzamer tot stand dan de natuurlijke getallen. Het valt te verwachten dat deze type getallen door hogere array structuren als het ware worden vermenigvuldigd, etc. en dat we ze uiteindelijk kunnen noteren met dezelfde soort arrays. Elke nieuwe recursie is gebouwd op een reeks vorige recursies. Maar het hele concept van reeks of rij valt als insignificant weg te strepen tegen de diepte van geneste arrays. Misschien dat in de diepte de recursie typen samenvallen met de getallen uit de functie arrays die ermee worden geclassificeerd. Zou dit niet zo zijn en blijven de typen arrays significant achter bij de natuurlijke functie arrays, dan zou door het rigoreus definieren van overgangen of cycli daartussen, de cycli gebruikt kunnen worden om record grote getallen functies mee aan te geven. $ 6. Multidimensionale arrays Een multidimensionale array is een structuur, onderverdeeld in repeterende reeksen van variabelen. De structuursom die alle variabelen optelt is triviaal en traag. We evalueren multidimensionale expressies met verschillende algoritmes voor het maken van grote getallen. Onze Adam en Eva systemen beginnen primitief met supermachten over de rij, maar lopen in meerdere dimensies parallel aan de Conway-Knuth ketens met superpijlen. Multidimensionale Birdy arrays, die we afleiden uit die van Bird, zijn maximaal snel, doordat we functie recursies opladen naar hogere iteratoren. $ 6.1. Structuursom Tussen variabelen in de functie rij staan komma's. Deze systeem structuur kan worden uitgebreid met nieuwe separatoren: een dimensie index, geneste index rijen, recursie over nest diepte, etcetera. We kunnen de capaciteit van de ontstane ruimtes in de array kwantificeren met een structuursom. Bij de structuursom vormt elke volgende dimensie een vermenigvuldiging en de hele multidimensionale array een macht. Dit leggen we uit. Reeksen enen 1.. maken de natuurlijke getallen, die de variabelen vormen in de expressie. De functie van variabelen in de array functie wordt bepaald door hun positie in de structuur en door het toegepaste algoritme. Een rij met variabelen noemen we de eerste dimensie in een array, terwijl deze eigenlijk bestaat uit rijen van rijen van enen. Als we deze getallen alleen maar optellen, dan drukt de rij lengte een vermenigvuldiging uit. Ook kunnen we gelijke variabelen in een dimensionele structuur plaatsen, die geen andere functie heeft dan optellen. Vul een kubus van 3 bij 3 bij 3 met getallen 3 en tel deze op. 111 = 3 = 3*1 = 3^1 "getal + 111 + 111 = 3*3 = 3^2 "rij + 111 111 111 = 3*3*2 + 111 111 111 = 3*3*3 = 3^3 "vlak + 3^3 + 3^3 = 3^4 = 81. "kubus Hier voegen we rij op rij toe in de tweede dimensie. De array structuur met een reeks rijen noemen we een vlak, hoewel naast getalwaarden ook de rij lengtes in de evaluatie ervan sterk variabel zijn. We stapelen een aantal vlakken in de kubieke ruimte, de derde dimensie. Elke herhaling van de voorgaande dimensie structuur vormt de volgende dimensie. Maar in de array notatie staat elke ruimte structuur op een lijn, waarin deze van elkaar gescheiden zijn met specifieke separatoren. Het simpelst is om een aantal komma's ,{m} na elkaar te gebruiken om de dimensie m onder te verdelen. a,..,,..,,,.. :k_[i,j] :k_i :k_3 Stellen we gelijke zijden k dan sommeert dit tot a*k^3 in een kubieke array. Of tel met gelijke maten k een m aantal dimensies op tot a*k^m een macht. a.T_i.. :m T_i = ,{i}.. :k Voor de structuursom stellen we alle aantallen gelijk aan a , zowel de variabele waarden als de rij lengtes, de dimensie maten en het aantal dimensies. Vervolgens laten we alle separatoren ertussen wegvallen. Elke komma telt dus voor 0 en heeft geen functie, behalve optellen. Ook als we de komma teller ,{m} uitbreiden tot index arrays, met geneste index getallen, vervallen deze in hun geheel tot 0 en houden we de structuursom over. Zouden we die index waarden meetellen in de som, dan blijft dat insignificant. Met index [1] erbij en lengte k komt de som op de rij ongeveer op a1*k . En met index [2] en k rijen in het vlak op a1*k^2+2*k wat al minder bijdraagt. Zo blijft de som inclusief indexen in a dimensies kleiner dan a1^a1 . De som van de variabelen in de gescheiden ruimte zal altijd significant groter zijn, dan de som van de indexen van hun scheiding, ook bij diep geneste arrays. Voor de structuursom tellen we variabelen a op in alle ruimtes, allen met vaste maten a en gegeven a dimensies. Dan is de structuursom a^a1 voor de multidimensionale array, wat we tot een tetratie a^^2 kunnen afronden. Array functies laden afgetelde iteratoren opnieuw op en via de lengte tellers ook de dimensie maten. Als we meerdere komma's gebruiken voor het scheiden van dimensies, moeten we iteraties niet aftellen tot 0 maar tot 1 om de structuur intact te houden. Of gebruik anders een komma index ,[m] in de stijl van Bird [m] voor de dimensie m van de ermee onderscheiden ruimte. De structuursom kwantificeert de wiskundige informatie die de arrayruimte kan bevatten, ongeacht de tekens van de separatoren of operatoren die we op de variabelen erin toepassen. Het is voorlopig nog de vraag of de structuursom primitief recursief blijft, of in een hogere array constructie de Ackermann supermachten a*{a}a te boven gaat. $ 6.2. Adam's dimensies Adam is een primitief recursief array systeem, waar iteraties worden afgeteld tot 0 en met een verzamelsom b weer opgeladen. Met de eerste rij drukte Adam een reeks popster supermachten uit. Vanaf de vierde parameter k>1 of afgerond over de hele rij geldt deze vergelijking. a,..f :k1 ~> a*{k}f2 Na de overgang ,[1] waarmee Adam de volgende rij opent, komt een "lengte teller" te staan, die de eerdere rij verlengt met extra cellen. Elke stap die de teller aftelt, voegt een komma met een maximale variabele ,b toe aan de rij ervoor. Daarna vult de rest van de lege rij zich opnieuw en levert na evaluatie een grotere som b' op, elke teller stap opnieuw. Afgetelde iteratoren op de lege rij, of in welke dimensie dan ook, worden in Adam niet opgeruimd, zolang er nog variabelen rechts op volgen. Elke recursie over de lengte teller expandeert de vorige rij, steeds met een significant groter aantal parameters. De nieuw opgeladen dimensie teller ,[m]b is dermate dominant, dat het opruimen van uitgetelde array dimensies ervoor geen effect sorteert. Bird staat het opladen van afgetelde cellen ,1 alleen toe als er nog aftelbare variabelen rechts in dezelfde rij volgen. Hij elimineert alle lagere lege structuren, onder een hogere dimensie separator. De consequentie van dit esthetisch principe is, dat cellen niet stap voor stap kunnen worden toegevoegd. Bird moet de hele lege dimensie structuur tegelijk opladen, wanneer de basis a,b daaronder in de evaluatie is bereikt. Via een tussennotatie met pijlhaken bewaakt hij de maximaliteit van zijn array functies. Bird kan daarmee zonder onze dimensie tellers, daar de rijen a,..1 binnen zijn dimensies a[m]..1 tegelijk door :b worden uitgespreid. Het grote bezwaar tegen Bird's notatie is nu nog niet duidelijk, maar welke van twee index subarrays precies lager komt, wordt in zijn hogere systemen steeds moeilijker te bepalen. Ook Bird's pijlhaak substituties, om meerdere uitgetelde ruimtes in een aparte routine te vullen, zijn een drama. In de hier ontwikkelde systemen is dit niet nodig, het nieuwe groeit vanzelf aan op het oude. - - - - - - - - - - - - - - - - We substitueren de tweede cel na opladen van b nu direct door de a kopie, wat in de eerdere rij definitie van Adam werd uitgesteld. a,b1,{k>0},1R = a,a,{k}b,R Voorwaarde is k>0 omdat eerste iteratie 1c de kopie en som als ab1 optelt. Na het verlengen van Adam's eerste dimensie met ,[1] die cellen met ,[] en dan komma's , toevoegt aan de rij, generaliseren we dit uitbreiden naar meerdere dimensies, door ,[m] dimensionale separatoren in te voegen. a,b1,{k≥0},[m1]1R = a,a,{k},[m]b,[m1]R Bij k=0 staan ervoor op de rij geen afgetelde ,0 iteraties. En als m=0 dan valt de nieuwe index array [] weg en blijft er een komma , over. Zo telt Adam zijn geneste arrays leeg, weer te geven met ,[0] of zonder ,[] nul teken, en elimineert daarna de array haken. Tel steeds 1 af alvorens som b op te laden naar de ingevoegde dimensie teller. Ongeacht welke dimensies l_i≥0 links ervan zijn afgeteld. a,b1.,[l_i]..,[m1]1R :k = a,a.,[l_i]..,[m]b,[m1]R :k Dit werkt net zoals Adam met een dubbele recursie over de eerste rij, waar enkel l_i=0 komma's staan, de popster machten uitdrukte. Maar de eerste iteratie, die optelt en waar m=- en k=0 zijn, blijft een speciaal geval. Daaruit volgt de separator eliminatie voor index arrays. ,[0] ≡ , ,[-] ≡ 0 Equivalentie ≡ maakt introductie van een lege index array [0] bij een komma mogelijk, waarna we de regel voor dimensionaal opladen kunnen toepassen. Bij een iteratie stap van ,1p in een rij, telt de regel die af tot ,[]p en laadt in de schaduw dimensie ,[-]b de som op, te reduceren tot nieuwe variabele b in de gegeven voorstaande cel. - - - - - - - - - - - - - - - - Rij dimensies blijven onderverdeeld met een komma , die vooraf gaat aan elke variabele. In de definitie komt een eigen regel '3.' om die cellen weer op te laden, naast regel '5.' voor het opladen onder de dimensie separator ,[m>0] vorm. Definitie van Adam systeem 'A.' voor de multidimensionale structuur 'II.' met een enkele index voor de separator. -A.II.1. a,b `=? b -A.II.2. a,b,1 `= a,ab, -A.II.3. a,1b, ,1 `= a,a, b, -A.II.4. ,[] ≡ , -A.II.5. a,1b ,[1m]1 `= a,a ,[m]b,[1m] Het evaluatieteken = in de regels is opgetuigd met extra functionaliteit. Een vraagteken =? geeft die regel een lagere prioriteit. En een tik links `= of rechts =` geeft aan waar de scan in de expressie begint, aan de linker of de rechter kant, en in welke richting 'l-r' (of 'r-l' anders) de match voor de tweede vorm (als die na de spatie voorkomt) gezocht wordt. In de regelvormen aan beide zijden staan alleen de actieve tekens in de expressie. Deze bepalen links van het evaluatieteken de selectie passage(s), en geven rechts ervan aan hoe deze door de evaluatie zal veranderen. Variabelen in een regelvorm zijn altijd gretig, zodat de selectie van b alle beschikbare enen in de expressie opeet. De vorm met equivalentie ≡ wordt in de input expressie met voorrang overal vervangen (eventueel), maar is later alleen direct na regel '5.' van toepassing, waar met m=0 een variabele werd aangeplakt op rij. Evalueer die regel `= die vanaf links genomen in de expressie het eerst zijn vorm vindt of compleet maakt (minst rechts). Selectie begint aan de linker kant van de expressie tot aan de spatie of breek, waar een inactieve passage kan volgen met wachtende afgetelde iteraties. Voor de tweede vorm, scan 'l-r' in de expressie tot ook dit actieve deel bij de regel past. Zo selecteert Adam steeds de eerste aftelbare iteratie vanaf links in de expressie. - - - - - - - - - - - - - - - - De vorm van de uitkomst waarmee evaluatie stopt, is een natuurlijk getal 1.. dat bestaat uit een groot aantal enen. Maar rechts volgen nog de resterende separatoren van de afgetelde iteraties. Zonder opruimregels daarvoor kunnen we de uitkomst b alleen uitkiezen, door met =? aan te merken dat de andere regels in Adam voorrang krijgen, anders zou regel '1.' meteen kiezen. Pas de definitie aan, zodat de regels niet in volgorde, maar steeds als eerste van links in de expressie worden toegepast. De vorm met = in regel '1a.' betreft de hele expressie en kiest de output b in de laatste evaluatie stap. Opruimen vooraf met regels '0.' maakt dit mogelijk. -A.II.0a. , =` 0 -A.II.0b. ,[m] =` 0 -A.II.1a. a,b = b Als we regels met selectie =` aan de rechter kant met prioriteit evalueren, dan worden de rest cellen van de hoogst afgetelde iteraties meteen opgeruimd. Of wacht tot de andere regels niet meer van toegepassing zijn en het totaal in b klaar is, en verwijder dan pas 'r-l' de reeks resterende separatoren. Merk op dat het teken nul 0 in unaire regels een leeggekomen plek aangeeft, en dus niet bij het getal links ervan hoeft te worden opgeteld. Maak een speciaal geval van regel '5.' en '4.' die rij dimensies apart expandeert. -A.II.4a. a,1b ,[1]1 `= a,a ,b,[1] We kunnen regel '5.' nu ook aanpassen, met m>0 in regel '5a.' als voorwaarde. Anders speelt regel volgorde in de definitie weer een rol. De selectie positie zou nog altijd precederen over die volgorde, maar als twee regelvormen op dezelfde positie in de expressie beginnen en eindigen, is het de regel die in de definitie eerder staat die moet worden toegepast. In ieder geval gaat de primitievere regel '4a.' dan voor en komen index arrays niet meer ,[] leeg te staan. Voeg naar keuze een speciale regel toe voor expressies, die in de evaluatie van standaard a,b,R nooit ontstaan. Met m≥0 in de dimensie index. a,[m1]1R = a,a,[m1]R a,[m1]1R = a,[m]a,[m1]R Die laatste variant maakt iets grotere getallen, maar significant is dat niet. Deze optionele regels hebben weinig toegevoegde waarde, winst is dat hiermee ook de multidimensionale expressies a,[m]R binnen het systeem vallen. $ 6.3. Eva's dimensies Op de eerste rij in Eva zagen we een primitief recursieve functie, die parameters aftelt tot ,1 en de som ab oplaadt. Met maar twee regels in dit systeem benaderden we de supermacht getallen. a,..f :k1 ~> a*{k>0}f1 In Eva gebruiken we reeksen van komma's ,{m} als dimensie separator, wat net zo werkt als de dimensie index ,[m] in Adam. Het gaat ons er nu om met twee type tekens zo groot mogelijke getallen te noteren. De eerste komma in de basis a,b van de expressie staat steeds alleen. Definitie van Eva systeem 'E.' met multidimensionale structuur 'II.' en telbare komma's als dimensie separatoren. De regels selecteren hun vormen vanaf links `= in de expressie. Eerst passen we regel '2.' zo mogelijk toe steeds, omdat =? uitstel aangeeft. -E.II.1. a,b `=? ab -E.II.2. a,b1 ,{m1}2 `= a,1 ,{m}ab,{m1}1 Een variabele vorm zoals b is gretig naar enen, zodat er in de expressie een separator op moet volgen. Zo ook met m≥0 in de kwantificatie van de dimensie, die het teken , gretig herhaalt, zodat er zeker een getal voor komt. Na opladen is de vorm b in de basis tijdelijk leeg en telt als 0 bij de volgende evaluatie stap. De 'l-r' scan pakt na de op de spatie overgeslagen vorm de eerste actieve iteratie rechts. De passieve passage kan leeg zijn, zodat de match links op de match rechts aansluit, of die kan bestaan uit een reeks ,{k_i}1.. afgetelde iteraties. Iedere cel 1 wacht daarin om via 1,{0}a te worden gevuld met 1a en af te tellen tot waarde a in de volgende stap. De onder dimensie tellers ,{m>1} nieuw in te voegen elementen in die reeks krijgen waarde a- na de aftel stap. - - - - - - - - - - - - - - - - Regel '1.' levert de uitkomst als de hele expressie door toepassing van de eerste regel is uitgewerkt. Alternatief is om met extra regel '0.' onderweg van rechts =` op te ruimen, zodat exacte regel '1a.' op het laatst optelt. Regel volgorde speelt zo geen rol in het systeem. -E.II.0. ,{m>0}1 =` 0 -E.II.1a. a,b = ab Door voorbeelden uit te werken en te schuiven met tekens in regel '2.' werd me duidelijk, hoe systeem Eva simpel en kloppend is te maken: met de methode om ab op te laden. Elke iteratie houdt een rest van 1 in de evaluatie, zodat het aantal komma's ,{m1} te gebruiken is om de dimensie m aan te duiden van de tussenliggende ruimtes. Zo staat een element ,,p1 vlak na een rij variabelen, die door iteratie van de teller p keer met een cel met toenemende som ,b wordt uitgebreid. 3,1,,3 2= 3,1,3,,2 2= 3,1,{0}3,2,,2 = 3,4,2,,2 2= 3,7,1,,2 2= 3,1,1,9,,1 0= 3,1,1,9 2= 3,1,4,8 2= 3,4,3,8 == 3,10,1,8 2= 3,1,13,7 == 3,37,1,7 2= 3,1,40,6 == 3,1,121,5 == 3,1,364,4 == 3,1,9841,1 0= 3,1,9841 2== 3,29521,1 0= 3,29521 1= 29524 Elke stap van d itereert 1,c naar 1,c*3+1 en dat == herhalen we hier. Maar we kunnen d ook itereren van b,1 naar b*3+7,1 dat werkt ook. De som b die naar rechts oplaadt op de rij zal groot worden, maar deze waarde is structureel minder significant dan de rij lengte. De eerste rij in de evaluatie van 3,1,,3,2 neemt toe tot 29527 parameters bijvoorbeeld (per 3,1,1,1,,29524 teller), wat tot enorm grote getallen leidt, ongeacht de hoogst opgeladen som ,b die al bijna even enorm is. - - - - - - - - - - - - - - - - Standaard dimensionale expressies in Eva hebben de vorm a,1R die tijdens de evaluatie gehandhaafd blijft. We kunnen ons systeem uitbreiden met speciale regels voor expressies a,{k>1}R die significant grotere getallen noteren. Bijvoorbeeld door de hogere teller a,,p om te zetten in a,1,{p}a een aantal komma's. Dit kan er geforceerd uitzien, omdat we de komma's in ,{p} er niet stapsgewijs overhevelen. a,{q1}p = a,{q}1,{p}a Adam's eerste index is ,[p] equivalent aan Eva's aantal van p1 komma's. En Adam's tweede index ,[1,q] laadt de eerste index een q aantal keer op met het subtotaal b van diens recursie. Dezelfde soort recursie kan hier rechts volgen, door regel '2.' te generaliseren. a,{q>0}b1 ,{m1}2 `= a,{q}1 ,{m}ab,{m1}1 Systeem Eva kan door deze speciale regels toe te voegen, de tweede index in de separator array van Adam evenaren (beperkt wel tot een enkele subarray). Normaler is om een regel als deze op die speciale dimensie separator waar m>0 toe te passen. a,{m1}2 `= a,{m}a,{m1}1 Dit stemt overeen met onze expressie standaard, waar een construct ,{n} dat ergens rechts van een construct ,{m} komt en gelijk of groter n≥m is, altijd dominant is en een significant groter getal zal uitdrukken. De getallen van Eva vergelijken we later Conway's pijlketens en Bird's arrays. Maar met twee primitieve evaluatie regels (uit te breiden tot drie regels) en twee tekens in de expressie (in de input en tijdens de evaluatie), is Eva ongetwijfeld het meest minimale systeem dat record grote getallen kan produceren. $ 6.4. Vergelijk met 'A' en 'E' In de functies van Adam 'A.' en Eva 'E.' passen we op dezelfde structuren verschillende regels toe, maar de uitkomsten zijn ongeveer even groot. Hier vergelijken we deze multidimensionale expressies eerst met Conway's pijlketens en vervolgens met onze Birdy versie van Bird's lineaire array. $ 6.4.1. Adam's rij 2 is Conway's →d We beginnen met de eerste cel in de tweede rij, die nog te vergelijken is met de supermachten. Het is vaak genoeg om te weten dat een expressie ongeveer groter dan ~> een eerdere bekende is, want als we met dit resultaat verder bouwen zouden de details toch verdwijnen. Tijdens de evaluatie zien we in de variabelen supersterren met minoriteit precedentie. Dit werkt a*{c2}a*{c1}b uit als a^{c1}(a^{c}b) omdat de lagere supermacht operatie voorrang krijgt. A(a,b,[1]c3) = a,a,b-,[1]c2 = a,a*b,,[1]c2 = a,,,a*b,[1]c1 = a,a**a*b,,,[1]c1 = a,a***a**a*b,,,,[1]c == a*{i}..b c3:1 ~> a*{c3}a*{c2}b ~> a*{c3}b Onthoudt dat in Adam reeksen ,.. de lege cellen ,0.. van iteraties zijn, die in de rij wachten om opgeladen te worden. En dat Eva met komma's ,{m1} een dimensie separator aanduidt, dezelfde die Adam met een index ,[m] noteert. E(a,b2,,c3) = a,1,ab1,,c2 = a,1+a*ab,1,,c2 = a,1,1,a*ab,,c1 = a,1,1,1,a**a*ab,,c ~> a,a***a**a*ab,1,1,1,,c ~> a*{i}..b c2:0 ~> a*{c2}a*{c1}b ~> ab*{c3}2 Zowel Adam als Eva drukken met de eerste parameter op de tweede rij, die de lengte teller van de eerste rij is, ongeveer een supermacht uit. Bij Adam krijgen we 1 superster meer, omdat Eva niet tot 0 maar overal tot 1 terugtelt. Die eerste teller wordt nu recursief opgeladen door de tweede parameter op de tweede rij. De lengte van de uitgetelde rij die resteert, is daarbij insignificant, omdat die slechts *{0} optelt. En elk volgende rij subtotaal dat we opladen naar cel c van de teller, maakt die rij consequent een *{b} supermacht groter. A(a,b1,[1],d1) = a,a,[1]b,d ~> a,a*{b}a,{b},[1],d ~> a*{..b..}a :d1: -> a→bo→d1→2 ~ a→b→(..a^bo..) :d: Variabele o staat voor een relatief klein natuurlijk getal: elk getal dat we decimaal kunnen noteren zou voldoen. Hier in de vergelijking met de pijlketen van Conway geven we met de toegevoegde o aan, dat de waarde van b ook wat groter kan zijn, de pijlketen expressie blijft dan toch kleiner. Recursie van superexponenten is het gebied van de getallen van Graham. Vergelijk hierin Eva met de van Bird afgeleide array functie Birdy. E(a,b,,1,d1) = a,1,,ab1,d ~> a,a*{ab1}2,,1,d ~> a*{..ab1..}2 :d: = B(a,2,..ab1..) :d: -> B(ab,d1,2,2) ~> B(a,..ab..,1,2) :d: ~ Bird(ab,d1,1,2) Op de tweede lijn in Eva lieten we het restant ,1.. op de eerste rij gelijk al weg, alsof het werd opgeruimd, omdat de expressie ongeveer wel gelijk blijft. De functie 'B.' is onze Birdy array functie die verschilt van Bird in de manier van herladen van cellen ,1 die op zijn. Bird nest daar rechts de subexpressies in, terwijl Birdy simpel de waarde van de tweede cel oplaadt, die we vooraf nesten met 1 extra in de derde cel. A(a,b1,[1],,e1) = a,a,[1],b,e ~> a,a→a→b→2,[1],,e ~> a→a→(..b..)→2 :e1: -> a→bo→e1→3 E(a,b,,1,1,e1) = a,1,,1,ab1,e ~> a,B(a,ab1,2,2),,1,1,e ~> B(a,..ab1..,2,2) :e: -> B(ab,e1,3,2) ~ Bird(ab,e1,2,2) Het verdere verloop over de tweede rij is daarmee duidelijk. Het algoritme van Adam en Eva blijft even traag als voorheen, waarbij elke volgende variabele op de rij een enkele recursie uitdrukt. A(a,b1,[1],{d1}c1) = a,a,[1],{d}b,c ~> a,a→a→b→d1,[1],{d},c ~> a→a→(..b..)→d1 :c1: -> a→b1→c1→d2 E(a,b1,,.1,..c2) :d1 = a,1,,.1,..ab1,c1 :d ~> a,B(a,ab,d1,2),,.1,..c :d1 ~> B(a,..ab..,d1,2) :c: ~ B(ab,c1,d2,2) ~ Bird(ab,c1,d1,2) Wie verwachtte dat de tweede rij gelijk ging lopen met Bird's lineaire array, zodra we de lengte teller met subtotalen van de eerste rij uitdrukken, komt bedrogen uit. Adam en Eva's oplaadregel is bijna zo krachtig en de oplaadsom is aanvankelijk supergroot, maar bij Conway en Birdy vindt dit opladen herhaaldelijk plaats, in een onafzienbare trein met geneste subexpressies. En dat maakt het verschil. $ 6.4.2. Adam's vlak is Conway's pijlketen De verschillen tussen Adam en Eva zijn in de vergelijking met snellere systemen eigenlijk onbelangrijk. Hier werken we alleen de voorbeelden voor Adam uit. De eerste parameter op de rij in Adam en Eva is de lengte teller van de rij ervoor. De teller die de tweede rij expandeert, loopt zoals we zagen gelijk met de vierde parameter d in Conway's pijlketen, die de tweede dubbele recursie uitdrukt. A(a,b1,[1],[1]d3) = a,a,[1],b,[1]d2 ~ a,a→a→b→2,[1],,[1]d2 ~ a,a→a→(a→a→b→2)→3,[1],,,[1]d1 ~ a,a→a→b!→4,[1],,,,[1]d ~ a,a→a→b!→d3,[1],{d2},[1]1 ~ a,a,[1],{d3}a→a→b!→d3 ~ a→a→(..a..)→d3 :a→a→b!→d3: ~ a→a→(a→a→b!→d3)→d4 ~> a→a→b!→d4 We voegen een uitroepteken toe aan de variabele b! om een groot getal aan te geven dat daarmee is gemaakt, maar dat toch niet significant groter wordt dan een normale input waarde binnen de gegeven context. Zoals een faculteit n! = 1.*i.. :n dat zou kunnen zijn. A(a,b1,[1],[1],d1) = a,a,[1],[1]b,d ~> a,a→a→a!→b1,[1],[1],d ~> a→a→a!→(..b1..) :d1 ~> a→a→b!→d1→2 Vervolg deze vergelijking over de hele derde rij van Adam. Deze werkt hetzelfde als op de tweede rij, maar nu met de vijfde parameter in Conway's pijlketen. A(a,b1,[1],[1],{e1}d1) = a,a,[1],[1],{e}b,d ~> a,a→a→a!→b→e1,[1],[1],{e1}d ~> a→a→a!→(..b..)→e1 :d1 ~> a→a→b!→d1→e2 Elke volgende rij in het vlak van Adam drukt een dubbele recursie over de vorige rij uit. Dit houdt in dat we steeds een schakel toevoegen aan Conway's pijlketen in de vergelijking. In zijn geheel geeft dit een tripel recursie. A(a,b.,[1]..,{z}y) :k ~> a→..b!→y→z1 :k Merk op dat systeem Eva hetzelfde presteert met als tekens enen 1.. en twee separatoren, namelijk , tussen variabelen en ,, tussen de rijen. Verschil is dat de afgetelden in Eva ,1.. en ,,1.. niet nul zijn, maar het aantal herhalingen ervan blijft gelijk aan die in Adam. De variabele rechts moet y1 zijn, maar telt dus hetzelfde aantal stappen van opladen. $ 6.4.3. Eva's dimensies is de Birdy rij Ga uit van een d aantal rijen in het Eva vlak, waarbij de laatste rij op dezelfde manier is verlengd als in de vergelijking van de tweede rij hierboven. Die tweede dimensie teller in Eva is te vergelijken met de vierde parameter in Birdy, die zoals we van Bird weten de lengte van Conway's pijlketen geeft. E(a,b,,,d2) = a,1,,ab,,,d1 ~> a,1.,,ab!.. :d1 ~> a,a.,,a..,a..b :d :b! ~> B(a,a,b!,d1) ~> B(a,b,1,d2) ~ ab→↑d3 Eva's tweede dimensie teller wordt recursief opgeladen met subtotalen b . E(a,b,,,1,c1) = a,1,,,ab,c ~> a,B(a,b,1,ab),,,1,c ~> B(a,b,1,..ab..) :c: ~ B(ab,c1,2,1,2) Zo correspondeert de tweede cel in Birdy met de laatste variabele in Eva, want beide tellen de functie recursie af over de hele expressie. Zo drukt de derde cel in Birdy de lengte uit van de laatste rij in Eva, die (net als haar eerste rij) een dubbele recursie toevoegt. Zo staat de vierde cel in Birdy gelijk aan het aantal rijen in het laatste vlak van Eva, die als een tripel recursie of pijlketen van Conway is aangeplakt. En zo telt de vijfde cel e in Birdy het aantal vlakken in de derde dimensie van Eva. Bij uitbreiding die in de laatste (meest rechtse) drie dimensionale array. E(a,b,,,,e1) = a,1,,,ab,,,,e ~> a,1.,,,ab!.. :e ~> B(a,b,1,1,e1) Zo krijgt in het algemeen in de vergelijking elke rechts gesorteerde Eva dimensie een corresponderende parameter op de rij van Bird of Birdy, die in Eva het aantal van die dimensies telt en in Birdy een type recursie toevoegt. Het aantal separator tekens k voor de hoogste Eva dimensie is dominant en dan het aantal :f van die te vullen ruimtes. E(a,b,{k1}f1) ~> a,1.,{k}ab!.. :f ~> B(a,b.,1..f) :k ~ ab→↑{k-}f1 De dimensionale structuur van Conway-Knuth →↑ superpijlen werd in sectie $.5.3.4. al precies vergeleken met de lineaire array van Birdy. De rij van Eva begint bij de supermacht parameter c van Conway en Bird. Het vlak met rijen ,, van Eva vormt Conway's pijlketen → of parameter d bij Bird. Elke volgende ruimte ,{k2} in Eva loopt een dimensie achter bij die van de Conway-Knuth →↑{k} superpijlen en opent een parameter op de rij van Bird. $ 6.5. Multidimensionale Birdy In multidimensionale expressies van systeem Birdy noteren we vrijwel even grote getallen als met Bird's multidimensionale arrays, maar Birdy's definitie is simpeler en de evaluatie van expressies verloopt stapsgewijs. Tot de functie recursie regel '4.' is de definitie van Birdy dezelfde als voor de rij, maar de tekst vorm X kan elke toegestane multidimensionale passage bevatten. -B.II.0. B(a) = a1 -B.II.1. B(X,[m]1) = B(X) -B.II.2. B(a,b1) = B(a1,b) == ab1 -B.II.3. B(a,1,2X) = a -B.II.4. B(a,b1,2X) = B(a,(a,b,2X),1X) -B.II.5. B(a,b1,`,2X) = B(a,a1,`b,1X) -B.II.6a. ,[0] ≡ 0 -B.II.6b. ,[1] ≡ , -B.II.7b. B(a,b`,[2m]2X) = B(a,b`,[1m]b,[2m]1X) Omdat eerdere regels voorrang krijgen, zijn er op de scan tic ` hier alleen nog reeksen ,[m_i]1.. afgetelde cellen te verwachten in meerdere dimensies, met separator indices m_i>0 en als eerste index ,[1] de gewone , komma. Opladen met regel '5b.' onder separatoren met index in Birdy is vergelijkbaar met oplaadregel '2b.' voor dimensies in systeem Adam. Maar de in Birdy uitgedrukte getallen worden door subexpressie recursie dimensionaal groter. Separator eliminatie met regel '6a.' is alleen nodig, als we de vorm van opladen op de rij '5a.' overslaan en daar de dimensionale vorm '5b.' toepassen. Afgetelde cellen in tussenliggende dimensies laten we in Birdy net als in Adam gewoon staan. Lengtes en maten nemen zodoende cummulatief toe en worden steeds allemaal opnieuw opgeladen. Maar al deze extra ruimte blijft insignificant vergeleken met elke daarboven opgeladen teller, die stapsgewijs een dominant grote ruimte toevoegt. Wel of niet opruimen verandert de uitkomst vrijwel niet. $ 7. Geneste arrays De dimensie index ,[m] van de separator komma kan worden verlengd tot een rij ,[m.,n_i..] van index variabelen. Een structuur of getalruimte met deze hierarchie van separatoren noemt Bird de hyperdimensionale array. Op hun beurt kunnen separatoren in index arrays weer met een volgende index of rij worden uitgebreid. Zo nesten we rijen in eerdere rijen tot elke mogelijke diepte. Zo'n systeem voor grote getallen noemt Bird "geneste arrays". $ 7.1. Geneste som Bouw een structuursom van geneste arrays op door nieuwe separatoren toe te voegen en rond daarbij alle maten gelijk af tot n , dat wil zeggen de variabele waarden en rij lengtes, die op dat niveau ondergeschikt zijn. Begin door op de rij met alleen komma , separatoren een som => van een n aantal variabelen n op te tellen. , => n*n ,[2] => n^3 ,[m] => n^n De structuursom van de multidimensionale array is aldus een macht. Elke volgende separator schept ruimte voor n keer de vorige som. ,[1,1] => n^n1 ,[m,1] => n^nn ,[m,n] => n^(n*n) De eerste index doet de som n^n keer. Met elke volgende index wordt de vorige index vermenigvuldiging n keer herhaald. ,[m,1,1] => n^(n*n1) ,[m,n,1] => n^(n*n*2) ,[m,n,n_2] => n^n^3 Volgt de structuursom met de eerste geneste rij in hyperdimensionale arrays. ,[m.,n_i..] = ,[,[2]1] => n^n^n ,[m,[2]1] => n^(n^n+n) ,[m.,n_i..,[2]1] => n^(n^n*2) Elke index stap rechts op een voorgaande index structuur herhaalt dus de toegevoegde exponent van de vorige som. ,[,[2]3] => n^(n^n*3) ,[,[2]m] => n^n^n1 ,[,[2]m,1] => n^(n^n1*2) Zodat elke rechtse index variabele 1 telt bij de dubbele exponent en elke extra index rij dus n daarbij optelt, wat de som geeft van het index vlak. ,[,[2]m,n] => n^n^n2 ,[,[2],[2]1] => n^n^nn ,[,[2],[2],[2]1] => n^n^(n*3) Vervolg de derde index dimensie door rechts lagere structuren te plaatsen. ,[,[3]1] => n^n^n^2 ,[,[3]m] => n^n^(n^2+1) ,[,[3],[2]1] => n^n^(n^2+n) Dezelfde index dimensie opbouwen herhaalt de hoge exponent in de som. ,[,[3],[3]1] => n^n^(n^2*2) ,[,[4]1] => n^n^n^3 ,[,[m]1] => n^n^n^n De tweede niveau index telt dus de tetratie n^^4 als som. Vergelijk de eerste index ,[m] met som n^^2 en de eerste index rij ,[,[2]1] daartussen met n^^3 als som. Als dat zo doorgaat dan telt de tweede geneste index rij de tetratie n^^5 op. ,[,[m,1]1] => n^n^n^nn ,[,[m,n]1] => n^n^n^n^2 ,[,[,[2]1]1] => n^n^n^n^n Als de structuur rechts op het eerste index niveau een index [L,n] extra krijgt, dan telt dat 1 bij de derde exponent. Gebeurt dit op het tweede geneste niveau, dan telt dat 1 bij de vijfde exponent. ,[,[,[m]1]1]1 => n^^6 ,[..2..]1 :t: => n^^tt- ,[..m..]1 :t: => n^tt De som van de hele ruimte van rij in rij geneste arrays volgt dan als tetratie. Met een even toren (van exponenten) bij een enkele index binnenin en een oneven toren bij een rij met een aantal indexen binnenin. $ 7.2. Meervoudige separatoren Om variabelen te ordenen in meerdimensionale arrays gebruikten we in Adam een index ,[m] bij de komma en in Eva reeksen ,{m} komma's. Zo kon Eva met maar twee tekens getallen uitdrukken ter grootte van Bird's lineaire array. Vergelijk meervoudige separatoren met telbare elementen, zoals voorgesteld voor Eva, versus <=> de gebruikte indexering in systeem Adam. Bij de hyperdimensionale arrays wordt op het eerste geneste array niveau in Adam aan de komma een rij van indexen gehecht. Dezelfde hyperruimte kan worden onderverdeeld door separatoren bestaande uit telbare komma's met een tweede type separator ,[2] ertussen, hier links in Eva. ,{m} <=> ,[m] ,{m},[2],{n} <=> ,[m,n] ,{m}.,[2],{n_i}.. <=> ,[m.,n_i..] Om deze opbouw te vervolgen maken we in dit hoofdstuk alle komma met index elementen ,[2] ook telbaar in Eva. Aan de dubbel geneste indexen in Adam ontspruit een even grote verzameling separatoren. De ruimte van deze arrays zouden we multidimensionale hyperdimensies kunnen noemen. L,[2],[2]R <=> ,[L,[2]R] ,[2],[2],[2] <=> ,[,[3]] ,[2].. :m <=> ,[,[m]] Deze groeiende elementen verdelen steeds links L en rechts R de voorgaande subruimte in de separator. Bij Eva is dat in de komma elementen serie, versus in de vooronder geneste index array bij Adam. L,[3]R <=> ,[L,[,1]R] ,[3].. :m1 <=> ,[,[m,1]] ,[n2].. :m1 <=> ,[,[m,n]] Eva's eerste telbare index vormt dezelfde ruimtes als de tweede enkele index in de dubbel geneste array van Adam. Dan volgt de tweede telbare index in Eva, eerste nest, versus de derde index in Adam, tweede nest. L,[1,2]R <=> ,[L,[,0,1]R] ,[1n,2].. :m1 <=> ,[,[m,n,1]] ,[1n_1,1n_2].. :m1 <=> ,[,[m,n_1,n_2]] Volgende komma indexen lopen parallel in Eva telbaar in het eerste nest, versus Adam enkel in het tweede nest. Adam's index dimensie teller m is de laagste variabele en deze ontbreekt bij Eva, zodat de index rij in Eva 1 korter uitvalt. ,[.1,..2] :p <=> ,[,[.,0..,1]] :p ,[.1n_i,..1].. :p :m1 <=> ,[,[m.,n_i..]] :p De eerste index rij van meervoudige separatoren blijkt equivalent te zijn aan de tweede geneste index rij met enkelvoudige separatoren. Elke geneste array kan op dezelfde manier in ruimtes worden onderverdeeld. Eén index niveau in Eva met telbare separatoren valt steeds gelijk uit met twee niveau's in Adam met enkelvoudige. Dus geldt voor alle geneste index rijen in Eva versus Adam. ,[..Q1..].. :q: :m & Q = n_i,.. :p <=> ,[..m,Q..] :qq: Een geneste arrays met telbare separatoren zal met een soortgelijk algoritme even grote getallen maken als een geneste arrays met enkelvoudige separatoren. Maar het aantal nest niveau's is de helft als separatoren op alle niveau's telbaar zijn. Helaas is dit geen belangrijke verbetering, het verschil bedraagt slechts een factor 2 qua nest diepte. Met in het systeem vervolg een diepte teller die oplaadbaar is, wordt dit verschil insignificant. Conclusie is dat telbare tekens aanvankelijk belangrijk zijn, te beginnen met de 1.. natuurlijke getallen en eventueel met ,.. komma's voor array dimensies. Maar dat array functies met enkelvoudige separatoren, enkelvoudige haakjes, etcetera, "oneven" zo snel over de geneste niveau's gaan, en na uitbreiding in de diepte ongeveer net zo snel. Als meervoudige tekens geen voordeel dienen, houden we regels voor recursies en structuur elementen liever simpel, door alleen te tellen met variabelen. Zulke systemen groeien door grotere structuur concepten te herkennen, en deze als voorheen recursief te herhalen vanuit de basis som. $ 7.3. Inladen Het opladen van indexen in een geneste array noemen we "inladen". Daar zijn wat problemen mee, zodat we de regels ervoor secuur moeten bepalen. Het eerste probleem is, dat het inladen van een subtotaal niet in een passieve index array met een lege teller erboven mag gebeuren. Want dan zou de opgebouwde som, de q in dit voorbeeld, verloren gaan. a,b1,[1,1]1 = a,a,[,1]b,[1,1] = a,a,[a-,]b,[1,1] == a,q,`,[1,1] ≠ a,a,`,[q,] Om dit te voorkomen moeten we separator index arrays opruimen, als de iterator ervan is afgeteld en die separator de laatste is binnen zijn ouder array of rechts in de expressie. Dit geldt eigenlijk alleen als die index arrays een actief separator-iterator element bevatten, zoals de ,1 in de subarray ,[1,1] rechts in het voorbeeld. Maar het is mooier en makkelijker om ook de afgetelde dimensionale separatoren ,[m] en enkele komma's , te verwijderen, die op het eind van de ouder array komen. Zolang er in de ouder array nog een actief element volgt, worden lege iteratoren vanzelf opnieuw opgeladen, dus hoeven we deze niet op te ruimen. Merk op dat Bird ervoor kiest om afgetelde separatoren te verwijderen, als deze links voor een grotere staan. Maar we vinden het te bewerkelijk om alle soorten index arrays qua grootte te moeten kunnen vergelijken. Het tweede probleem $ 7.4. Adam genest Definitie Adam systeem 'A.' met geneste structuur 'III.' voor het nesten van rijen separator indexen. De regels gelden in volgorde: de eerste vorm van links die past, evalueert de expressie naar rechts. -A.III.1. a,b = b -A.III.2. a,b,1 `= a,ab, -A.III.3a. ,[1] ≡ , -A.III.3b. ,[] ≡ 0 -A.III.4a. , =` 0 -A.III.4b. ,] ≡ ] -A.III.4c. ,[S] =` 0 -A.III.4d. ,[S]] ≡ ] -A.III.5a. a,b1, ,1 `= a,a, b, -A.III.5b. a,b1 ,[1S]1 `= a,a ,[S]b,[1S] Een 'l-r' scan `= selecteert de eerste vorm vanaf de linker kant in de expressie, en kan op de spatie   een fragment overslaan. Als een tweede vorm in de regel volgt, selecteren we de eerste match ervan (na de eerste vorm) in de expressie, mogelijk te vinden in een geneste array. In het overgeslagen passieve tekst fragment bevindt zich dus zeker geen match. Zo komt de selectie van een 'r-l' regel met =` direct rechts in expressies. Bij een regel met gelijk teken = selecteert de vorm een hele expressie. Met substitutie equivalentie ≡ kan de vorm overal te vinden zijn. Teken 0 staat voor een evaluatie waar de selectie vorm geheel vervalt. Een expressie in Adam kan eventueel tussen ronde A() haakjes staan. De tekst variabelen S zijn gesloten, zodat elk open haakje erin van een geneste index array [S_i] gepaard is aan een sluit haakje. Ons "rechts binnen" criterium is simpel te constateren. En we slagen er goed in, om alle inactief blijvende elementen te elimineren. Waarna regel '1.' de uitkomst geeft. Opruimen met regels '4.' moet wel tijdens de evaluatie plaatsvinden, met voorrang boven regels '5.' dus. $ 7.4. Eva genest Eva moet een systeem worden, dat met zo weinig mogelijk tekens en eenvoudige regels zo groot mogelijke getallen uitdrukt. Eerst nog bouwen we Eva's telbare komma's voor dimensies uit naar een rij hyperdimensionale indexen. Bij dieper geneste arrays zetten we het systeem over naar de bekende index variabelen. # 7.4.1. Eva's hyperdimensionale arrays Bird noteerde zijn hyperdimensionale arrays met separatoren bestaande uit een rij index variabelen, de eerste van zijn geneste arrays. We zagen in $.7.3.1 al hoe de rij indexen van Adam ook met aantallen komma's kan worden weergegeven en dan dezelfde ruimtes voor variabelen schept. Hier vervolgen we het dimensionale systeem 'II.' van Eva en introduceren de enkele punt komma ; als separator tussen de reeksen van komma's. Definitie systeem Eva 'E.' voor de eerste geneste rij 'IIIa.' met telbare komma's als hyperindexen. Pas die `= regel toe, die een vorm selecteert die het meest links in de expressie begint. -E.IIIa.1. a,b = b -E.IIIa.2a. ,;,1 ≡ ,1 -E.IIIa.2b. ,,1 =` ,1 -E.IIIa.2c. 1,1 =` 1 -E.IIIa.3. a,1b ,;,, `= a,1 ,{1ba};, -E.IIIa.3a. 1m; ≡ ,m; -E.IIIa.3b. a,1b ,;,, `= a,1 ,ba;, -E.IIIa.4. a,b1 ,S2 `= a,1 Sba,S1 & S = ,{1m}.;,{1n_i}.. :k≥0 De reductie van expressies verloopt dan zo. a,b1,`,,;,,;,,2 4,2= a,1,`,;,,;,,ab 3= a,1,`,{a1};,;,,ab == a,c1,`,{a1};,;,,2 4,2= a,1,`,{a};,;,,ac == a,d1,`,,;,;,,2 4,2= a,1,`,;,;,,ad 3,2a= a,1,`,;,{a1}ad 3= a,1,`,{a1};,{a}ad Er ontstaat een probleem. De komma reeksen in de separator worden steeds met de constante a opgeladen en niet met de groeiende subtotalen, hier met b<c<d in de evaluatie trein aangegeven. Want op het moment dat een komma index of aantal tot 1 wordt afgeteld, schuift het subtotaal naar de variabele erboven. De uitkomst blijft zodoende klein. Het algoritme van Adam of Eva kopieert alleen de constante en nergens het subtotaal. Dit kan alleen werken, als een geneste array wordt opgeladen door de iterator of index, die rechts in de array erboven staat. De regel daarvoor moet duidelijk maken waar de separator structuur precies eindigt, wat niet triviaal is. Bij meerdere niveau's van arrays zal de subtotaal waarde zich trapsgewijs naar binnen toe verplaatsen. Het geeft geen pas daar in Eva steeds de constante a bij op te tellen. # 7.4.3. Eva's geneste arrays Voor geneste arrays in het algemeen in Eva stappen we over op het komma index systeem van Adam. Definitie Eva systeem 'E.' voor geneste rijen 'IIIb.' met regels in volgorde. -E.IIIb.1. a,b = b -E.IIIb.2a. ,[1] ≡ , -E.IIIb.2b. ,[] ≡ 0 -E.IIIb.3a. ,1 =` 0 -E.IIIb.3b. ,1] ≡ ] -E.IIIb.3c. ,[S]1 =` 0 -E.IIIb.3d. ,[S]1] ≡ ] -E.IIIb.4. a,b1 ,[1S]2 `= a,1 ,[S]ab,[1S]1 -E.IIIb.4a. a,b1 ,2 `= a,1 ab,1 -E.IIIb.4b. a,b1,2 `= a,ab1,1 .. # 7.5. Birdy's geneste arrays # 7.6. Bodhi's geneste arrays We kiezen er bij het opladen in Bodhi systeem 'Bo.' voor om subtotaal b te laten staan, om daarna de eventueel afgetelde indexen voor zijn rekening te nemen. Dit lijkt het simpelst, maar betekent dat er een kopie van b moet worden gemaakt om in te voegen. De voorafgaande reeks afgetelde iteraties wordt daarna ook met het grote subtotaal b gevuld. Maar toch zijn Bodhi's uitkomsten niet significant groter dan die bij Bird of Birdy, waar de ruimte links met de kleine a wordt gevuld. Regel voor het opladen van afgetelde variabelen ,1 op de eerste rij. Stel k>0 voor het aantal lege cellen, zodat c=1 als eerste kan opladen. -Bo.I.5. B(a,1b.,1..,2X) :k "opladen" = B(a,1b.,1..b,1X) :k Herhaalde toepassing == van deze regel vult het hele afgetelde deel links in de rij stapsgewijs met kopies b>0 van het subtotaal. == Bo(a,1b,1.b,..1X) :k = Bo(a,$.,b..,1X) :k - - - - - - We kunnen in evaluatie voorbeelden de gebruikte regelnummers aangeven. Ook expressies B(a,1,1) en B(a,1,1,R) waar regel '3.' geen match voor vormt, kunnen onder regel '5.' vallen. B(a,1,1,2,3) 5= B(a,1,1,1,3) 5== B(a,1,1,1,1) 1== B(a) 2= a Zulke expressies ontstaan nooit in de evaluatietrein en hebben als input weinig zin. Altijd is die expressie triviaal te herleiden tot a . - - - - - - Vergelijk Birdy 'B.' met Bodhi 'Bo.' B(a,b1,2,2) ~> Bo(a,b1,2,2) <- (a,3,..a..1) :b: Omdat: B(a,b1,2,2) = (a,(a,b,2,2),1,2) := (a,(a,b,2,2),(a,b,2,2)) <- (a,(a,a,(a,b,2,2)),(a,b,2,2)) =: (a,3,(a,b,2,2)1) == (a,3,..a..1) :b: # 7.6. Systeem vergelijking ..