Reading this question "Natural RE undecidable problems but not Turing-complete" the following language came to my mind:

If $\Sigma(\cdot)$ is the busy beaver function (maximum attainable score among all halting 2-symbol n-state Turing machines of the above-described type, when started on a blank tape), define the function:

$$BB(\langle M \rangle) = \begin{cases} 1 & \text{$\langle M \rangle$ computes $\Sigma(\cdot)$}\\ 0 & \text{ otherwise} \end{cases}$$

Now define the language:

$L = \{ \langle M \rangle \; | \; \langle M \rangle \mbox{ halts and } BB(\langle M \rangle) = 0 \}$

Is $L$ recursively enumerable? (it should be r.e.: just simulate in parallel M with all TMs of the same length, and if $M$ halts and another $M'$ halts with a higher score add M to the enumeration).

Can we reduce the halting problem to $L$ ? (it seems that it cannot "capture" the halting of the busy beavers)

  • $\begingroup$ Is $|\langle M \rangle|$ the number of states? $\endgroup$ – Pål GD Feb 14 '13 at 18:47
  • $\begingroup$ When will you enumerate an $M$ that doesn't halt into $L$? $L$ can't be RE unless you enumerate all its members, and the procedure you've described only enumerates those that actually halt. $\endgroup$ – Steven Stadnicki Feb 14 '13 at 18:54
  • $\begingroup$ @PålGD: yes it is the number of states (halting state excluded) $\endgroup$ – Vor Feb 14 '13 at 19:17
  • $\begingroup$ @StevenStadnicki: I implictly assumed that $L$ contains only machines that halt ... perhaps I should clarify it in the question (let me think about it a little bit, perhaps it makes the question trivial). $\endgroup$ – Vor Feb 14 '13 at 19:20
  • 2
    $\begingroup$ @Kaveh It's not even a promise problem - you can simply define $L$ (as I believe the OP intended) as $L=\{\langle M\rangle | M\ \text{halts} \wedge BB(\langle M\rangle) = 0\}$. $\endgroup$ – Steven Stadnicki Feb 15 '13 at 6:08

I can't believe I didn't see this before — but yes, with an oracle for $L$ you can solve the halting problem. Obviously an oracle for $L$ gives us 'recursively' all non-Busy Beaver halting machines, so the question is 'can we figure out recursively in $L$ what the busy beavers are?'. Define $\Sigma_2(n)$ as the count function of the 'second busiest beaver'; that is, the second-highest attainable score among all halting two-symbol $n$-state TMs. The trick here is that there's a recursive function $f()$ such that $\Sigma(n)\leq\Sigma_2(f(n))$ (it's almost certain that $f(n)=n+1$ will do the trick, in fact, but that requires knowing that the BB function is strictly increasing) : given a machine $M$ of size $n$ that prints $\Sigma(M)$ 1s on its tape and then halts, there's some $c\gt 1$ and two machines each of size $\leq cn$ that print exactly $\Sigma(M)$ 1s and exactly $\Sigma(M)+1$ 1s, respectively, on their tapes — and this holds true for a 'busy beaver' machine $M$ even though we don't know $M$ explicitly. This means that having a bound on the 'second busy beaver' function for $f(n)$ gives a bound for the busy beaver function on $n$; but then having this, it's easy to solve the halting problem for a TM $M$ of size $n$ - if $\langle M\rangle\in L$ then say that $M$ halts; otherwise, find the longest-running machine of size $f(n)$ in $L$ (which can be done recursively since there are only finitely many machines of size $\leq f(n)$) and simulate $M$ for as many steps as that machine takes to halt. If $M$ doesn't halt within that time then $M$ can't possibly halt.

  • $\begingroup$ Thanks; inspired by your answer I found a quick (trivial )-: direct reduction from the halting problem in a separate answer. $\endgroup$ – Vor Feb 15 '13 at 10:50

This is a reworked version of Steven's good answer, with an explicit reduction from the Halting problem.

Given $\langle M \rangle, w$ build $M'$ that runs $M$ on $w$ and if it halts goes to the right of the tape, writes a 0 and halt.

If $M'$ halts, $BB(M')=0$ because there is an equivalent TM of the same size that writes a 1 and halts; so we can use the decider for $L$ to check if $M$ halts on $w$ ($M$ halts on $w$ iff $M' \in L$)

... it turned out that the question is indeed trivial :-)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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