This post is a result of me reaching Exercise 1.10 in Structure and Interpretation of Computer Programs (SICP) and finding out that GitHub released support for mathemtical expressions on Markdown. There will probably be more posts on SICP exercises as I progress through the book.

Scheme Primer

Some familiarity with Scheme syntax is needed to understand this post. The opening pages of SICP gives us a suitable way to do this by stating that,

when we describe a language, we should pay particular attention to the means that the language provides for combining simple ideas to form more complex ideas.

So we will do just that. This idea can be limited to three mechanisms:

  • primitive expressions, which represent the simplest entities the language is concerned with,
  • means of combination, by which compound elements are built from simpler ones, and
  • means of abstraction, by which compound elements can be named and manipulated as units.

Primitive expressions in Scheme are nothing you wouldn’t find in any other language: integers, strings, booleans and floats. You can assign names to these values using define,

(define radius 3.5)
> radius
3.5

combinations of these expressions with primitive procedures are created using prefix notation,

> (* 25 4 12)
1200

> (+ 2.7 10)
12.7

> (/ 10 5)
2

and such operations can be nested to produce compound operations.

> (+ (* 3 5) (- 10 6))
19

Functions, called procedures in Scheme, are an abstraction technique by which such compound operations can be named and called.

(define (square x) (* x x))

> (square 5)
25

(define (sum-of-squares x y)
  (+ (square x) (square y)))

> (sum-of-squares 3 4)
25

Control flow is described in Scheme using the cond or if procedures where the former allows for an n-ary case analysis.

(define (abs x)
  (cond 
    ((> x 0) x)
    ((= x 0) 0)
    ((< x 0) (- x))
  )
)

> (abs -3)
3

However, the notation above is not practised where the brackets are lined up to elucidate the syntax since this can lead to really long files to read as functions get bigger. We will write it instead as:

(define (abs x)
  (cond ((> x 0) x)
        ((= x 0) 0)
        ((< x 0) (- x))))

And that’s all we need to tackle Exercise 1.10 which is given below.

Exercise 1.10

Before we start writing down the math, let us add MathJax support to our static site generator Jekyll using Vincent Zhang’s tutorial. MathJax is JavaScript library that scans the page for mathematical markup, and typesets the mathematical information accordingly. All we need to do is add the public CDN <script> tags to our base head.html. Note that the resource identifier should use HTTPS in the <script> tag.


Exercise 1.10 (SICP; page 47)


We will use the substitution model of evaluation to expand $ (A \ x \ y) $ at the given parameters.

(A 1 10)

(A 0 (A 1 9))
(A 0 (A 0 (A 1 8)))
(A 0 (A 0 (A 0 (A 1 7))))
(A 0 (A 0 (A 0 (A 0 (A 1 6)))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))
(A 0 (A 0 (A 0 (A 0 (A 0 32)))))
(A 0 (A 0 (A 0 (A 0 64))))
(A 0 (A 0 (A 0 128)))
(A 0 (A 0 256))
(A 0 512)
1024

We observe that the multiplications operations, which reduce the chain of function compositions to our answer, is deferred and the max length of this chain can be pre-determined using the parameters (input size). Such a function is called a primitive recursive function. Computability theorists care about this quality of functions.

We also observe from the behaviour of this function instance that Ackermann functions of the form $(A \ 1 \ n)$ can be represented using the closed-form expression $2^n$. Thereby, we now know $ g(n) $ as well. The proof for this is straightforward using induction - we will skip writing that.

(A 2 4)

(A 1 (A 2 3))
(A 1 (A 1 (A 2 2)))
(A 1 (A 1 (A 1 (A 2 1))))
(A 1 (A 1 (A 1 2)))

We could stop here and use $g(n)$ to write this expression as $ g(g(g(2))) $. Looking at the number of compositions of $g(n)$ should give you a clue about finding a closed-form for $h(n)$ but let us continue.

(A 1 (A 1 (A 0 (A 1 1))))
(A 1 (A 1 (A 0 2)))
(A 1 (A 1 4))
(A 1 (A 0 (A 1 3)))
(A 1 (A 0 (A 0 (A 1 2))))
(A 1 (A 0 (A 0 (A 0 (A 1 1)))))
(A 1 (A 0 (A 0 (A 0 2))))
(A 1 (A 0 (A 0 4)))
(A 1 (A 0 8))
(A 1 16)

We can stop here and use the first subsection to get our answer.

\[\begin{align} 2^{16} = 65536 \hspace{50cm} \end{align}\]

Note also that the max size of the deferred operation chain (16) is not readily apparent from our input size. We are no longer dealing with primitive recursive functions.

(A 3 3)

(A 2 (A 3 2))
(A 2 (A 2 (A 3 1)))
(A 2 (A 2 2))
(A 2 (A 1 (A 2 1)))
(A 2 (A 1 2))
(A 2 (A 0 (A 1 1)))
(A 2 (A 0 2))
(A 2 4)

We can stop there.

For the second half of the question, we already know that $g(n) = 2^n$ for $n>0$ and $f(n) = 2n$ for $n>0$ is obvious. We solve for $h(n)$.

Note that we’re now writing Scheme notation using TeX typesetting. Recall that $(A \ x \ y)$ means initiating the procedure A with arguments x and y.

\[\begin{aligned} h(n) &= (A \ 2 \ n) \\ &= (A \ 1 \ (A \ 2 \ (n-1))) \\ &= (A \ 1 \ (A \ 1 \ (A \ 2 \ (n-2)))) \\ &= \underbrace{(A \ 1 \ (A \ 1 \ \ldots \ldots}_{k \text{ times}} (A \ 2 \ (n-k)) \ldots \ldots)) \\ &= (A \ 1 \ (A \ 1 \ \ldots (A \ 2 \ 1) \ldots )) \ \ \text{for} \ \ k = n - 1 \\ &= \underbrace{(A \ 1 \ (A \ 1 \ \ldots}_{n-1 \text{ times}} (2) \ldots )) \\ \end{aligned}\]

By representing $k$ function compositions of $g(x)$ using $\ g^k(x)$, we have all three functions in mathematical notation, for $n>0$,

\[\begin{aligned} A(0,n) &= f(n) = 2n \\ A(1,n) &= g(n) = 2^n \\ A(2,n) &= h(n) = g^{n-1}(2) = \underbrace{2^{2^{2^{⋰^{2}}}}}_{n \text{ times}} \end{aligned}\]

The process of repeatedly exponentiating an integer to build a power tower like above is called tetration. You can guess this will lead to really large numbers quickly. Consider $A(2, 5)$ and $A(2,6)$:

\[\begin{aligned} A(2,5) &= g^4(2) = 2^{2^{2^{2^{2}}}} = 2^{65536} \thickapprox 2.003 \times 10^{19728} \\ A(2,6) &= g^5(2) = 2^{2^{65536}} \thickapprox 10^{10^{19727}} \end{aligned}\]
Click the triangle to see what the first number looks like 2^65,536 = 2003529930406846464979072351560255750447825475569751419265016973710894059556311453089506130880933 34810103823434290726318182294938211881266886950636476154702916504187191635158796634721944293092798 20843091048559905701593189596395248633723672030029169695921561087649488892540908059114570376752085 00206671563702366126359747144807111774815880914135742720967190151836282560618091458852699826141425 03012339110827360384376787644904320596037912449090570756031403507616256247603186379312648470374378 29549756137709816046144133086921181024859591523801953310302921628001605686701056516467505680387415 29463842244845292537361442533614373729088303794601274724958414864915930647252015155693922628180691 65079638106413227530726714399815850881129262890113423778270556742108007006528396332215507783121428 85516755540733451072131124273995629827197691500548839052238043570458481979563931578535100189920000 24141963706813559840464039472194016069517690156119726982337890017641517190051133466306898140219383 48143542638730653955296969138802415816185956110064036211979610185953480278716720012260464249238511 13934004643516238675670787452594646709038865477434832178970127644555294090920219595857516229733335 76159552394885297579954028471943529913543763705986928913757153740001986394332464890052543106629669 16524341917469138963247656028941519977547770313806478134230959619096065459130089018888758808473362 59560654448885014473357060588170901621084997145295683440619796905654698136311620535793697914032363 28496233046421066136200220175787851857409162050489711781820400187282939943446186224328009837323764 93181478984811945271300744022076568091037620399920349202390662626449190916798546151577883906039772 07592793788522412943010174580868622633692847258514030396155585643303854506886522131148136384083847 78263790459607186876728509763471271988890680478243230394718650525660978150729861141430305816927924 97140916105941718535227588750447759221830115878070197553572224140001954810200566177358978149953232 52085897534635470077866904064290167638081617405504051176700936732028045493390279924918673065399316 40720492238474815280619166900933805732120816350707634351669869625020969023162859350071874190579161 24153689751480826190484794657173660100589247665544584083833479054414481768425532720731558634934760 51374197795251903650321980201087647383686825310251833775339088614261848003740080822381040764688784 71647552945326947661700424461063311238021134588694532200116564076327023074292426051582811070387018 34532456763562595143003203743274078087905628366340696503084422585596703927186946115851379338647569 97485686700798239606043934788508616492603049450617434123658283521448067266768418070837548622114082 36579802961200027441324438432402331257403545019352428776430880232850855886089962774458164680857875 11580701474376386797695504999164399828435729041537814343884730348426190338884149403136613985425763 55771053355802066221855770600825512888933322264362819848386132395706761914096385338323743437588308 59233722284644287996245605476932428998432652677378373173288063210753211238680604674708428051166488 70908477029120816110491255559832236624486855665140268464120969498259056551921618810434122683899628 30716548685255369148502995396755039549383718534059000961874894739928804324963731657538036735867101 75783994818471798498246948060532081996066183434012476096639519778021441199752546704080608499344178 25628509272652370989865153946219300460736450792621297591769829389236701517099209153156781443979124 84757062378046000099182933213068805700465914583872080880168874458355579262584651247630871485663135 28934166117490617526671492672176128330845273936469244582892571388877839056300482483799839692029222 21548614590237347822268252163995744080172714414617955922617508388902007416992623830028228624928418 26712434057514241885699942723316069987129868827718206172144531425749440150661394631691976291815065 79745526236191224848063890033669074365989226349564114665503062965960199720636202603521917776740668 77746354937531889958786628212546979710206574723272137291814466665942187200347450894283091153518927 11142871083761592223802766053278233516615551493693757784666701457179719012271178127804502400263847 58788339396817962950690798817121690686929538248529830023476068454114178139110648560236549754227497 23100761513187002405391051091381784372179142252858743209852495787803468370333781842144401713868812 42499844186181292711985333153825673218704215306311977485352146709553346263366108646673322924098798 49256691109516143618601548909740241913509623043612196128165950518666022030715613684732364660868905 01426391390651506390819937885231836505989729912540447944342516677429965981184923315155527288327402 83526884424087528112832899806259126736995462473415433335001472314306127503903073971352520693381738 43322950701049061867539433130784798015655130384758155685236218010419650255596181934986315913233036 09646190599023611268119602344184336333459492763194610171665291382371718239429921627253846177606569 45422978770713831988170369645886898118632109769003557358846244648357062914530527571012788720279653 64479724025405448132748391794128826423835171949197209797145936887537198729130831738033911016128547 41537737771595172808411162759718638492422280237344192546999198367219213128703558530796694271341639 10338827543186136434901009431974090473310144762998617254244233556122374357158259333828049862438924 98222780715951762757847109475119033482241412025182688713728193104253478196128440176479531505057110 72297431456991522345164312184865757578652819756484350895838472292353455946452121583165775147129870 82259092926556388366511206819438369041162526687100445602437042006637090019411855571604720446436969 32850060046928140507119069261393993902735534545567470314903886022024639948260501762431969305640666 36662609020704888743889890749815286544438186291738290105182086993638266186830391527326458128678280 66013375000965933646251460917231803129303478774212346791184547913111098977946482169225056293999567 93483801699157439700537542134485874586856047286751065423341893839099110586465595113646061055156838 54121745980180713316361257307961116834386376766730735458349478978831633012924080083635682593915711 31309780305164417166825183465736759341980849589479409832925000863897785634946932124734261030627137 45077286156922596628573857905533240641849018451328284632709269753830867308409142247659474439973348 13081098639941737978965701068702673416196719659159958853783482298827012560584236558953969030647496 55841479813109971575420432563957760704851008815782914082507777385597901291294073094627859445058594 12273194812753225152324801503466519048228961406646890305102510916237770448486230229488966711380555 60795662073244937337402783676730020301161522700892184351565212137921574820685935692079021450227713 30999877294595969528170445821819560809658117027980626698912050615607423256868422713062950098644218 53470810407128917646906550836129916694778023822502789667843489199409657361704586786242554006942516 69397929262471452494540885842272615375526007190433632919637577750217600519580069384763578958687848 95368721228985578068265181927036320994801558744555751753127364714212955364940843855866152080121150 79075068553344489258693283859653013272046970694571546959353658571788894862333292465202735853188533 37094845540333656535698817258252891805663548836374379334841184558016833182767683464629199560551347 00391478768086403226296166415606675081537106467231084619642475374905537448053182260027102164009805 84497526023035640038083472053149941172965736785066421400842696497103241919182121213206939769143923 36837470922826773870813223668008692470349158684099115309831541206356612318750430546753698323082796 64574176208065931772656858416818379661061449634325441117069417002226578173583512598210807691019610 52229263879745049019254311900620561906577452416191913187533984049343976823310298465893318373015809 59252282920682086223033258528011926649631444131644277300323779227471233069641714994553226103547514 56312906688543454268697884477429817774937101176146516241836166802548152963353084908499430067636548 06102940094693750609845588558043970485914449584445079978497045583550685408745163316464118083123079 70438984919050658758642581073842242059119194167418249045270028826398305795005734171148703118714283 41844991534567029152801044851451760553069714417613685823841027876593246626899784183196203122624211 77391477208004883578333569204533935953254564897028558589735505751235129536540502842081022785248776 60357424636667314868027948605244578267362623085297826505711462484659591421027812278894144816399497 38818846227682448516220518170767221698632657016543169197426512300417573299044735376725368457927543 65412826553581858046840069367718605020070547247548400805530424951854495267247261347318174742180078 57469346544713603697588411802940803961674694628854067917213860122541950381970453841726800639882065 63287928395827085109199588394482977756471520261328710895261634177071516428994879535648545535531487 54978134009964854498635824847690590033116961303766127923464323129706628411307427046202032013368350 38542536031363676357521260470742531120923340283748294945310472741896928727557202761527226828337674 13934256526532830684699975970977500055608899326850250492128840682741398816315404564903507758716800 74055685724021758685439053228133770707415830756269628316955687424060527726485853050611356384851965 91896864959633556821697543762143077866593473045016482243296489127070989807667662567151726906205881 55496663825738292741820822789606844882229833948166709840390242835143068137672534601260072692629694 68672750794346190439996618979611928750519442356402644303271737341591281496056168353988188569484045 34231142461355992527233006488162746672352375123431189344211888508507935816384899448754475633168921 38696755743027379537852625423290248810471819390372206668947022042588368958409399984535609488699468 33852579675161882159410981624918741813364726965123980677561947912557957446471427868624053750576104 20426714936608498023827468057598259133100691994190465190653117190892607794911921794640735512963386 45230356733455880333131970803654571847915504326548995597058628882868666066180218822486021449999731 22164138170653480175510438406624412822803616648904257377640956326482825258407669045608439490325290 52633753231650908768133661424239830953080654966187938194912003391948949406513239881664208008839555 49422370967348400726427057011650890751961553701862647974563811878561754571134004738107627630149533 09735174180655479112660938034311378532532883533352024934365979129341284854970946826329075830193072 66533778255931433111096384805394085928398890779621047984791968687653998747709591278872747587443980 67798249682782722009264499445593804146087706419418104407582698056880389496546165879839046605876453 41810289907194293021774519976104495043196841503455514044820928933378657363052830619990077748726922 99860827905317169187657886090894181705799340489021844155979109267686279659758395248392673488363474 56516870161662406424242412289611180106156823425393921800524834547237792199112285959141918774917938 23340010078128326506710281781396029120914720100947878752551263372884222353869490067927664511634758 10119387531965724212147603828477477457170457861041738574791130190858387789015233434301300528279703 85803598151829296003056826120919509437373254541710563838870475289505639610298436413609356416325894 08137981511693338619797339821670761004607980096016024823096943043806956620123213650140549586250615 28258803302290838581247846931572032323360189946943764772672187937682643182838260356452069946863021 60488745284243635935586223335062359450028905585816112753417837504559361261308526408280512138731774 90200249552738734585956405160830583053770732533971552620444705429573538361113677523169972740292941 67420442324811387507563131907827218886405337469421384216992886294047963530515056078812636620649723 12575790195988730411956262273437289005165611110941117452779654827904712505819990774980638215593768 85546498822938985408291325129076478386322494781016753491693489288104203015610283386143827378160946 34133538357834076531432141715065587754782025245478065730134227747061674424196895261316427410469547 46214837562882997718041867850845469656191509086958742511844358373065909514609804512474094113738999 27822492983367796011015387096129749705566301637307202750734759922943792393824427421186158236161317 88639255309511718842129850830723825972914414225157940388301135908333165185823496722125962181250705 81137594955250227472746743698871319266707692991990844671612287388584575846227265733307537355728239 51616964175198675012681745429323738294143824814377139861906716657572945807804820559511881687188075 21297183263644215533678775127476694079011705750981957508456356521738954417987507452385445520013357 20333323798950743939053129182122552598337909094636302021853538488548250628977156169638607123827717 25621313460549401770413581731931763370136332252819127547191443450920711848838366818174263342949611 87009150304916533946476371776643912079834749462739782217150209067019030246976215127852195614207080 64616313732365178539762920920255002889620129701413796400380557349492690735351459612086747965477336 92958773628635660143767964038430796864138563447801328261284589184898528048048844180821639423974014 36290348166545811445436646003249061876303950235640204453074821024136689519664422133920075747912868 38051751506346625693919377402835120756662608298904918772878338521785227920457718469658552787904475 62192663992008409302075673925363735628390829817577902153202106409617373283598494066652141198183810 88451545977289516457213189779790749194101314836854463961690460703010759681893374121757598816512700 07612627891695104063158576375347874200702220510708912576123616580268068158584998526314658780866168 00733264676830206391697203064894405628195406190685242003053463156621891327309069687353181641094514 28803660599522024824888671155442910472192913424834643870536850864874909917881267056566538719104972 18200423714927401644609434598453925367061322106165330856620211889682340057526754861014769936887382 09584552211571923479686888160853631615862880150395949418529489227074410828207169303387818084936204 01825522227101098565344481720747075601924591559943107294957819787859057894005254012286751714251118 43564371840535630241812254732660933027103979680910649392727226830354104676325913552796838377050198 55234621222858410557119921731717969804339317707750755627056047831779844447637560254637033369247114 22081551997369137197516324130274871219986340454824852457011855334267526471597831073124566342980522 14554941562527240289153333543493412178620370072603152798707718724912344944771479095207347613854254 85311552773301030342476835865496093722324007154518129732692081058424090557725645803681462234493189 70813889714329983134761779967971245378231070373915147387869211918756670031932128189680332269659445 92862106074388274169194651622676325406650708810710303941788605648937698167341590259251946118236429 45652669372203155504700213598846292758012527715422016629954863130324912311029627923723899766416803 49714122652793190763632613681414551637665655983978848938173308266877990196288693229659737995193162 11872154552873941702436698855938887933167445333631195415184040882838151934212341228200309503133410 50704760159987985472529190665222479319715440331794836837373220821885773341623856441380700541913530 24594391350255453188645479625226025176292837433046510236105758351455073944333961021622967546141578 11271970017386114942795014112532806212547758105129720884652631580948066336876701473107335407177108 76615935856814098212967730759197382973441445256688770855324570888958320993823432102718224114763732 79135756861542125284965790333509315277692550584564401055219264450531207375628774499816364633283581 61403301758139673594273276904489203618803867549557518068900585329272014939235005258451467069826285 48257883267398735220457228239290207144822219885587102896991935873074277815159757620764023951243860 20203259659625021257834995771008562638611823381331850901468657706401067627861758377277289589274603 94039303372718738505369129571267150668966884938808851429436099620129667590792250822753138128498515 26902931700263136328942095797577959327635531162066753488651317323872438748063513314512644889967589 82881292548007642518658649024111112730135719718138160258317850693224400799865663537154408845486639 31817083957357807990597308390948818040609359591909074739609044101505163217496814121007657191774837 67355751000733616922386537429079457803200042337452807566153042929014495780629634138383551783599764 70885134900485697369796523869584599459559209070905895689145114141268450546211794502661175016692826 02509507707782119504326173832235624376017767993627960993689751913949650333585071554184364568526166 74243688920371037495328425927131610537834980740739158633817967658425258036737206469351248652238481 34166380806150570482905989069645193644001859712042572300731641000991698752426037736217776343062161 67448849308109299010095179745415642512048220867145868492551324442667771278637282113315362243010918 24391243380214046242223349153559516890816288487989988273630445372432174280215755777967021666317047 96972817248339284101564227450727177926939992974030807277039501358154514249404902653610582540937311 46531049433824843797186069372144446008267980024712294894057618538922034256083026970528766213773735 94394224114707074072902725461307358541745691419446487624357682397065703184168467540733466346293673 98362000404140071405427763248013274220268539369886978760700959004868465062677136307097982100655728 51013066010107806337433447730734786538817426812307437660666433127753564665786037151929227684404582 73283243808212841218776132042460464900801054731426749260826922155637405486241717031027919996942645 62095561981645454766204502241144940474934983220680719135276798674781345820385957041346617793722853 49400316315995440936840895725334387029867178297703733328068017646395020900239419314991150091052768 21119510999063166150311585582835582607179410052528583611369961303442790173811787412061288182062023 26384986151565645123004779296756361834576810504334176954306753804111392855379252924134733948105053 20257087281863072911589113359420147618726642915640363719276023062838406504254417423354645499870553 18726887926424102147363698625463747159744354943443899730051742525110877357886390946812096673428152 58591992485764048805507132981429935991146323991911395992675257635900744657281019180584180734222773 47213977232182317717169164001088261125490933611867805757223910181861685491085008852722743742120865 24852372456248697662245384819298671129452945515497030585919307198497105414181636968976131126744027 00964866754593456705993699546450055892162804797636568613331656390739570327203438917541526750091501 11988568727088481955316769316812728921430313768180164454773675183534978579242764633541624336011259 60252109501612264110346083465648235597934274056868849224458745493776752120324703803035491157544831 29527589193989368087632768543876955769488142284431199859570072752139317683783177033913042306095899 91373146845690104220951619670705064202567338734461156552761759927271518776600102389447605397895169 45708802728736225121076224091810066700883474737605156285533943565843756271241244457651663064085939 50794755092046393224520253546363444479175566172596218719927918657549085785295001284022903506151493 73101070094461510116137124237614267225417320559592027821293257259471464172249773213163818453265552 79604270541871496236585252458648933254145062642337885651464670604298564781968461593663288954299780 72254226479040061601975197500746054515006029180663827149701611098795133663377137843441619405312144 52918551801365755586676150193730296919320761200092550650815832755084993407687972523699870235679310 26804136745718956641431852679054717169962990363015545645090044802789055701968328313630718997699153 16667920895876857229060091547291963638167359667395997571032601557192023734858052112811745861006515 25988838431145118948805521291457756991465775300413847171245779650481758563950728953375397558220877 77506072339445587895905719156736


The second number is 2 to the power of 2003529930……………5719156736 and is about that many digits long!

To put the second number into perspective, the number of Planck volumes (cubic Planck lengths) in the observable universe is around $4.65 \times 10^{185}$.

Let us see where bigger input values will take us! We are now done with our exercise and entering the territory of really large numbers…

Knuth’s up-arrows

Consider $A(3, n)$. We can derive a mathematical definition in the same way as we previously did.

\[\begin{aligned} (A \ 3 \ n) &= (A \ 2 \ (A \ 3 \ (n-1))) \\ &= \underbrace{(A \ 2 \ (A \ 2 \ \ldots \ldots}_{k \text{ times}} (A \ 3 \ (n-k)) \ldots \ldots)) \\ &= \underbrace{(A \ 2 \ (A \ 2 \ \ldots}_{n-1 \text{ times}} (2) \ldots )) \ \ \text{for} \ \ k = n - 1 \\ &= h^{n-1}(2) \end{aligned}\]

What does $h^{n-1}(2)$ look like? Recall that $n$ defines the number of 2’s in a power tower. By iterating $h(n)$ with itself, we are stacking power towers on top of each other $n$ times. For example, consider $A(3,4)$:

\[\begin{aligned} (A \ 3 \ 4) &= h^3(2) \\ &= h(h(h(2))) \\ &= h(h(\underbrace{2^{2^{⋰^{2}}}}_{2})) = h(\underbrace{2^{2^{⋰^{2}}}}_{\underbrace{2^{2^{⋰^{2}}}}_{2}}) = \underbrace{2^{2^{⋰^{2}}}}_{\underbrace{2^{2^{⋰^{2}}}}_{\underbrace{2^{2^{⋰^{2}}}}_{2}}} \end{aligned}\]

