13
$\begingroup$

If $HT(n)$ is the set of halting times of $n$-state Turing machines on a binary alphabet with empty initial tape, then $BB(n) = \max HT(n)$.

What can we say about the second largest number in $HT(n)$? Call this $BB_2(n)$.

$BB_2(n)$ is trivially uncomputable, since it lets one compute $BB(n)$: just wait for one more machine to halt. Naively, I would expect the gap $BB(n) - BB_2(n)$ to be "busy beaver-like", growing faster than any computable function. Is this provable?

$\endgroup$
  • $\begingroup$ Suppose one of the n states is not reachable. $\endgroup$ – mic May 2 '17 at 18:40
  • $\begingroup$ @mic: I don't think that's relevant. $BB(n-1) = BB_2(n)$ seems highly unlikely. $\endgroup$ – Geoffrey Irving May 2 '17 at 20:33
  • 1
    $\begingroup$ This will depend on the encoding. If you flip the accept/reject states, the number of states remains the same and so is the time to halt, which would make $BB(n)=BB_2(n)$. $\endgroup$ – Lance Fortnow May 2 '17 at 22:44
  • 6
    $\begingroup$ That's why I let $HT(n)$ be the set of halting times, so that the gap is nonzero by construction. $\endgroup$ – Geoffrey Irving May 3 '17 at 1:57
  • 1
    $\begingroup$ Is it even possible to prove the gap isn't eventually 1? $\endgroup$ – Geoffrey Irving May 4 '17 at 2:23
-1
$\begingroup$
  1. The number of states is just a notion of complexity of the description of computable functions in a model, you can pick any model of computation and any encoding of them as binary strings and then take the length as n and define BB(n) based on that and all the interesting results about BB(n) would still be true, there is boring special about TM model and number of states.

  2. There is nothing that prevents them from picking any modified model of TMs. Generally the questions which are not invariant under such changes of representation of TMs are not about computability or TMs but about the particular representation (like BB(n) mod 2, etc. ) and unless there is some particular reason for them being interesting they don't worth pursuing imho. They are nice puzzles but not of much value. l Note that "BB(n) is not computable" is invariant under change of representations of TMs.

  3. So is this question invariant under change of representation of computable functions? The answer I think is no.

i. Consider a representation where we have two special states 0 and 1 and either 0 is initial and just can transition to 1 or 0 is unreachable and 1 is initial. In this encoding the difference is 1.

ii. Consider another representation where we have a UTM plus a part that writes n bits on tape before transitioning to UTM. So the question becomes max f(x) - 2ndmax f(x) where maxes are over n bits strings and where f is an arbitrary computable function. We only need to find a computable function where this is not computable. I haven't thought about it much but my gut says there is such a computable function.

$\endgroup$
  • 2
    $\begingroup$ None of this is relevant, because I picked standard Turing machines as my notion of computation. I agree that there a few different common definitions (one or two sided tape, whether the tape starts out zero or some special empty symbol), but nothing like the preencoded UTMs you mention. $\endgroup$ – Geoffrey Irving May 6 '17 at 14:55
  • 1
    $\begingroup$ Using $n$ to count an entirely different encoding would be a different and much less interesting question, since as you say the encoding can be chosen to break the question. $\endgroup$ – Geoffrey Irving May 6 '17 at 14:56
  • $\begingroup$ Let me put it in a different way: why are you interested in the answer? It is a nice puzzles like many others about BB for particular representation of TMs but they do not reveal anything about computability and computation. The picking of the standard for representation of TM was an arbitrary action, one could have picked my first representation above and the answer to your question would have been 1. Just because it is called standard does not make it special among representations. $\endgroup$ – Kaveh May 6 '17 at 15:44
  • $\begingroup$ This is no different from asking if some arbitrarily chosen Diophantienne equation E has an integer solution. There are infinitely many such equations, without a reason why one is interested in E it is not very interesting question. When people ask questions like "computability of BB(n) mod 2" they think they are asking deep questions about computability whereas in reality it is more like asking for solubility of some arbitrarily chosen Diophantienne equation, it is just some of them look nicer to the eye. $\endgroup$ – Kaveh May 6 '17 at 15:55
  • 2
    $\begingroup$ I'm interested because I believe the answer is the same for all nondegerate encodings: it's unprovable, it's unprovable that it's unprovable, etc. But I don't know how to phrase this, so I picked one. The fact that it's trivial for specially chosen encodings is similar to the halting problem being solvable for halt-by-construction machines. $\endgroup$ – Geoffrey Irving May 6 '17 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.