Grahams tal, Rayos tal och gränsen för kompressibilitet

Grahams tal, Rayos tal och gränsen för kompressibilitet

Det är frestande att föreställa sig mycket stora tal som en tävling i ren storlek. Först kommer exponenter, sedan exponenttorn, sedan Knuths pilar, sedan Grahams tal, och därefter något ännu större. Men den bilden är missvisande. Den antyder att alla dessa konstruktioner ligger i samma landskap, bara allt högre upp. I själva verket rör det sig om olika regimer. Vissa konstruktioner trappar upp operationer inom ett givet språk. Andra utgår från språket självt, dess uttryckskraft och dess gränser, och diagonaliserar sedan över det som kan definieras inom dessa gränser. Det är denna skillnad som visar sig vara avgörande.

Detta blir tydligt så snart man börjar tänka i termer av symbolbudget. Om man får använda högst ett visst antal symboler, är frågan inte längre bara vilket tal som är störst, utan hur mycket struktur som kan packas in i en begränsad formel. Därmed förskjuts uppmärksamheten från talen som sådana till språket som medium för kompression. Ett starkare språk är inte bara ett språk som kan skriva större tal. Det är ett språk som kan uttrycka mer informationsrik struktur inom samma längd.

Grahams tal illustrerar den första regimen. Dess betydelse ligger inte främst i att det är ett ofattbart stort tal. Det intressanta är snarare hur det uppstår. Vanlig exponentiering räcker snabbt inte till. Man inför därför en notation som kan komprimera beskrivningen av upprepad exponentiering. Knuths pilnotation börjar med den enkla regeln

\[ a \uparrow b = a^b \]

Med två pilar får man tetration,

\[ a \uparrow\uparrow b \]

och med tre pilar en ännu högre operation. Redan här har man lämnat det vanliga räknespråket bakom sig och börjat bygga ett nytt språk vars styrka ligger i att det kan uttrycka upprepningsmönster mycket effektivt. Grahams tal tar sedan detta ett steg längre. Där används inte bara många pilar; själva antalet pilar byggs upp rekursivt. Talet blir därmed en vittnesbörd inte bara om storlek, utan om hur långt man kan komma genom att låta notationen bära strukturen.

Men just denna typ av konstruktion visar också varför spelet inte kan stanna vid Grahams tal. Antag att $g(64)$ representerar Grahams tal eller något mycket nära det. Då kan man förstås skriva

\[ g(g(g(64))) \]

Men så snart man märker att detta bara är iteration av samma operation, blir det naturligt att införa en mer kompakt notation, till exempel

\[ g^n(64) \]

där $g^n$ betyder att funktionen $g$ itereras $n$ gånger. Då förändras genast skrivandets ekonomi. Det är inte längre effektivast att skriva ut många explicita $g$:n; i stället används symbolerna till att göra exponenten $n$ så kraftfull som möjligt. Och när detta väl är gjort, kan man i nästa steg införa en ny operator som komprimerar hela denna typ av iteration. Exemplet visar något allmänt: allt som är tillräckligt regelbundet kan kapslas in, och så snart det kapslas in frigörs budget för något större.

Här blir Rayos tal filosofiskt mer intressant än Grahams. Grahams tal visar hur långt man kan komma inom ett visst notationssystem. Rayos tal visar att ett på förhand fixerat språk kan göras till föremål för en diagonal konstruktion. Men här krävs en precisering. Rayos tal är inte definierat relativt ett godtyckligt språk. I den klassiska formuleringen används ett formellt förstaordningsspråk för mängdteori, och just detta bidrar till konstruktionens enorma styrka.

Den metateoretiska poäng som intresserar mig här är därför en liten generalisering av Rayos grundtanke, inte Rayos tal självt. Om $L$ är ett formellt språk, kan man i informell form definiera en språkrelativ funktion så här:

\[ \begin{aligned} R_L = 1 + \max\{\, n :\;& n \text{ kan definieras unikt i } L \\ & \text{med högst en googol} \\ & \text{symboler} \,\} \end{aligned} \]

Detta är alltså inte en definition av Rayos tal i strikt mening, utan en Rayo-liknande konstruktion relativt ett givet språk $L$. Poängen är att storleken på det största tal som kan definieras inom en fast symbolbudget beror på språkets uttryckskraft.

Men den poängen kan skärpas ytterligare. Det räcker inte att säga att olika språk når olika långt. Man måste också fråga hur ett uttryck nära maximum ser ut. Och här uppstår en kontraintuitiv observation: ett uttryck som verkligen ligger nära gränsen för vad språket tillåter kan inte innehålla långa exploaterbara regelbundenheter. Om det gjorde det, skulle just dessa regelbundenheter kunna komprimeras genom en ny definition eller en ny operator. Därmed skulle symboler frigöras, och dessa symboler skulle kunna investeras i ytterligare växande struktur. Samma argument kan sedan tillämpas på varje ny operator som införs.

