Matematisk funktion med snabbt växande komplexitet

Hej!

För många år sedan, när jag läste på högskolan kom jag i kontakt med en mattematisk formel, eller funktion, som genererade en talserie, men där komplexiteten steg otroligt mycket i varje steg. Jämför med exvis fibonacci-serien, men helt andra uträkningar per steg. Minns att man manuellt kunde räkna fram ungefär fjärde talet, medans dåtidens superdatorer kunde räkna upp till typ 7e talet under rimlig tid.

Någon som har en susning om vad jag svamlar om? Vad hette "funktionen"? Tror den såg riktigt enkel ut.

http://en.wikipedia.org/wiki/Ackermann_function ?

Tackar! Kan mycket väl vara den jag mins. Dock mins jag den som "endimensionell" men jag kan ha fel. Gissar även att det kan finnas många liknande.

Tack igen!

Det finns förstås andra funktioner/talföljder som också växer snabbt, t.ex. a(n) = n^(n^(n^...)), där vi har n st n.

a(1) = 1
a(2) = 2^2 = 4
a(3) = 3^(3^3) = 3^27 = 7625597484987
a(4) = 4^(4^(4^4)) = 4^(4^64) = 4^(3,4028236692093846346337460743177e+38) = ....

Tack, men det var liksom inte att talen växte snabbt. Utan att tiden det tar att räkna ut talen ökar dramatiskt...

Hur menar du? Förstår du inte att nästa tal i den talserien går att räkna ut på en millisekund med en modern dator, men att uppfatta dess storlek är omöjlig.

Vad menar du med tiden att räkna ut talen ökar dramatiskt? Det krävs inte längre 50000 transistorer för att räkna ut 14*60.

Och hur tror du att tiden att räkna ut a(n) varierar med n?

Det kanske är Ramseytal som TS far efter?

http://en.wikipedia.org/wiki/Ramsey%27s_theorem

Intressant citat: