Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The busy beaver function $\text{BB}(n)$ describes the maximum number of steps that an $n$-state Turing machine can execute before it halts (assuming it halts at all). It is not a computable function because computing it allows you to solve the halting problem.

Are functions like $\text{BB}(n) \bmod 2$, or more generally $\text{BB}(n) \bmod m$ for a modulus $m$, computable? Computing these functions doesn't solve the halting problem, so the above argument doesn't apply.

share|cite|improve this question
11  
This seems like it might well depend sensitively on the details of your machine setup. – Chris Eagle Jan 7 '13 at 0:01
10  
Some discussion on this question: scottaaronson.com/blog/?p=46 – Dan Brumleve Jan 7 '13 at 0:44
5  
A variation: can it be shown that $\text{BB}(n)$ is composite infinitely often? This version is seemingly less sensitive to the encoding. – Dan Brumleve Jan 7 '13 at 4:02
4  
1-D BB Turing machines are hard to visualize, so I made a page for 2-D Turing Machine BBs.. Once a 1-D Turing machine becomes predictable, it can be classified as halting or infinite. Thus, the point of predictability is the important point. This rarely happens elegantly. The champions tend to be machines that can be extended forward as they get into temporary predictable behaviors. – Ed Pegg Feb 26 '13 at 15:51
6  
Related. – Andrés E. Caicedo Jul 23 '13 at 16:21

There are two types of Busy Beaver: the original definition is the maximum number of $1$s that an $n$-state, 2 symbol Turing Machine can leave on a blank tape (consisting entirely of $0$s) after halting. The function for this is $\Sigma(n)$.

The other definition is maximum number of steps (or moves) that an $n$-state, 2 symbol Turing Machine can take on a blank tape before halting. The function for this is $\text{S}(n)$.

It actually doesn't matter which definition we're using because both are uncomputable. The machine that generates $\Sigma(n)$ and the machine that generates $\text{S}(n)$ don't have to be the same. For ease of discussion I will call them both $\text{BB}(n)$, as you have done.

It's easy to prove that the general case of $\text{BB}(n)\mod m$ is also uncomputable. For a sufficiently large $m$, $\text{BB}(n)\mod m = \text{BB}(n)$, therefore it's not computable either. It might be possible to calculate $\text{BB}(n)\mod m$ for certain small values up to a limit but we don't have enough information to say either way.

If $m=1$, then absolutely! Yes, it can be computed, but this is a boring answer that tells us nothing useful about $\text{BB}(n)$. I'm assuming you're interested in non-trivial cases.

share|cite|improve this answer
1  
Your argument doesn't have the right quantifiers in it. For fixed $m$, knowing $BB(n) \bmod m$ for all $n$ does not tell you $BB(n)$ for all $n$, so you can't use the fact that $BB(n)$ is uncomputable to conclude that $BB(n) \bmod m$ is uncomputable. In fact, 1) any finite sequence of $BB(n)$s is computable in a tautological sense, and 2) as pointed out in the comments, $BB(n) \bmod m$ is highly sensitive to details of encodings: you might choose dumb encodings with the property that it's always $0$, for example, and so trivially computable. – Qiaochu Yuan Feb 7 at 3:19
    
If $m$ is smaller than $BB(n)$, then this is true. However, there are an infinite number of values for $m$ larger than $BB(n)$. This holds true for all finite values of $n$. If you know all the values in advance it is trivial to produce a formula that works for all of them. $n^3-6.5n^2+15.5n-9\mod m$ works for any $m$ and all $\Sigma(n)$ up to 4. – CJ Dennis Feb 7 at 4:21
1  
Again, you're not using the right quantifiers. Since $BB(n)$ grows arbitrarily large, for fixed $m$ there will always be some $n_0$ such that $BB(n) > m$ for $n > n_0$. So for any fixed $m$, reducing $\bmod m$ necessarily causes you to lose information about the busy beaver numbers in such a way that you can't conclude that the sequence $BB(n) \bmod m$ is uncomputable from this argument. (Again, independently, your argument also can't work because it's possible to choose a dumb encoding relative to which $BB(n) \equiv 0 \bmod m$, in which case the sequence is trivially computable.) – Qiaochu Yuan Feb 7 at 4:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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