Ett uttryck nära maximum måste därför motstå vidare komprimering. De tal som ligger närmast en Rayo-liknande gräns kommer därför inte främst till uttryck genom långa regelbundenheter. Där ett mönster kan komprimeras, finns det fortfarande outnyttjad budget. De största talen inom en given budget måste därför definieras genom formler där nästan varje symbol tillför ny struktur snarare än upprepar gammal struktur.

Här ligger också en användbar informationsteoretisk intuition. Shannon-entropi mäter, grovt talat, hur mycket ny information som i genomsnitt bärs av symbolerna i ett meddelande. En sträng med starkt upprepade eller lätt förutsägbara mönster har låg entropi; en sträng där nästa symbol är svårare att förutsäga har högre entropi. Översatt till vårt sammanhang betyder detta inte att ett optimalt Rayo-nära uttryck bokstavligen maximerar Shannon-entropi i strikt matematisk mening. Shannon-entropi är definierad för sannolikhetsfördelningar, inte för enskilda formler. Men som intuition är den träffande: varje tydligt regelbundet mönster signalerar lägre informationsdensitet, alltså kompressibilitet, alltså outnyttjad budget.

Det finns här också en begränsad parallell till Kolmogorov-komplexitet. Likheten ligger inte i att vi befinner oss inom den klassiska teorin för beräkningsbara språk, eftersom Rayos ursprungliga språk är mängdteorins språk och inte en teori om Turingberäkning. Tal nära Rayo-gränsen har därför inte hög Kolmogorov-komplexitet i någon bokstavlig mening. Parallellen ligger i frågans riktning. Kolmogorov-komplexitet frågar hur kort ett givet objekt kan beskrivas. En Rayo-liknande funktion frågar hur stort objekt som kan nås inom en given beskrivningslängd. De är inte identiska begrepp, men de belyser samma spänning mellan längd, struktur och kompressibilitet.

Detta betyder att frågan “vilket är det största talet?” är ännu mer missvisande än man först kunde tro. Den mer precisa frågan är inte bara i vilket språk, och med hur lång beskrivning? Man måste också fråga hur mycket oregelbunden struktur språket kan artikulera inom denna längd. Ett rikt språk är inte bara ett språk som låter oss uttrycka högre iterationer. Det är också ett språk som låter oss beskriva mer intrikat och mindre kompressibel struktur på ett kompakt sätt.

Ur detta perspektiv framstår Grahams tal och Rayos tal inte som två steg i samma sekvens, utan som två olika sätt att synliggöra språkets roll. Grahams tal visar hur ett rikt notationssystem kan producera enorma tal genom rekursiv upptrappning inom en given formell ram. Rayos tal, och dess språkrelativa släktingar, visar att ingen sådan ram är slutgiltig, eftersom själva språket kan göras till föremål för en diagonal konstruktion relativt en längdgräns.

Om man har två språk, $L$ och $L'$, där $L'$ inte bara är rikare utan också tillräckligt uttrycksfullt för att på ett kompakt sätt beskriva definitioner i $L$, deras längd och deras semantik, då är det rimligt att vänta sig att

\[ R_{L'} > R_L \]

Detta är inte trivialt. Det kräver att $L'$ verkligen kan tala om $L$ på ett tillräckligt effektivt sätt. Men när det kravet är uppfyllt ser man tydligt den metateoretiska poängen: det är inte bara talen som växer, utan språkens förmåga att organisera och komprimera växandet. Och därmed också deras förmåga att artikulera allt mer informationsrik struktur inom samma budget.

Här ligger också den filosofiska lärdomen. Man behöver inte säga att talen på något starkt sätt “skapas” av notationen. Det räcker att notera något mer återhållsamt men ändå viktigt: vilka tal som blir gripbara genom korta, eleganta och jämförbara beskrivningar beror i hög grad på språkets resurser. Men nära språkets övre gräns förändras också innebörden av elegans. Den formel som bäst utnyttjar symbolbudgeten är inte nödvändigtvis den mest symmetriska eller mest regelbundna, utan den där nästan inget återstår att komprimera.

Det är därför Grahams tal fortfarande fascinerar. Inte för att det skulle vara det största tänkbara talet, utan för att det så tydligt visar hur mycket matematisk styrka som kan ligga i ett notationssprång. Och det är därför Rayos tal är ännu mer avslöjande. Det visar att ingen sådan seger är slutlig. Varje gång ett språk fixeras, uppstår möjligheten att gå utanför det. Själva vandringen uppåt genom metaspråk har dock sina egna gränser och öppna frågor. Men redan innan man når dessa frågor har något viktigt blivit synligt: nära den yttersta gränsen för en given symbolbudget upphör storleken att vara en fråga om elegant iteration och blir i stället en fråga om hur mycket inkompressibel struktur ett språk kan bära.

Det finns alltså ingen sista triumf i detta spel, bara en allt skarpare förståelse av att de största talen inte främst handlar om storlek, utan om språkets makt.