Supermachten

Link naar dit blog:
allergrootste.blogspot.nl/2017/10/supermachten.html
edit 2019.

§2.2 Supermachten

Nadat machtsverheffen lange tijd de hoogste operatie was, vond de algo­ritme kenner Donald Knuth³ in 1976 zijn telbare opera­toren ↑{c} uit, om ge­tallen in het gebied van super­machten te noteren. Alleen de aller­kleinste super­machten zijn nog precies uit te rekenen.

De elementaire operaties tot aan machten beschouwen we als vooraf gegeven. Eerst komt de enkele pijl ↑ die bij Knuth de operator ^ is van gewone machten. Hij legt dit uit als her­haald vermenig­vuldigen, wat herhaald op­tellen is. Tetratie noteert Knuth met twee pijlen ↑↑ en hij werkt dit uit tot een rij machten, enzovoort.

Regels voor Knuth's pijlen, die wij altijd van rechts oplossen.

• a↑{c}1 = a {c>0}
• a↑{c1}b1 = a↑{c}a↑{c1}b =! a↑{c}a↑{c}a↑{c1}b- == a↑{c}..a :b

De operator voorrang voor supers ^{c} geldt niet voor Knuth's ↑{c} pijlen, die we strikt =! rechts asso­ciatief op­lossen binnen een reeks operaties. Dit past bij de r-l evaluatie van Conway's pijl­ketens C.I en bereidt onze extensie naar super­pijlen voor.

Het was de verbeelding van de wiskundige Ronald Graham, expert in de grafen­theorie, die popula­risator Martin Gardner⁴ aan­spoorde om een buite­nissig aantal van Knuth's pijlen te gebruiken om Graham's getal mee aan te duiden. Graham's getal is een boven­grens voor een reken­kundig probleem met bi­chromatische hyper­machten, zoals het Neder­landse Guinness record boek⁵ dat noemde. Hoewel Gardner de schatting, die Graham eerder publi­ceerde⁶, danig over­dreef.

Het mooie van het bewijs dat Graham gaf, is dat de oplossing zeker bestaat, hoewel dit getal wel eens onbe­rekenbaar ver weg zou kunnen liggen. Maar het is voor de hand liggend dat het klein is.
Zoals het 9e priemgetal p8+4 = 23 dichter­bij ligt, dan de boven­grens 1+1.*pi.. :8 die het bestaan ervan bewijst.
Tegenwoordig zoekt men de oplossing voor het probleem van Graham trouwens vanaf 13 en zijn boven­grens is tot 2↑↑↑6 terug­gebracht.

Graham's record getal is een hyper­macht, die we noteren als recursie over super­macht pijlen, van binnen naar buiten te tellen en van rechts af uit te werken.

• 3↑{..4..}3 :4↑3: = 3↑{..3↑↑↑↑3..}3 :63:
• 3↑↑↑↑3 = 3↑↑↑3↑↑↑3 =! 3↑↑↑3↑↑3↑27.

Knuth's operaties werden eerder al uitgedrukt in een functie, die we voor het eerst in 1925 bij David Hilbert⁷ tegen­komen. Hilbert begint om op­tellen, vermenig­vuldigen en machten te her­halen, om daarmee de operatie van tetratie aan te duiden.
De hogere supermachten pakt Hilbert in in zijn twee­ledige recur­sieve functies Hc die we aldus her­schreven.

• H₁(a,b) = a+b = ab
• H_c1(a,1) = (H_c,a,1) = a
• H_c1(a,b1) = (H_c,a,b1) = H_c(a,(H_c,a,b)) == H_c(a,..(H_c,a,1)..) :b: = H_c(a,..a..) :b:

Hilbert gaf zijn voorzet Ha(a,a) en Wilhelm Ackermann schoot die er in 1928 in, met een stroef bewijs⁸ dat deze functie niet primitief recursief is te formu­leren.
Ackermann functie G(a) = F(a,a,a) werkt met deze regels.

• F(a,b,0) = a+b = ab
• F(a,0,1) = a*0 = 0 F(a,0,2) = 1 F(a,0,c>2) = a (vervroegd)
• F(a,b1,c1) = F(a,F(a,b,c1),c) == F(a,..F(a,0,c1)..,c) :b1:

Het is mogelijk om in één regel, vanuit unair optellen, met Hilbert's en Knuth's repetitie van operaties in haakjes, een complete definitie te geven van super­machten.

a^{c}b1 = a*{c1}b1
  = (a*{c}..a..) :b:

Knuth's pijl operaties, onze super­sterren en de eerdere recursieve functies hebben allen het­zelfde bereik. Wij noemen het super­machten, of dubbele recursie. Daar spelen twee recursies: een grote met iter c over een kleine met iter b over een constante a>1.

De Hongaarse wiskundige Rozsa Péter had in haar boek⁹ uit 1950 slechts twee para­meters nodig in een dubbel recur­sieve functie.
Definieer Péter's P met naam en positie van variabelen omge­zet.^d De functie begint met op­tellen van een constante a=1.

• P(b,0) = b+1 = b1
• P(0,c1) = P(1,c)
• P(b1,c1) = P(P(b,c1),c) == P(..P(0,c1)..,c) :b1: = P(..1..,c) :b2:

Om systemen voor grote getallen te vergelijken, volstaan we met het uit­rekenen van de belang­rijke iteraties. Zodoende, als de voort­zetting inzich­telijk is, levert dit een bewijs door demonstratie.

# Demonstratie 2.2

Péter's P(b,c1)+3 = 2*{c}b3 uitgedrukt in super­machten.

• P(b,1) = P(..2..,0) :b: == 2.+1.. :b = b+2
• P(b,2) = P(..3..,1) :b: == 3.+2.. :b = b*2+3
• P(b,3) = P(..5..,2) :b: == (..5..*2+3) :b: = 2^(b+3)-3.
• P(b,4) = P(..13..,3) :b: == 2^(..16..).-3 :b: = 2^^(b+3)-3.
• P(b,5) = P(..2^^4-3..,4) :b: == 2^^(..2^^^3..).-3 :b: = 2^^^(b+3)-3.
• P(b,c+3) = P(P(b,c3),c2) == P(..P(1,c2)..,c2) :b: = P(..2^{c}4-3..,c2) :b: == 2^{c}..2^{c1}3-3 :b = 2^{c+1}(b+3)-3.

Péter's P is een speciaal geval van functies Pa waar a=1.
In algemene functie Pa telt de initiële regel a een­kennig op.

• P_a(b,0) = a+b = ab
• P_a(0,c1) = P_a(1,c)
• P_a(b,c1) = P_a(P_a(b-,c1),c) = P_a(..1..,c) :b1:

Het is interessant om de uitkomsten bij waardes van a te vergelijken.
Na P0(b,0) = b reduceert P0 steevast tot 1.

• P₀(b,1) = P₀(..1..,0) :b: == 1
• P₀(b,2) = P₀(..1..,1) :b: == 1
• P₀(b,c2) = P₀(b,c1) = 1

Dat P2(b,c)+3 = 2*{c}b3 volgt uit P2(1,0) = 3 en eerdere demon­stratie van Péter's P1 omdat ook P1(1,1) = 3 en daarna is P2 op dezelfde wijze recursief bepaald.

• P₂(b,0) = b2 = P₁(b,1) = 2+b3-3.
• P₂(b,1) = P₂(..3..,0) :b: == 3.+2.. :b = b*2+3 = 2*b3-3.
• P₂(b,c) = P₁(b,c1) = 2*{c}b3-3.

Ook de vergelijking van P3 met super­sterren is merkwaardig exact.

• P₃(b,0) = b3 = 3+b2-2.
• P₃(b,1) = P₃(..4..,0) :b: == 4.+3.. :b = b*3+4 = 3*b2-2.
• P₃(b,2) = P₃(..7..,1) :b: == (..1..*3+4) :b1: = 3.*3..-2. :b1 = 3^b2-2.
• P₃(b,3) = P₃(..25..,2) :b: == 3.^3..-2. :b1 = 3^^b2-2.
• P₃(b,c2) = P₃(..3^{c}3-2..,2) :b: == 3^{c}..3^{c1}2-2 :b = 3^{c1}b2-2.

