Hvad er det største tal?

poster

På MIT afholdt man i 2007 en konkurrence om at navngive store tal. Nærmere bestemt var det en duel mellem logikerne Agustin Rayo og Adam Elga fra MIT om at kunne give en bestemt beskrivelse af så stort et naturligt tal som muligt. I konkurrencen ville det være usportsligt bare at tilføje “plus 1” til modstanderens bud. Det ville også være usportsligt at komme med beskrivelser som f.eks. “det mindste tal, der er større end noget andet tal som hidtil er blevet beskrevet af noget menneske”; man måtte kun bruge sædvanlig matematisk notation, ikke egne sproglige primitiver.

Og vinderen var… Agustin Rayo. Hans bud var

Det mindste tal større end ethvert endeligt tal som kan beskrives af et udtryk i mængdeteori, som anvender én googol symboler eller færre

Denne beskrivelse kan formuleres i andenordens-logik, og på konkurrencesiden kan man se hvordan dét skal gøres (det kræver Gödel-nummerering!).

Ideen til konkurrencen kom fra en artikel Who Can Name the Bigger Number? af Scott Aronson, der er professor i datalogi, også på MIT. I denne artikel (som bestemt er værd at læse!) kommer Aronson ind på nogle meget store tal, nemlig de tal som den såkaldte busy beaver–funktion definerer. Faktisk angiver denne funktion nemlig en øvre grænse for hvor store tal vi kan beregne.

BB(n) er defineret til at være det største antal skridt som kan foretages af et program med n linjer inden det standser. Funktionen BB(n) er ikke beregnbar – for hvis den var, kunne vi nemt finde ud af om et program standser på et givet input. Vi skulle bare finde ud af hvor mange linjer programmet har og så simulere det i højst BB(n) — hvis programmet så stadig ikke er standset, standser det nemlig aldrig. Og der kan ikke være nogen beregnbar funktion f der for alle n opfylder at f(n) > BB(n). For var der et program, der beregnede en sådan f, ville dette program have m linjer for ét eller andet m, men da ville det højst kunne foretage BB(m) skridt — og bad man så det problem om at beregne f(m) ville det ikke kunne nå at skrive tallet f(m), da det kun ville have BB(m) skridt til rådighed!

Ideen med konkurrencen om at finde det største tal var at gøre studerende interesseret i teorien om beregnelighed (som jeg selv har undervist i engang) og i de filosofiske aspekter af dette område. Det er en rigtig god idé. Hvis der engang bliver lavet en lignende konkurrence på dansk jord, stiller jeg gerne op.

(Visited 184 times, 1 visits today)
Loading Facebook Comments ...

Skriv et svar