[Solved]: A variant of the busy beaver function

Problem Detail: 

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)

Asked By : Vor

Answered By : Steven Stadnicki

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9780

 Ask a Question

 Download Related Notes/Documents