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.
1
-
$\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$– usulCommented May 12, 2014 at 19:13
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
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.
answered May 12, 2014 at 19:36
$\begingroup$
$\endgroup$
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)$.
