# Proving a language is not decideable using a reduction from Busy Beaver?

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.

• 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? – usul May 12 '14 at 19:13

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.

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