And breaking that down we have,

\[\begin{aligned} \underbrace{2^{2^{⋰^{2}}}}_{\underbrace{2^{2^{⋰^{2}}}}_{\underbrace{2^{2^{⋰^{2}}}}_{2}}} = \underbrace{2^{2^{⋰^{2}}}}_{\underbrace{2^{2^{⋰^{2}}}}_{2^2}} = \underbrace{2^{2^{⋰^{2}}}}_{2^{2^{2^2}}} = \underbrace{2^{2^{⋰^{2}}}}_{65536 \text{ times }} \end{aligned}\]

That is a power tower of 65,536 two’s! You can see how drastic and jumpy the growth rate is for these functions. We can try to represent $A(3,n)$ as follows,

\[\begin{aligned} A(3,n) = h^{n-1}(2) = \left. \underbrace{2^{2^{⋰^{2}}}}_{\underbrace{2^{2^{⋰^{2}}}}_{\underbrace{\vdots}_{2}}} \right\}n \ \ \ \ \text{for } n>0 \end{aligned}\]

Although this notation using braces helps elucidate tetration and pentation as we’ve just figured out, it can get cumbersome. We introduce Knuth’s up-arrow notation ($\uparrow$) specifically made for very large integers by Don Knuth in 1976.

  • the single up-arrow represents exponentiation
\[\begin{aligned} a \uparrow b = a^b = \underbrace{a \times a \times \cdots \times a}_{b \text{ times}} \end{aligned}\]
  • the double arrow represents tetration
\[\begin{aligned} a \uparrow \uparrow b = \underbrace{a^{a^{⋰^{a}}}}_{b \text{ times}} = \underbrace{a \uparrow (a \uparrow (\cdots \uparrow a))}_{b \text { times}} \end{aligned}\]
  • the triple arrow represents pentation
\[\begin{aligned} a \uparrow \uparrow \uparrow b = \underbrace{a \uparrow \uparrow (a \uparrow \uparrow (\cdots \uparrow \uparrow a))}_{b \text { times}} \end{aligned}\]

… and so on.

Definition 1. A general rule is that $m$ arrow ops expand into $m-1$ right-associative series of arrow ops.

\[\begin{aligned} a \uparrow^{m} b = \underbrace{a \uparrow^{m-1} (a \uparrow^{m-1} (\cdots \uparrow^{m-1} a))}_{b \text{ copies}} \end{aligned}\]

Using this rule, our new formula for $A(3,n)$ becomes amazingly simple and intuitive.

\[\begin{aligned} A(3,n) &= 2 \uparrow \uparrow \uparrow n \end{aligned}\]

For a quick sanity check, let us calculate $A(3,4)$ as before.

\[\begin{aligned} A(3,4) &= 2 \uparrow \uparrow \uparrow 4 \\ &= 2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow 2)) && \text{ (Definition 1)} \\ &= 2 \uparrow \uparrow (2 \uparrow \uparrow 4) \\ &= 2 \uparrow \uparrow (2 \uparrow (2 \uparrow (2 \uparrow 2))) && \text{ (Definition 1)} \\ &= 2 \uparrow \uparrow 65536 \\ &= \underbrace{2 \uparrow 2 \uparrow \cdots \uparrow 2}_{65536 \text{ copies of 2}} \end{aligned}\]

Just as before, we have a power tower of two’s with length 65536.

Can we now find a closed-form function for the general case $A(m, n)$ where $m,n∈ℕ$?

Closed-form of the Ackermann function

Yes, we can.

Let us first rewrite the recursive defintion of $A$ from Ex.1.10 (which we will denote now by $A^r$) using mathematical function notation.

\[A^r(m,n)= \begin{cases} 2n&\text{if }m=0\\ 0&\text{if }m\ge1\text{ and }n=0\\ 2&\text{if }m\ge1\text{ and }n=1\\ A^r\big(m-1,A^r(m,n-1)\big)&\text{if }m\ge1\text{ and }n\ge2. \end{cases}\]

We can guess and conjecture from the previous sections the following claim.

Claim A closed-form formal definition of the Ackermann function can be written as

\[A(m, n) = \begin{cases} 2n&\text{if }m=0\\ 0&\text{if }m\ge1\text{ and }n=0\\ 2 \uparrow^m n&\text{ otherwise} \end{cases}\]

for all integers $m\geq 0, n\geq 0$ and $\uparrow^m$ represents $m$ up-arrow ops.

Generally speaking, to prove something like this, it’s natural for the structure of the induction to mirror the structure of the recursive definition (since in some ways, they are one and the same). So, for our function, we want an induction method based on the cases below. Note that $𝑃(𝑚,𝑛)≡𝐴(𝑚,𝑛)$.

  1. $∀n. P(0,n)$
  2. $∀m. P(1+m,0)$
  3. $∀m. P(1+m,1)$
  4. $∀m(∀n. P(m,n)) → ∀n. P(1+m,1+n) → P(1+m,2+n)$

The fourth case is not very obvious at first but it is justifiable. In order to solve $P(1+m,2+n)$, we need $A(1+m,2+n) = A(m, A(1+m,1+n))$. To rewrite the inner $A$, $P(1+m,1+n)$ is sufficient, and $∀k. P(m,k)$ to rewrite the outer $A$. These are the two premises required to reach the consequent.

Our claim isn’t too difficult to derive from two-dimensional lexicographic induction.

Theorem 1. (Lexicographic Induction) Let $S(m,n)$ denote a statement involving two variables, $m$ and $n$ that belong to the set $U⊆(ℕ,ℕ)$. Suppose

  • $S(0,n)$ is true for all $n = 0, 1, 2, 3,…$
  • if $S(m,n)$ is true for all $n$, then $S(m+1,n)$ is true for all $n$
    • $S(m+1,0)$ is true
    • if $S(m+1,n)$ is true, then $S(m+1,n+1)$ is true

Then, $S(m,n)$ is true for all positive numbers $m$ and $n$.

This theorem is illustrated using the tables below. Each green cell in the tables represents pairs of $(m,n) \in U$ for which $S(m,n)$ holds.

First, we have the base case $∀n. S(0,n)$.


$∀n. S(0,n)$


We induct on $m$ where if a column $m$ is shaded green, then so is the column $m+1$.


$∀n. S(m,n) → S(m+1,n)$


But how do we prove the right side of this implication? We induct on $n$ where if some cell in column $m+1$ is shaded green, then so is the next one below it. If our base case is $(m+1,0)$, then the whole column is shaded green.


$S(m+1,n) → S(m+1,n+1)$


And thus by combining these nested inductions we have every column shaded green.


$∀m∀n. S(m,n)$


To prove $∀m∀n. P(m,n)$ where $m, n \geq 0$:

  • First induct on $𝑚$

    • Case 1 above covers the base case for this, when $𝑚=0$.

      \[\begin{aligned} A^r(0,n) = 2n = 2 \uparrow^0 n = 2 \times n = 2n && \text{ (first sub-case of A)} \end{aligned}\]

    • For the inductive step, we are given $∀𝑛.𝑃(𝑚,𝑛)$ and need to prove $∀𝑛.𝑃(1+𝑚,𝑛)$, do this by induction on $𝑛$

      • When $𝑛=0$, case 2 covers this.

        \[\begin{aligned} A^r(1+m,0) = 0 = 2 \uparrow^{1+m} 0 = 0 && \text{ (second sub-case of A)} \end{aligned}\]

      • When $𝑛=1$, case 3 covers this.

        \[\begin{aligned} A^r(1+m,1) = 2 = 2 \uparrow^{1+m} 1 = 2 && \text{ (Definition 1)} \end{aligned}\]

      • Since, we gave explicit cases for $0$ and $1$ on $n$, the inductive step will be of the form $Q(1+n) → Q(2+n)$. These statements need therefore be true, for $n\geq0$:

        \[\begin{aligned} P(1+m,0) \hspace{1.8cm} \\ P(1+m,1) → P(1+m,2) \\ P(1+m,2) → P(1+m,3) \\ ...\hspace{3cm} \\ P(1+m,1+n) → P(1+m,2+n) \end{aligned}\]

        We are given $𝑃(1+𝑚,1+𝑛)$ and need to prove $𝑃(1+𝑚,2+𝑛)$. This is case 4 above, since we already have that $∀𝑛.𝑃(𝑚,𝑛)$.

        \[\begin{aligned} A^r(1+m,2+n) &= A^r(m,A^r(1+m,1+n)) \\ &= 2 \uparrow^m (2 \uparrow^{m+1} n+1) && \text{ (induction hypotheses)} \\ &= 2 \uparrow^m \underbrace{(2 \uparrow^{m} 2 \uparrow^{m} 2 .. \uparrow^{m} 2)}_{n+1 \text{ copies}} && \text{(Definition 1)} \\ &= 2 \uparrow^{m+1} n+2 \\ &= \text{RHS of } A(1+m, 2+n) \end{aligned}\]

$\therefore$ By the principle of induction, our claim holds for all $m,n \geq 0$. $\hspace{5cm} \blacksquare$

And we’re done.

See also

Comments