Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

There is well-known Rado's "Busy Beaver" sequence — the maximal number of marks which a halting Turing machine with n states, 2 symbols (blank, mark) can produce onto an initially blank two-way infinite tape. It begins:

1, 4, 6, 13, ...

The sequence grows faster than any computable function and so is non-computable itself. Calculating the next (5th) term is widely believed to be a very difficult task (at least as difficult as solving the Collatz problem).

Let's consider a sequence of remainders of the "Busy Beaver" sequence elements modulo 2:

1, 0, 0, 1, ...

Is anything known about computability of this latter sequence?

share|improve this question
4  
It seems difficult to say much of anything about it. –  Joel David Hamkins Jul 22 '13 at 20:41
4  
Related –  Logan Maingi Jul 22 '13 at 21:05
    
@JoelDavidHamkins A very subjective question: Do you think computability of this sequence will likely always remain an open question? –  Vladimir Reshetnikov Jul 22 '13 at 23:33
2  
Vladimir, amazing new discoveries are made all the time, so I wouldn't venture an opinion on that... Meanwhile, I had just meant that I don't see any promising approach to settling the question positively or negatively. –  Joel David Hamkins Jul 22 '13 at 23:54
    
This question was discussed on m.se, math.stackexchange.com/questions/271834/… –  Gerry Myerson Jul 23 '13 at 9:22
add comment

1 Answer

I will not answer the question since I think it is not completely defined without completely specifying the machine model. In the following I explain why.

Note that the exact running time of a machine is not natural mathematically, it heavily depends on the particular model of the machine we use (that is why in complexity theory we get rid of such constants using asymptotic notations like $O$). Therefore, the question of computing the running time modulo some value is not natural either.

We can easily consider a machine model where all halting machines halt in even number of steps and another model where all halting machines halt in odd number of steps, and in both cases your question is trivially computable. Even more artificially, we can define a machine model where a halting machine with size $k$ halts in even number of steps iff a particular machine halts in $k$ steps (which would make the problem uncomputable). These are all valid models of computation though artificial ones.

The function is trivially computable in one model of computation, and uncomputable in another model of computation. That tells us that the question is not a natural one. Note that this is not the case regarding $BB$, it is uncomputable in all acceptable models of computation (having same computational power as Turing machines). The answer doesn't depend on the particular model of computation we use, the numbers will be different, but the question about computability has the same answer in all of them.

Your question about $BB(k) \mod 2$ for a particular fixed completely specified model of computation is well defined, but IMHO it is not a very interesting one: it is too much dependent on the particularities of the machine model. Unless you have some reasonable restrictions on the models such that the answer will be the same on all such models the question would not be very interesting IMHO.

In a sense, this is similar to asking if a particular Diophantine equation has any integer answers without explaining why that particular equation is of any interest. Here is the same, from mathematical perspective, the answer to the question is not a natural one and too much dependent on the particular encoding of the machines and I don't see any way of getting around this dependence. (Also from practical perspective, I also don't see any use for computability of this function.)

share|improve this answer
    
This is pretty much a copy-paste of the answer you posted and deleted on m.se, right? –  Gerry Myerson Jul 23 '13 at 9:23
    
@Gerry, I deleted that answer on Feb. 6 when I noticed my argument about uncomputability of the uniform version independent of the encoding does not work. The rest was fine but I forgot to repost that part. When I clicked on the link to the question on Mathematics I saw my deleted answer there, so I removed that part from the answer and posted the part that was fine. I don't know if it is better to post this on MSE or MO. If people think it is more appropriate to post it there I can delete this one and undelete the other one. –  Kaveh Jul 23 '13 at 9:27
add comment

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.