1
$\begingroup$

I was given this function: $F(n)$ returns the smallest TM (measured in number of states) such that on input $\epsilon$, the TM makes at least $n$ steps before eventually halting ($n$ is a natural number). I was asked to prove that this function is uncomputable using a reduction from the Busy Beaver. I'm still new to reductions and after sitting on this problem for a while I've gotten nowhere. I'd appreciate any help/guidance.

$\endgroup$
  • $\begingroup$ The idea of the reduction is to design an algorithm that computes the Busy Beaver function, by letting this algorithm call $F(n)$. Does that help get things started? $\endgroup$ – usul May 12 '14 at 19:13
1
$\begingroup$

Hint: Why is the busy beaver function difficult (rather, impossible) to compute? Consider the following algorithm: given $n$, run all $n$-state Turing machines, and whenever one of them halts, update your estimate on the maximum number of steps. Eventually you will have found $BB(n)$, but you wouldn't know, since some of your machines are still running. Will any of them terminate, or have you discovered $BB(n)$? The function $F(n)$ given to you in the question could help in that respect.

$\endgroup$
1
$\begingroup$

Note that $F(n)$ is non-decreasing function, and that

$F(BB(n))\leq n$

and

$F(BB(n)+1)>n$.

That was my big hint. For the complete solution, keep reading:

Build a $TM$, $S$, such that on a given $n$:

Run on $k$ from $1$ until $FF(k)\leq n$ and $FF(k+1)>n$. Then return that $k$.

-- S computes $BB(n)$.

$\endgroup$

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.