Tetration(en.wikipedia.org)

28 pointsby billpgvor 16 Jahren11 comments

en.wikipedia.org

http://en.wikipedia.org/wiki/Tetration

3 comments

akshaymvor 16 Jahren

This is a fantastic article on "big numbers" (and discusses tetration):

http://www.scottaaronson.com/writings/bignumbers.html

(I think someone has posted it to HN before, which is why I am leaving it as a comment)

warfanglevor 16 Jahren

Definite upvote. That essay is insanely fascinating; I tend to re-read it every few months.

michael_dorfmanvor 16 Jahren

I like the article, too, but I'm always disappointed when it doesn't cover Knuth's up-arrow, which seems absurdly relevant.

ablealvor 16 Jahren

Thanks. Obviously http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation

Shorter read: http://www.daviddarling.info/encyclopedia/K/Knuths_up-arrow_... , which comes quickly to next step:

Three up-arrows together represent a still more vastly powerful operator, equivalent to hyper5 or pentation, or a power tower of power towers

tectonicvor 16 Jahren

So if humans can compute the first few Busy Beaver numbers, does that mean we're not Turing machines?

pmiller2vor 16 Jahren

Not at all. Just because a problem in general is uncomputable does not mean that certain specific instances can't be computed. For example, the halting problem is undecidable, but anyone can see that loop of the form

    while (1) { }

is an infinite loop. Undecidability and uncomputability apply only at the level of general problems, not specific instances.

tectonicvor 16 Jahren

Thanks :)

jacquesmvor 16 Jahren

Addition, multiplication and exponentiation all have pretty clear day to day applications.

Is there a laymans explanation for how you could apply this in an 'ordinary' setting, in other words is this from my non-mathematical background a useful construct or should I treat it as a curiosity?

I find it interesting that there is a simple order to the operations +, *, ^ and so on that apparently can be extended further than I was aware of, is there a limit to that?

How would a fifth element in that series be applied?

Edit: as to the last, it seems the series builds on the previous operation in the series to build the next, so possibly 'pentation' would be a series of tetrations?

2+4 = 6

2x4 = 2+2+2+2 = 8 (edit2: using an 'x' here because hn eats asterisks thinking you mean italics)

2^4 = 4x4x4x4 = 256

2^^4 = 2^(2^(2^2)) = 65536

2^^^4 = ...?

jonpvor 16 Jahren

This (http://en.wikipedia.org/wiki/Knuths_up-arrow_notation#Introd...) describes how it can be extended without limit. And there's are numerical examples at the end of that section demonstrating how. And this (http://en.wikipedia.org/wiki/Pentation) focusses specifically on the next step on "pentation".

I'm not aware of any "real-world" applications of tetration in the way that eg exponentials can describe certain physical or economic processes. But it does have some genuine uses in pure mathematics such as calculating the upper bound of some numbers. It's not just making big numbers for the sake of it.

jacquesmvor 16 Jahren

hehe, funny, I just caught on to that (see edit above).

It's pretty logical really, but I can't seem to come up with what it should work out to. But the notation, once you go from ^ for exponentiation to ^^ for tetration immediately suggests ^^^ for the next step. I feel pretty dumb now for not realizing right away that was what was intended. (edit: I suck at math, in case that wasn't clear yet...).

Thanks!

jonpvor 16 Jahren

Tetration is used to express Graham's number (http://en.wikipedia.org/wiki/Grahams_number) which appeared in the Guinness book of records as the largest number ever used in a serious mathematical proof.