Till det tok som snurrar runt på internet adderar vi nu att om du tänker på Grahams tal, ett fantastiskt stort tal som dyker upp i den del av kombinatoriken som kallas Ramseyteori, så kollapsar din hjärna till ett svart hål. Det verkar komma från något skämt i en video från Numberphile. Jag får väl vara försiktig då :)
Om det här talet sägs ofta att det observerbara universum inte skulle räcka till för att skriva ut det i decimalform. Det är sant, men det fångar liksom inte hur stort Grahams tal är. Det är lite som att säga att Rubiks kub har över tre olika tillstånd.
Jag har ofta skrockat lite inombords åt uttrycket "astronomiskt stort tal" och tänkt "de skulle bara veta vilka tal som förekommer i andra sammanhang". Så här kommer ett förslag på klassificering av tal i storleksfamiljer ordnade efter olika vetenskaper.
1. Astronomiska tal. Det här är tal av typen hur många meter det går på ett ljusår. The scale of the universe, kan man säga. Animeringen här är hisnande, men det är ingen större svårighet att skriva ner ett tal med 50 eller 100 siffror med papper och penna.
2. Kryptologiska tal. Här har vi de tal som gör att vi kan skicka pengar och inloggningar säkert över internet. Kryptonycklar är slumpmässiga strängar av ettor och nollor som är så långa att det ska vara praktiskt omöjligt att gissa eller leta igenom för att hitta dem och knäcka krypteringen. Animeringen the scale of the universe sträcker sig över 62 tiopotenser. Ett kryptosystem med nyckellängd på 256 bitar har $2^{256}$, eller ungefär $10^{77}$, möjliga nycklar. System med offentlig nyckel (public key) måste ha kanske 8 eller 16 gånger längre nyckel. Nu blir det lite jobbigt att skriva för hand, men en sådan nyckel tar ändå bara upp en försvinnande liten del av ett datorminne. De kryptologiska talen är bara ett litet snäpp ovanför de astronomiska i min klassificering. Titta gärna på avsnitt 1.7 i boken Applied Cryptography av Bruce Schneier.
3. Fysikaliska tal. Här har vi tal som dyker upp i statistisk mekanik. Varför fryser vatten till is vid en viss temperatur? Varför kokar det vid en viss annan temperatur, och hur kan det ändå finnas vatten i luften fast det är kallare än så och vatten är tyngre än luft? Vad är det som händer när saker koagulerar, spricker, blir magnetiska och så vidare, och det där entropi, vad är det?
För att reda ut sådana saker behöver man resonera om tal som är större än de astronomiska och kryptologiska. Det handlar inte om antalet molekyler i luften i ett rum, utan om på hur många sätt de kan arrangeras, om vi till exempel klassificerar dem efter huruvida de befinner sig i eller utanför en kastrull på spisen. Typiskt rör det sig om sådant som två upphöjt till Avogadros tal. Nu kan vi inte längre hantera talen med en miniräknare eller med datorns flyttal. Fast vi skulle fortfarande kunna skriva ner dem i decimalform om vi omvandlade några planeter till papper! Och någon liten måne till gem för att hålla ordning.
4. Talteoretiska tal. I den del av talteorin som handlar om fördelningen av primtal, händer det ofta att man upphöjer till någonting ett par, tre, fyra gånger. Gauss och Riemann hade kommit på redan på 1800-talet att antalet primtal mindre än ett tal $x$, vilket brukar skrivas $\pi(x)$, approximeras väldigt bra av funktionen \[\mathrm{li}(x) = \int_0^x \frac1{\log t}\,dt.\] I den här integralen blir det lite tjafs kring $t=1$, men vi tolkar det som ett principalvärde, dvs kancellerar oändligheterna. Det såg till en början ut som om $\pi(x)$ alltid är mindre än $\mathrm{li}(x)$. Hur långt man än tittar i primtalstabellerna, verkar primtalen aldrig komma ikapp.
Men sedan bevisade Littlewood och Skewes att $\pi(x)$ och $\mathrm{li}(x)$ kommer att hoppa bock över varandra oändligt många gånger, och att första gången primtalen kommer ikapp den logaritmiska integralen är för något $x$ som är mindre än \[e^{e^{e^{79}}}.\]
Det här talet, $e$ upphöjt till $e$ upphöjt till $e$ upphöjt till 79, är redan långt förbi vad som kan skrivas ut i decimalform med alla atomer i det kända universum. Talet $e^{79}$ är ett astronomiskt stort tal, och när vi tar $e$ upphöjt till det talet, får vi ett tal som det krävs astronomiska resurser för att skriva ner i decimalform. Sedan ska vi alltså ta $e$ upphöjt till det talet.
5. Kombinatoriska tal. Här kommer Grahams tal och dess släktingar. Längst ner i det här skiktet ligger tornen. I stället för att som Skewes och Littlewood nöja oss med tre-fyra exponentieringar, bygger vi ett torn av en viss höjd, så här \[2^{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}.\] Om vi sätter höjden till exempelvis 10, är vi redan i en helt annan bollpark än talteoretikerna.
Här är ett problem där torn dyker upp: Tänk dig att du bor på en oändligt lång gata, där varje hus ska målas rött, grönt, eller blått. Det blir inte snyggt om två grannar väljer samma färg, så det vill vi undvika. Enkelt, du hör ju bara efter med dina två grannar hur de har tänkt måla, och vad de än säger, finns det åtminstone en färg kvar. Problemet är bara att de har sina andra grannar att tänka på, så de kanske kommer och frågar dig först. Vi antar att vi kan singla slant för att lösa upp situationer av typen "ok, vi tänker båda måla blått, så då får en av oss byta". Men informationen i grannarnas kommunikation hinner bara gå en ändlig sträcka, säg $n$ hus, på den vecka eller så man har på sig att välja färg. Då visar det sig att det inte går att garantera att alla grannar väljer olika! Som Alexander Holroyd berättade för oss på Chalmers förra våren, kommer det ungefär på ett ställe av $Tower(n)$ (ett torn av höjd $n$) att köra ihop sig och på grund av ändringar hit och dit i sista sekunden sluta med att två grannar målar sina hus i samma färg!
Grahams tal, som är ännu mycket större än till exempel $Tower$ av något talteoretiskt tal, handlar om i vilken dimension en viss variant av tic-tac-toe inte längre kan sluta oavgjort. Där får vi börja med att skapa torn vars höjd bestäms av tidigare torn, och så vidare, och då har vi "ändå inte sett någonting än" som de säger på engelska. Jag får hänvisa till Numberphile igen.
6. Datavetenskapliga tal. Alla tal vi har diskuterat hittills har varit möjliga att beräkna i princip. Det vore en enkel sak att skriva ett datorprogram som, om det kördes på en idealisk dator med oändlig hastighet och oändligt mycket minne, skulle spotta ut $Tower(1000)$ eller Grahams tal. Ett program för $Tower(1000)$ skulle kunna vara (i pseudokod):
\[N=1; \quad \mathrm{for} \,\, (k=1,\dots, 1000)\,\, \mathrm{do} \,\, N=2^N; \quad \mathrm{return}\, N.\] Det fick plats på en rad här. Och vi skulle kunna använda $Tower$ som en subrutin i ett något längre program för att beräkna de följande hisnande nivåerna upp till Grahams tal. Hela programmet skulle nog med bred marginal få plats på säg 50 rader om 20 tecken vardera, dvs det skulle ha färre än 1000 tecken om det skrevs i något vanligt programmeringsspråk. Låt oss nu definiera $f(N)$ som det största tal som ett sådant idealiskt datorprogram med högst $N$ tecken kan skriva ut. Då är $f(1000)$ minst lika med Grahams tal, och förmodligen ofattbart mycket större. Lägg märke till att programmet alltså måste stanna för att det ska räknas. Ett program som bara fortsätter att skriva ut siffror i oändlighet är inte en beskrivning av något tal, och räknas inte.
Med de datavetenskapliga talen passerar vi gränsen för vad som överhuvudtaget kan beräknas. Funktionen $f$ är en variant av det som kallas Busy Beaver, och är ett av standardexemplen på vad som i likhet med Alan Turings halting problem inte går att beräkna med någon algoritm.
Nu skulle man kunna tro att de datavetenskapliga talen ligger väldigt långt från de pussel och tankenötter som vanligt folk håller på med. Men även de är allestädes närvarande och dyker upp i just pussel. Wang tiles är fyrkantiga pusselbitar som ska läggas så att färgerna matchar. För en given uppsättning är frågan om det går att täcka hela planet. Hur stor är den största kvadrat som kan byggas av någon uppsättning av $n$ stycken Wang tiles som inte kan täcka hela planet? Svaret är att det i allmänhet inte går att räkna ut överhuvudtaget! Det är en funktion av busy-beavertyp, vilket innebär att om vi ställer den frågan för till exempel $n=1000$ tiles, kommer svaret att vara större än de tal jag nyss kallade "kombinatoriska".
Jag och Urban Larsson har ett papper där vi visar att de datavetenskapligt stora talen lurar bakom barnspel med tändstickor.
Men det finns en vetenskap kvar på min lista, och de tal man kan stöta på där är så löjligt stora att vi ytterligare en gång får konstatera att vi inte hade sett någonting än.
7. Logiska tal. På samma sätt som programmeringens språk gjorde att vi kunde definiera $f(n)$ som det största tal som kan beräknas av ett $n$ tecken långt program, kan vi använda matematiska språk för att definiera det största tal som kan definieras med $n$ tecken.
Då måste vi konstruera ett språk som gör att vi kan definiera matematiska begrepp formellt, inuti språket. Sådana språk har konstruerats, och ett av dem, ZFC, har kommit att bli en standard för den här typen av resonemang, även om det inte mig veterligen finns någon som faktiskt använder ZFC på det sätt som programmeringsspråk används.
ZFC står för Zermelo-Fraenkels system utvidgat med the axiom of Choice, och det är i princip tillräckligt kraftfullt för att man ska kunna definiera begrepp som Turingmaskin. Det gör att vi med ett sådant språk formellt kan definiera funktionen $f$ ovan, trots att vi inte har något sätt att beräkna den. Vi kan sedan bland annat definiera en hel hierarki av olika varianter av Turingmaskiner, utökade med svarta lådor som beräknar lägre nivåers busy-beaverfunktioner. Så om vi definierar $N$ som det största tal som kan definieras i ZFC med högst en miljon tecken, får vi något som slår till och med de datavetenskapliga talen med hästlängder.
Scott Aaronson har en väldigt trevlig uppsats som bland annat förklarar detta i mer detalj, och nu ser jag att han har skrivit om detta på sin blogg ganska nyligen.
Men är det inte lite paradoxalt att vi kan prata om detta tal $N$ i en bloggpost med färre än en miljon tecken? Kan vi definiera ännu större tal genom att formalisera våra resonemang om ZFC?
Då hamnar vi i frågor om huruvida olika utvidgningar av ZFC är motsägelsefria, och snart är vi i vad Scott Aaronson kallar Gödels träsk. Så vi kan lika gärna avsluta med
Det största tal du kan tänka på plus ett, stjärnstopp stjärnstopp stjärnstopp!
Här är förresten en snygg affisch.
Uppdatering: Nu finns en Numberphile-video om denna Big Number Duel.
No comments:
Post a Comment