Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
This seems like it might well depend sensitively on the details of your machine setup. –  Chris Eagle Jan 7 '13 at 0:01
Some discussion on this question: scottaaronson.com/blog/?p=46 –  Dan Brumleve Jan 7 '13 at 0:44
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
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
Related. –  Andres Caicedo Jul 23 '13 at 16:21

Your Answer


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

Browse other questions tagged or ask your own question.