Hierna komen de details bij supermachten niet meer overeen. Er is geen vast getal q voor de optel aftel routine en dit is niet te repa­reren.

• P₄(b,1) = P₄(..5..,0) :b: == 5.+4.. :b = b*4+5 = 4*(b+q)-q. & q=5/3
• P₄(b,2) = P₄(..9..,1) :b: == (..1..*4+5) :b1: = 4^b1*(1+q)-q. ≈ 4^(b+qr)-qr. r≈.041
• P₄(b,3) = P₄(..41..,2) :b: ≈≈ 4^..(1+qr)-qr. :b1 ≈ 4^^bqrs-qrs. s<.001
• P₄(b,c) ≈ 4*{c}(b+qr)

De twee systemen zijn aleen bij benadering ≈ te vergelijken. In feite zijn er geen op­lossingen voor varia­belen qr, qrs, etc. We noemen dit surro­gaat varia­belen.

• P₅(b,1) = P₅(..6..,0) :b: == 6.+5.. :b = b1*5+1 = 5*bq-q. & q=3/2
• P₅(b,2) = P₅(..1..,1) :b1: = 5^b1*q1-q. = 5^bqr-q. ≈ 5^bqr-qr. & qr = Log(5,q1)+1 ≈ 1.569
• P₅(b,c) ≈ 5*{c}bqr

Voltooi de benadering van de dubbele recursie Pa met super­macht opera­toren. Voor grote a dalen de optel aftel surro­gaten tot limiet 1.

• P_a(b,1) = P_a(..1..,0) :b1: == a1.+a.. :b = b1*a+1 = a*bq-q. & q=a1/a-
• P_a(b,2) = P_a(..1..,1) :b1: = a^b1*q1-q. = a^bqr-q. qr ≈ 1+Log(a,2) ≈ 1
• P_a(b,c) ≈ a*{c}b1

Het is aardig om te weten dat de limiet van Pa een stap in b verder is dan bij super­sterren, maar het zet geen zoden aan de dijk. Geteld vanaf c produ­ceren beide systemen onge­veer even grote ge­tallen.

Omzetting van Rozsa Péter's dubbel recursieve functie P() naar een links asso­ciatieve `= versie met oparator teken ¶ is een­voudig.

• b¶1 `= b11
• 1¶c1 `= 1¶c¶c
• b1¶c1 `= b¶c1¶c == 1.¶c.. :b2

Zo vermijden we de 0 en subexpressie haakjes. En we werken b¶c1 stap na stap uit tot een reeks van b van zulke ¶c recursies.

Supersterren *.. regelen we ook liever met enkele stappen. Maar om deze l-r te evalueren, zonder haakjes of prece­dentie, is lastiger. We intro­duceren pop opera­toren om super­machten te scheiden.
In deze definitie van supersterren is c≥0 zodat *{0} unair optelt.

• a*{c1}b1 `= a+*{c}a*{c1}b
• p+*{c}a+ `= a*{c}p+
• p+*{c}a*{c1}1 `= a+*{c}p

Hogere superster operaties worden van de uitwerking van de lagere apart gehouden door er pop­sterren +*.. tussenin te plaatsen. Als een plus volgt, dan valt de linker pop + voor deze sterren weg, terwijl de operanten om­keren of pop­schuiven. Van dit pop­schuiven zagen we al een voorbeeld met tetratie in blog §2.1.

We zagen gewone plus elim­inatie als alter­natief en de opera­toren #.. daar­van noemden we hek­machten.
Vul de regel a#{c}+b+ = a#{c}b+ in in het super­sterren schema. Ver­vang daarin de ster * door een hekje # om hek­machten te maken. Ook hier telt #{0} een­voudig direkt op, zodat de initiële regel voor c=0 over­bodig is.

De regels voor een hek­macht functie.

• #(a,1,c1) = a
• #(a,b1,1) = #(a,b,1)a
• #(a,b1,c1) = #(#(a,b,c1),a,c) == #(..a..,a,c) :b:

Hek­machten lossen we steeds links associatief op.
Bereken de snelheid van onze #.. hek­macht operaties ten opzichte van Knuth's ^.. super­machten.

• a##a##a = (a^a)^a = a^(a*a)
• a###b1 = a###b^a = a^(1.*a..) :b = a^a^b
• a1###a###a ≈ a1^a1^a^a
• a####b ≈ a^^b^a^^b ≈ a^^b1
• a#{4}a#{4}a ≈ (a^^a1)^^a1 ≈ a^..a^^a1 :a = a^^aa1
• a#{5}b2 ≈ a#{5}b1^^a1 ≈ a^..a^^a{b}1 :a ≈ a^^(a*b1)
• a#{5}a1#{5}a ≈ a^^a^^(a*a)
• a#{6}b ≈ a^^^b\*a
• a#{cc1}b ≈ a^{c}(a*b)
• a#{cc}b ≈ a^{c}b

Vanaf c=2 machten wordt het aantal hekken #.. verdubbeld ten op­zichte van *.. sterren. Een halve super­macht tilt het grondtal a de super­exponent in (eerst als macht, dan als factor) en de andere helft ont­wikkelt de super­toren van expo­nenten.

In de Grzegorczyk hierarchie¹⁰ is er geen aparte klasse recur­sieve functies tussen de super­machten in. Toch slaagden we erin c op te delen: in functies die op halve super­snelheid gaan en op hele. Wie weet is zo rationele ver­deling van supers c mogelijk…?

Toch denken we dat een fijnere algoritmische verdeling buiten iteratie over operant b van super­machten niet bestaat. En dat alle algo­ritmen die primitieve recursie over­treffen dit doen door te itereren over c.
Dit is ons dubbele vermoeden. Dubbele recursie kan dus niet 3 keer of 1/3 keer zo snel gaan als super­sterren bijvoor­beeld.

In het vervolg speelt deze kwestie bij geneste arrays. Als we posities in array functies indexeren, moeten geneste arrays dubbel zo diep zijn om het­zelfde getal uit te drukken. We tonen aan, dat verdub­beling van de nest­diepte een geschikte uit­komst geeft. Enkel of dubbel zijn in deze structuren blijkbaar de enige natuur­lijke alter­natieven…∴

^d. Keer de richting van de para­meters om, zodat de laatste para­meters de grotere ge­tallen maken, gg: Péter's recursion in "Number operations" voor bigPsi (concept 2011).

^3. Het is belangrijk om te begrijpen dat eindige getallen extreem groot kunnen zijn, in Donald Knuth "Coping with Finiteness" 1976.
^4. Een vergaande generalisatie van Ramsey theorie [grafen theorie], Martin Gardner over Graham's number, in "Mathe­matical Games" Scientific American, Nov. 1977.
^5. Het hoogste getal dat ooit in een rekenkundige proef werd gebruikt, Guinness over Graham's number, p.59 in "Het groot Guinness record boek" 1989.
^6. Deze bovengrenzen zijn meestal enorm, Ron Graham over Graham's number, in R.L. Graham & B.L. Rothschild "Ramsey's theorem for n-parameter sets" 1971.
^7. Deze recursies [over c] zijn geen normale, staps­gewijze, in David Hilbert "On the infinite" 1925, p.388 in "From Frege to Gödel" 1967.
^8. De functie F(a,a,a) neemt sneller toe dan elke type 1 functie in Wilhelm Ackermann "On Hilbert's con­struction of the reals" 1928, p.495 in "From Frege to Gödel".
^9. Het is voldoende om een tweetallige 'majorant' ψ(m,n) te definiëren, p.106 in Rozsa Péter "Recursive Functions" 1967.
^10. Elke klasse En van recursieve functies is gesloten onder de operaties van substi­tutie en beperkte recursie, in Andrzej Grzegorczyk "Some classes of recursive functions" 1953.