Hacker News new | ask | show | jobs
by spoonboy 5811 days ago
Just for fun, here's my shot: The number of steps required to compute the solution to the travelling salesman problem for each quark of every subset of every permutation of quarks in the universe in space-time.
4 comments

Busy Beaver grows grotesquely faster than that.

Think of it this way. Imagine your scenario, like you just laid out. Now write a program to actually find the number in question, including all input (in this case, some representation of the number you gave, which itself can be encoded as something less than the raw base 2 representation). Now, convert that program to the most efficient possible representation in the Turing Machine encoding in question, which for these sorts of problems are often surprisingly small.

Your problem fits into a small handful of states, a few tens tops, and relatively small "input" too (as encoded by the states in some manner). Therefore BB(a few tens) is at least that large. In fact, that's an unbelievable underestimation of BB(a few tens).

While we humans are thinking we're all clever stacking exponentials on exponentials, the Busy Beavers are off doing things we can't even conceive. Arrow notation and hyper arrow notation and every other such bit of notation are all very, very small functions, and therefore well covered by BB(very small); what concept or concepts does BB(50) exploit? Certainly nothing that would fit into English very comfortably.

I think this helps a human to grasp BB() at least a little; the cleverest, biggest numbers we've ever managed to express without the BB notation are usually in the form of functions quite easy to express with Turing Machines of not that many states. BB grows fast.

I'm not sure if quarks have "positions" in the exact sense of the word, so I don't think there's a metric you could apply here to get distances for which to solve TSP.

Suppose there was a metric between quarks. To be clear, are you saying: take all quarks in the universe. Take their powerset P. For each set S in P, create the complete graph K_{|S|} where edge lengths are distances. Let TSP(x, K_{|S|}) be the number of steps required to solve TSP. Sum TSP(K_{|S|}) for all S in P.

Let n be the number of quarks in the universe. The size of the powerset is 2^n. For each S in P, since TSP is solvable in exponential time, we'll upper bound the number of steps by 2^n. In other words, for each powerset, you're cost for solving TSP is at most 2^n. Therefore, the number of steps is at most 2^n * 2^n = 2^(2n), which is far smaller than say Ackermann(6, 6).

Touche.
That's just 2^10^83
I think that breaks the rules.

Here's something simple I came up with:

P(1) = 10

P(n+1) = 10^P(n)

Q(n) = P(n)^P(n)

Z(1) = Q(1)

Z(n+1) = Q(Q(n))

And then: Z(10^100)

In a somewhat restricted version of this contest some time ago the best entry was my:

B(b, c, 0) = 0

i < b => B(b, c, i + j * b) = i + B(b, c, j) * c

T(b, 0) = b * b

T(b, n+1) = T(T(b, n), B(b, T(b, n), n))

Z = T(2, T(2, T(2, 9)))

It is much, much larger than the number you just threw out. See http://bentilly.blogspot.com/2010/03/large-numbers.html for an explanation.