7 ms·

I laughed out loud when I saw that formula--y = loglogloglog x is a nonsense function. For those of you who haven't thought about logs for a while, that functio

I laughed out loud when I saw that formula--y = loglogloglog x is a nonsense function. For those of you who haven't thought about logs for a while, that function is increasing (bigger x give bigger y), but it grows so slowly that y won't be larger than 1 until x is larger than 2.33 x 10^1656520.

rtkwe 12y ago
A lot of approximate conjecture equations are only really true for very large numbers.
prezjordan 12y ago
Is loglogloglog...log the only beast that can conquer Knuth's arrow notation? (x ↑↑↑↑...↑ n) Every time I watch videos about arrow notation or, more famously, Graham's number, my head explodes :) https://www.youtube.com/watch?v=GuigptwlVHo https://www.youtube.com/watch?v=GuigptwlVHo Big big numbers are really, really cool!
- anonetal 12y ago
  log*(x) = how many times you have to take a log before you get to 1, grows more slowly than any constant length sequence of logs, and also appears naturally in many theoretical algorithms (e.g., union-find). I suspect even that is not enough to tame Knuth's arrow notation though.
  - jordigh 12y ago
    Union-find's big-Oh is the inverse of the Ackermann function, which isn't quite the same as iterated logs...
    - charrison 12y ago
      Depends on how you derive it. I've seen derivations that end up with a log* term. Of course, inverse Ackermann is a tighter bound.
  - throwaway_yy2Di 12y ago
    log* doesn't beat Knuth arrows. See that log*(e ↑↑ n) = (n-1) log*(e) = n So log* is just the inverse of e ↑↑ n. That makes sense. Logarithm is the inverse of exponentiation. log* is iterated logartithm-ing, and (↑↑) is iterated exponentiation (aka tetration). (↑↑) builds up a stack of powers, and log* tells you how tall that stack is.
- delhanty 12y ago
  Here's another nice big number link: http://www.scottaaronson.com/writings/bignumbers.html http://www.scottaaronson.com/writings/bignumbers.html If the inverse of the Ackerman function grows more slowly than loglogloglog...log, and the inverse of BB(N) grows more slowly still, maybe that would be enough to conquer Knuth's arrow notation?
  - Laremere 12y ago
    BB(N) must grow faster than any computable function. BB isn't computable because computing it would involve solving the halting problem. Any function which could grow larger than BB would imply solving the halting problem, and therefore can't be computable. Basically, inverse BB would eat Knuth's arrow notation for breakfast, and start asking about second breakfast and elevenses.
- throwaway_yy2Di 12y ago
  See my other comment: log* only conquers the second level of Knuth arrows, e ↑↑ n. But you can easily generalize log* , in a way that mirrors the way Knuth arrows are constructed, and inverts them at any level. Say log*[1](n) = log(n) log*[k](n) = 0 if n <= 1 = 1 + log*[k](log*[k-1](n)) if n > 1 Then the k-th level is the inverse of the k-th level Knuth arrows, e ↑^k n -- that is, e ↑↑..↑ n, with k arrows.
antognini 12y ago
"log log log x goes to infinity with great dignity." -- Dan Shanks

rtkwe 12y ago

A lot of approximate conjecture equations are only really true for very large numbers.

prezjordan 12y ago

Is loglogloglog...log the only beast that can conquer Knuth's arrow notation? (x ↑↑↑↑...↑ n) Every time I watch videos about arrow notation or, more famously, Graham's number, my head explodes :) https://www.youtube.com/watch?v=GuigptwlVHo https://www.youtube.com/watch?v=GuigptwlVHo Big big numbers are really, really cool!

anonetal 12y ago
log*(x) = how many times you have to take a log before you get to 1, grows more slowly than any constant length sequence of logs, and also appears naturally in many theoretical algorithms (e.g., union-find). I suspect even that is not enough to tame Knuth's arrow notation though.
- jordigh 12y ago
  Union-find's big-Oh is the inverse of the Ackermann function, which isn't quite the same as iterated logs...
  - charrison 12y ago
    Depends on how you derive it. I've seen derivations that end up with a log* term. Of course, inverse Ackermann is a tighter bound.
- throwaway_yy2Di 12y ago
  log* doesn't beat Knuth arrows. See that log*(e ↑↑ n) = (n-1) log*(e) = n So log* is just the inverse of e ↑↑ n. That makes sense. Logarithm is the inverse of exponentiation. log* is iterated logartithm-ing, and (↑↑) is iterated exponentiation (aka tetration). (↑↑) builds up a stack of powers, and log* tells you how tall that stack is.
delhanty 12y ago
Here's another nice big number link: http://www.scottaaronson.com/writings/bignumbers.html http://www.scottaaronson.com/writings/bignumbers.html If the inverse of the Ackerman function grows more slowly than loglogloglog...log, and the inverse of BB(N) grows more slowly still, maybe that would be enough to conquer Knuth's arrow notation?
- Laremere 12y ago
  BB(N) must grow faster than any computable function. BB isn't computable because computing it would involve solving the halting problem. Any function which could grow larger than BB would imply solving the halting problem, and therefore can't be computable. Basically, inverse BB would eat Knuth's arrow notation for breakfast, and start asking about second breakfast and elevenses.
throwaway_yy2Di 12y ago
See my other comment: log* only conquers the second level of Knuth arrows, e ↑↑ n. But you can easily generalize log* , in a way that mirrors the way Knuth arrows are constructed, and inverts them at any level. Say log*[1](n) = log(n) log*[k](n) = 0 if n <= 1 = 1 + log*[k](log*[k-1](n)) if n > 1 Then the k-th level is the inverse of the k-th level Knuth arrows, e ↑^k n -- that is, e ↑↑..↑ n, with k arrows.

antognini 12y ago

"log log log x goes to infinity with great dignity." -- Dan Shanks