Machten

Link naar dit blog:
allergrootste.blogspot.nl/2017/09/machten.html
edit 2019.

§2.1 Machten

Er zijn drie elementaire operaties tussen getallen. Optelling + wat getallen samen telt, vermenig­vuldiging * wat tellen herhaalt, en nu dan machts­verheffing met ^ of ** als operator. Zowel de operatie als het resultaat ervan noemen we een macht.

Machtsverheffen herhaalt vermenig­vuldigen met het­zelfde getal. Dat kan per stap worden gedaan. Onze macht operator is ^ een dakje, super­script notatie is onge­schikt voor de computer input lijn.

• a^1 ?= a
• a^b1 ?= a^b*a == a^1.*a.. :b = a*..a :b

De voorwaardelijke toewijzing ?= staat hier, omdat een macht rechts in een reeks elemen­taire operaties voor­rang krijgt. Bijv. de ex­pressie a^b^c betekent a^(b^c), waar de sub­expressie b^c eerst wordt uit­gewerkt (tot exponent).

Onze logaritme functie Log is een inverse van machts­verheffing, en nog wat weetjes over operaties met machten.

• m^p*m^q = m^pq (m^p)^q = m^(p*q) n^-*n = 1
• m^Log(m,n) = n Log(m,p*q) = Log(m,p)+Log(m,q) Log(m,n)*Log(k,m) = Log(k,n)

