26
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 5
    $\begingroup$ It seems difficult to say much of anything about it. $\endgroup$
    – Joel David Hamkins
    Commented Jul 22, 2013 at 20:41
  • 5
    $\begingroup$ Related $\endgroup$
    – Logan M
    Commented Jul 22, 2013 at 21:05
  • $\begingroup$ @JoelDavidHamkins A very subjective question: Do you think computability of this sequence will likely always remain an open question? $\endgroup$
    – Vladimir Reshetnikov
    Commented Jul 22, 2013 at 23:33
  • 5
    $\begingroup$ 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. $\endgroup$
    – Joel David Hamkins
    Commented Jul 22, 2013 at 23:54
  • $\begingroup$ This question was discussed on m.se, math.stackexchange.com/questions/271834/… $\endgroup$
    – Gerry Myerson
    Commented Jul 23, 2013 at 9:22

1 Answer 1

Reset to default
15
$\begingroup$

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.)

Improve this answer
$\endgroup$
7
  • $\begingroup$ This is pretty much a copy-paste of the answer you posted and deleted on m.se, right? $\endgroup$
    – Gerry Myerson
    Commented Jul 23, 2013 at 9:23
  • $\begingroup$ @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. $\endgroup$
    – Kaveh
    Commented Jul 23, 2013 at 9:27
  • $\begingroup$ I agree with the analogy to Diophantine equations: It was by people being curious about many particular Diophantine equations, and solving some of them, that a lot of theory got developed. The present question is similarly interesting, in that it is a question for which we don't yet have any applicable theories. Although you can certainly invent machine models for which this question is answerable one way or another with available theory, it seems unreasonable to inductively conclude that an answer to the original (hard) question would be unlikely to be accompanied by any interesting theory. $\endgroup$
    – Matt
    Commented Aug 20, 2014 at 22:34
  • $\begingroup$ @Matt, let me give a better analogy to explain the difference between the question about computability of BB mod 2 and the question about computability of BB from linear algebra: "is $e_1$ one of the basis vectors of a given subspace $S$ of $\Re^n$ (without specifying any particular basis for $S$)?" does not make sense. On the other hand, the number of basis vectors of $S$ makes sense even if we don't specify a basis for $S$. We can of course make the first question sensible by fixing a basis but then the question is not about the subspace but the particular basis. $\endgroup$
    – Kaveh
    Commented Aug 21, 2014 at 0:13
  • 1
    $\begingroup$ @Kaveh: I agree that the question depends on details of the TM model. I even agree that this dependence is critical to the answer but probably mathematically uninteresting. I disagree that a model has not been specified (implicitly) by the question -- the prominent link in the first line gives a model specification, and the question is clearly about the linked sequence. I think that an answer to the question as asked, which is hard to answer, is likely to be interesting, likely introducing new methods that can be widely applied to many models. $\endgroup$
    – Matt
    Commented Aug 21, 2014 at 7:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .