Tell me more ×
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.
up vote 15 down vote favorite
4

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
3  
This seems like it might well depend sensitively on the details of your machine setup. – Chris Eagle Jan 7 at 0:01
So I'm not sure what you mean by that. "Turing machine," as far as I'm aware, picks out a unique model of computation, and there's a unique thing I mean by "step" in this model of computation. – Qiaochu Yuan Jan 7 at 0:24
4  
Some discussion on this question: scottaaronson.com/blog/?p=46 – Dan Brumleve Jan 7 at 0:44
1  
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 at 4:02
1  
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 at 15:51
show 2 more comments

1 Answer

up vote -2 down vote

No, $\text{BB}(n) \bmod 2$ is not computable.

Even for $\text{S}(5)$, "there remain about 40 machines with non-regular behavior", according to Wikipedia's Busy Beaver page. For any particular n>4, there will be ornery machines. For $\text{S}(5)$, the true busy beaver might be the known 47,176,870 step machine, or it might be one of these 40 ornery machines. It's one of those 41 machines.

Some of ornery Turing machines show local regularity, but global non-regularity. For some of these, you can predict that if they do halt, it will on an even step, or on an odd step. You have multiple ornery Turing machines which do not effect with each other. For some of them whether they will halt is formally undecidable. It's like shooting a few trillion (HH,HT,TT,UU) coins into far space in random directions, and tracking which side up the last survivor will land. Even if an omniscient being told you the two last coins and the galaxies where they would land, solving the halting problem for you, you'd still have an unpredictable coin flip. Now increase the order of the machines -- the next step is much harder.

share|improve this answer
This is intuitively sensible but how close can we get to a rigorous proof? Certainly there are machines whose halting status is undecidable but how do we know there are not always an even number of them at any particular depth? – Dan Brumleve Jan 25 at 4:41
2  
I don't see where the first statement follows from any of the rest of it. Not knowing S(5) doesn't mean that we can't for instance say that 'the longest computational path on a 5-state halting turing machine (of this machine model) is of necessity odd'. It may well be possible to argue the point even without having details of any of the individual TMs or without knowing which is the halting machine. – Steven Stadnicki Jan 25 at 4:41
1  
Reverse the problem. For each $n$, run all of oeis.org/A052200 for $k$ steps until there is a machine where none halts on that step. Let $M(n)$ =lowest missing halting number of order $n$. This is computable in a finite number of steps, since the finite pool of machines must decrease at every step. $M(n)$ and it's modulus is unpredictable until someone calculates it, and that only deals with beginning behavior of nice machines. Our ability to deliberately design nasty machines rules out the possibility of predictability in the harder problem. – Ed Pegg Jan 25 at 16:10
3  
-1; this is not a proof. Please do not claim definitively that a mathematical statement is true on a mathematical forum without providing at least a sketch of a proof. – Qiaochu Yuan Jan 26 at 4:35

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.