Ster operaties *.. evalueren we hier strikt `= vanaf links. Daar zijn geen haakjes bij nodig of verge­lijkende prece­dentie regels. Alleen een rechter operatie zonder plus, die volgt na een ope­ratie met pop plus, wordt met voor­rang geholpen.
Het aantal sterren tellen we in deze evaluatie af naar links, tot we op nul *{0} uitkomen en de operanten ac natuurlijk optellen.

Een l-r definitie voor machten met ** twee popsterren.

• a**b1 `= a+*a**b (popster)
• c+*a+* `= a*c+* (popschuif)
• c+*a**1 = a*c (ontpop)

We gebruiken een popster om een macht af te schermen van zijn uit­werking, die links plaats vindt. Het plus teken van +* fungeert als haakje, maar is tijdelijk en verdwijnt als deze als ster operatie op­schuift voor een nieuw pop­ster haakje.

# Experiment 2.1

Ontwerp een Superplus systeem. Pas de regels in volgorde toe, zodat c>1 voor de eind iter­ator en b>0 en c>0 in de recursie.

• a+b = ab
• a+{c}1 = a
• a+{c1}b1 = a+{c}a+{c1}b

Als we hierbij prioriteit tegelijk met subexpressies overboord gooien, en +.. opera­toren puur l-r evalueren, werkt dat dan?
Ja en snel, twee plussen ++ herhaalt de verdubbeling van a.

a++b2 = a+a++b1
  = aa++b1 = aaaa++b
 == a.*2..++1 :b1
  = a*2^b1

Een post operatie \^ plaatst na uitwerking van de vooraf­gaande operatie een extra expo­nent bovenop de hoogste sub­operant daarvan. Post operatie \* vermenig­vuldigt deze hoogste exponent dan wel super­exponent (met prio­riteit zodra deze er is).
We plaatsen de post backslash rechts en draaien de operanten niet om, zoals bij de pop plus links van de operatie.

We vergelijken superplussen met ^.. supermachten, die in §2.2 een histo­risch overzicht krijgen. De expressie links van ≈> is maar weinig (insignificant) groter dan die rechts.

• a1+++b3 = a1++a1+++b2 = a1*2^a+++b2 ≈> 2^(a*2^a)+++b1 ≈> 2^2^2^a1+++b ≈≈ 2^..a1+++1 :b2 = 2^^b2\^a1 ≈ a^^b3
• a1+{c2}b2 = a1+{c1}a1+{c2}b1 ≈ a^{c}a1+{c2}b1 ≈ a^{c}a^{c}a1+{c2}b ≈≈ a^{c}..a1 :b1 = a^{c1}b1\^{c}a1 ≈> a^{c1}b2

Door twee tekens, de 1 en + plus, te gebruiken krijgen we super­grote ge­tallen. Ook al laten we de enkele tekens domweg vallen, in de initiële regels.
Bijv. 11+++++111 ≈ 2^^^^3 = 2^^65536.

Omdat a+{c}b <≈ a*{c}b zijn de recursies in de functies van super­plussen D(a,b1,c1) = D(D(a,a,c),b,c1) en van de super­machten F(a,b1,c1) = F(a,F(a,b,c1),c) die we later bespreken, onge­veer even snel.

Ontwerp nu een hybride functie met meervoudige recursie op twee posities. Noem dit de Excalibur functie: het twee­snijdend zwaard.

• E(a,b,1) = E(a,b) = ab
• E(a,1,c) = a
• E(a,b1,c1) = E(E(a,a,c),E(a,b,c1),c)

Rozsa Péter stelt² dat recursie in meerdere variabelen tegelijk niet signi­ficant sneller gaat, en dit willen we testen.

• E(a,b1,2) = E(aa,E(a,b,2)) == E(aa,..a..) :b: = a*2*b+a
• E(a1,b1,3) ≈> E(a^2*2,E(a,b,3),2) ≈> aa^2*E(a,b,3) ≈≈ aa^2*..a :b = aa^bb*a
• E(a1,b1,4) ≈> E(aa^aa,E(a1,b,4),3) ≈> aa^(a*3*E(a1,b,4)) ≈≈ a1^..(a*a*3) :b>0 ≈> a1^^b1\^2
• E(a,b1,5) ≈> E(a^^a,E(a,b,5),4) ≈> a^^(a+E(a,b,5)-) ≈≈ a^^..aa- :b>0 <≈ a^^^b1\*2
• a^{c}b < E(a,b,c2) <≈ a^{c}b\*2 < aa^{c}b

We verwachten dat hogere expressies E als de bij c=5 berekende zullen ver­lopen, en niet verder zakken richting F.
In ieder geval voegt de extra recursie hier weinig toe, al is argument a onge­veer ver­dubbeld. Misschien als we de extra stap E in stap F nesten, dat dat hoger­op groter uitpakt?

• G(a,b,1) = G(a,b) = ab
• G(a,1,c) = a
• G(a,b1,c1) = G(a,G(G(a,a,c),b,c1),c)

Als we onze Griffioen functie uit­werken, dan neemt super­macht c 1 toe, verge­leken met E of super­plussen. In het vervolg telt het tweede argument bijna als b*2, wat te ver­wachten viel door het dubbele nesten in de recursie stap.

• G(a,b2,2) = a+G(aa,b1,2) = a*3+G(a*4,b,2) == a*(2^b2)- ≈ 2^b2
• G(a,b2,3) ≈ 2^G(2^a,b1,3) = 2^2^G(2^2^a,b,3) == 2^^b1\^2^^b1\^a = 2^^bb2\^a ≈ 2^^bb4
• G(a,b1,4) ≈ 2^^G(2^^aa,b,4) == 2^^..2^^..aa :b :b = 2^^^bb\^^aa ≈ 2^^^bb2
• G(a,b1,c1) ≈ 2^{c}bb\^{c-}aa ≈ a^{c}bb1 ≈ 2^{c}bb2

Omdat argument c ongemoeid blijft, draagt het nesten van meerdere sub­expressies niet wezen­lijk bij aan het maken van grotere ge­tallen, als die recur­sies op zich al super­machten op­leveren.∴

Een serie gelijke operaties komt in de evaluatie van super pop­ster operaties nooit voor. We zien duo's van ster en pop­ster, met een naar links af­nemend aan­tal sterren.
Als we een pop operatie links vóór de macht plaatsen, dan zal deze ope­reren op de hoogste factor, die steeds naar rechts schuift. Eerst een simpel voorbeeld, dan de algemene formule.

• 1+2**3 = 1+2+*2**2 = 3+*2**2 = 3+*2+*2**1 = 2*3+*2**1 = 2+2*2+*2**1 = 4+2*1+*2**1 = 6+*2**1 = 2*6 == 12.
• p+*{q}a*{c1}b1 = a*{q}p+*{c}a*{c1}b = a^{c}b1\*{q}p

Bij rekenen met sterren, moeten we soms haakjes toe­passen. Maar hier gaat het erom één ster operatie in stappen uit te werken.
Een pop­ster +*{c} stelt zijn operatie niet alleen uit, maar draait de operanten daarna ook om. Dit pop­schuiven blijft gelijk in geval +* want vermenig­vuldigen is commu­tatief, maar bij super­machten maakt om­draaien groot verschil.

Pop­schuiven is nodig vanaf +** bij dubbele machten. Die ont­staan bij het uit­werken van tetraties *** in enkele stappen = zoals we dat hier­onder doen, tot de her­haling == ervan duidelijk is.

3***3 = 3+**3***2
      = 3+**3+**3***1
      = 3**3+**3***1
 3**3 = 3+*3**2
      = 3+*3+*3**1
      = 3*3+*3**1
  3*3 = 3+3*2
      = 3+3+3*1
      = 6+3*1
      = 9 (ontpopt)
 3**3 = 9+*3**1
      = 3*9 (ontpopt)
     == 27.
3***3 = 27+**3***1
      = 3**27 (ontpopt)
      = 3+*3**26
     == 9+*3**25
      = 9+*3+*3**24 (popster)
      = 3*9+*3**24 (popschuif)
     == 27+*3**24
    === 7625597484987.

Stel dat we de regel voor pop­schuiven vervangen door pop­ruimen, dus plus + elim­inatie zonder dat er operanten ver­wisseld worden. Dan blijven hek­machten #.. ver achter op *.. super­sterren.
Hierboven zou 27##3 omdat (3^3)^3 = 3^(3*3) = 3^9 al een factor 3^18 schelen. Hoe klein is dan 4####4 in vergelijking en hoe groot is 4****4 of gaat dat te ver voor telbare hekmachten…?

^2. Recursie met k variabelen leidt niet buiten de klasse van de primitief recursieve functies, p.75 in Rozsa Péter "Recursive Functions" 1967, 1950.