<ol>
<li><p>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.</p></li>
<li><p>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.</p></li>
<li><p>So is this question invariant under change of representation of computable functions? The answer I think is no.</p></li>
</ol>

<p>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. </p>

<p>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.</p>

CC BY-SA 3.0
2017-05-06T14:55:03.813Z
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.
Geoffrey Irving
CC BY-SA 3.0
2017-05-06T14:56:28.210Z
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.
Geoffrey Irving
CC BY-SA 3.0
2017-05-06T15:44:02.413Z
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.
Kaveh
CC BY-SA 3.0
2017-05-06T15:55:19.100Z
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.
Kaveh
CC BY-SA 3.0
2017-05-06T16:28:44.243Z
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.
Geoffrey Irving
CC BY-SA 3.0
2017-05-06T17:40:33.290Z
It is not similar because those always halting machines models are not Turing complete, you cannot built computability theory using them. I don't think the models I have above are "degenerate" (whatever that means), there is a theorem that says computability theory results are independent of machine model we pick as long as the model satisfies some basic conditions and the models I mention in my answer satisfy those conditions.
Kaveh
CC BY-SA 3.0
2017-05-06T11:42:37.340Z
2017-05-06T11:42:37.340Z
Kaveh
<p>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)$. </p>

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

<p>$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?</p>

CC BY-SA 3.0
2017-05-02T18:40:17.313Z
Suppose one of the n states is not reachable.
mic
CC BY-SA 3.0
2017-05-02T20:33:25.377Z
@mic: I don't think that's relevant.  $BB(n-1) = BB_2(n)$ seems highly unlikely.
Geoffrey Irving
CC BY-SA 3.0
2017-05-02T22:44:32.083Z
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)$.
Lance Fortnow
CC BY-SA 3.0
2017-05-03T01:57:32.960Z
That's why I let $HT(n)$ be the *set* of halting times, so that the gap is nonzero by construction.
Geoffrey Irving
CC BY-SA 3.0
2017-05-04T02:23:05.737Z
Is it even possible to prove the gap isn't eventually 1?
Geoffrey Irving
CC BY-SA 3.0
2017-05-05T02:08:07.137Z
Depends on the encoding.

 Consider an encoding 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.

Consider another encoding 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 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 the is such f.
Kaveh
CC BY-SA 3.0
2017-05-05T03:10:11.033Z
I don't think those are reasonable definitions of "the set of $n$-state Turing machines", but if it helps let's use the definition on Wikipedia: https://en.wikipedia.org/wiki/Turing_machine.  Note that encoding is the wrong word, since $n$ counts states not bits.
Geoffrey Irving
CC BY-SA 4.0
2022-06-03T23:07:50.633Z
Is it even possible to prove the gap is not 0? Maybe it is possible that there can be multiple machines at tie in busy beaver contest.
rus9384
CC BY-SA 4.0
2022-06-04T14:36:13.760Z
It’s nonzero by definition, as it’s about the second largest number, not the halting time of the second fastest machine.
Geoffrey Irving
<computability>
Gap between $BB(n)$ and "second largest" $BB(n)$
Geoffrey Irving
# Gap between $BB(n)$ and "second largest" $BB(n)$

(Asked by: username_0 on 2017-04-30)

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?

**Tags:** computability

> **Comments:**
> **username_1**: Suppose one of the n states is not reachable.  
> **username_0**: @username_1: I don't think that's relevant.  $BB(n-1) = BB_2(n)$ seems highly unlikely.  
> **username_2**: 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)$.  
> **username_0**: That's why I let $HT(n)$ be the *set* of halting times, so that the gap is nonzero by construction.  
> **username_0**: Is it even possible to prove the gap isn't eventually 1?  
> **username_3**: Depends on the encoding.   Consider an encoding 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.  Consider another encoding 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 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 the is such f.  
> **username_0**: I don't think those are reasonable definitions of "the set of $n$-state Turing machines", but if it helps let's use the definition on Wikipedia: https://en.wikipedia.org/wiki/Turing_machine.  Note that encoding is the wrong word, since $n$ counts states not bits.  
> **username_4**: Is it even possible to prove the gap is not 0? Maybe it is possible that there can be multiple machines at tie in busy beaver contest.  
> **username_0**: It’s nonzero by definition, as it’s about the second largest number, not the halting time of the second fastest machine.  

---

## 1 answers

### Answer by username_3 on 2017-05-06. Score: -1

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.

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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.  
> **username_3**: 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.  
> **username_3**: 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.  
> **username_0**: 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.  
> **username_3**: It is not similar because those always halting machines models are not Turing complete, you cannot built computability theory using them. I don't think the models I have above are "degenerate" (whatever that means), there is a theorem that says computability theory results are independent of machine model we pick as long as the model satisfies some basic conditions and the models I mention in my answer satisfy those conditions.  

---

