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.
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.
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.
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.
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?
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.
You might be thinking of something else. Erdős was constantly remarking that he would offer some amount for some problem. I would guess there are hundreds of open problems with Erdős prizes attached -- some large, some small.
Yeah, but if anyone in the world was going to have solved multiple Erdös problems, it would be Terry Tao. And he's still quite young, so he may well solve more.
Fifteen? No list I am aware of has 15 -- Erdos' definitely had lots more, of the Millennium Prize problems there are six open (and there was seven), most of Hilbert's are down there are 3 or 10 open depending how you look, but definitely not 15 (and there were 23 or so).
What is the significance of studying this problem? I mean, say they prove the twin primes conjecture. What does that mean? Do we benefit like we would if the travelling salesman problem was solved?
Significance of a problem shouldn't be considered from the same point of view as pricing an asset, by face value.
Open problems concerning prime numbers can be considered as large floodgates, waiting to be opened. Their applicability is likely to be infinite. Pick up any subject, try to quantify some behavior, sooner or later, primes will make an appearance. In fact, you should really do this; read the first few chapters of an elementary number theory book, then try to represent your area of expertise in a way that involves primes.
Perhaps in a few decades, or centuries, by tracing a certain technological improvement back in time, we'll be able to place a $-value this work. You can already do this now, for other (probably all, if you can be bothered) areas of (previously abstruse) mathematics, for example Group Theory -> Spectroscopy -> Biomedical Spectroscopy, or Algebraic Topology -> Improvements in semiconductors.
This is a different but related problem: instead of trying to prove that there are arbitrarily large twin primes, they are trying to see how the maximum gap between primes grows with their size. I know that doesn't answer the applicability question, but I think the answer to that is "who knows?" Pure mathematicians tend to study these things for their own sake and then someone may or may not figure out something useful to do with it.
Think of it more like fundamental research. Maybe nobody could make immediate productive use of the discovery of (for example) radioactivity in the late 1800s, but it has a wide variety of uses today from energy production to medical imaging.
It's unlikely that proof of the twin prime conjecture would prove that fundamental, but the results are hard to predict in advance.
