Jtdylktuy

Obviously "Largest $n$ that $BB(n)$ isn't larger than the input" is not calculable, otherwise while(iBB(i)<n)i++ solves the busy beaver;

However, if we define inverse busy beaver as "$n$ that $BB(n)$ is the input; undefined behavior if no $n$ satisfies", the proof above no longer works.

In this case is it solvable?

However, if we define inverse busy beaver as "$n$ that $BB(n)$ is the input; undefined behavior if no $n$ satisfy"

It should be easy to see that this function can't be a partial computable function. Well the simple way to see it is suppose that some program $P$ computed this given partial function. But now we can easily construct a program that computes a total computable function $f:mathbb{N} rightarrow mathbb{N}$ such that $f(x) ge BB(x)$ for all $x in mathbb{N}$.

Here is how we compute $f$ on some given input $x$. If $x=0$, just return $BB(0)$ as output. If $x>0$, one can just simulate this program $P$ on all inputs (in a certain fixed manner). Now each time the program $P$ halts on some input, you record this input value. Let's denote this value as $t$. Now you just check the condition $t>f(x-1)$ every time. If this condition is true, then return the value $t$ as output. Otherwise just keep simulating the program $P$.

So the above argument shows that there is no partial recursive function $g$ such that $g(BB(n))=n$ for all $n in mathbb{N}$ and $g$ is undefined on all other inputs (ones that are not of the form $BB(n)$). It seems that the intended question was whether there is some partial recursive function $f:mathbb{N} rightarrow mathbb{N}$ which "extends" $g$ in the sense that $f(x)=g(x)$ whenever $g(x)$ is defined. Don't confuse this function $f$ with the one in the first part of the answer (this is intended to be a different function).

I think there should be such a function $f$. For example, we can define $f$ as follows: $(1)$ If there is no program (with blank/zero input of course) that halts exactly on the $n$-th step, then define $f(n)=uparrow$. $(2)$ Now Suppose there is a program that halts exactly on the $n$-th step. Now consider the program(s) of smallest length (it doesn't matter if there are two programs of smallest length) which halt on $n$-th step, and let's denote the length of such program(s) as $N$. We define $f(n)=N$.

It seems that if we choose the specifics (such as definition of time and length of a program), then we can drop $(1)$ in above definition. For example, "normally" we assume that, for all $n$, there is always some program of length $n$ that halts exactly on the $n$-th step, on blank input. In that case, we will have $f$ as total and we will get $f(n) leq n$ (for all $n$).

First, we can observe that the function $f$ extends $g$ because $f(x)=g(x)$ for all points where $g$ is defined. For example, consider the value $BB(n)$ (for an arbitrary $n$). Now, by definition, there is exists a program of length $n$ which halts exactly on this step (when given zero/blank input). Now under most reasonable definitions, I think, $BB$ should be a strictly increasing function. That means there is no program of length less than $n$ which halts exactly on this step (when given zero/blank input). If that was true then we would have $BB(m)=BB(n)$ for some $m<n$ (violating the strictly increasing condition). Hence the function $f$ extends $g$.

Finally, here is a (very) rough sketch for the partial computable function $f$. We can proceed in iterations. In the $i$-th iteration we simulate all programs of length $leq i$ up unitl $i$ steps (on zero/blank input of course). Now consider any value $x leq i$. If there is some program of length $i$ or less that halts on the $x$-th step, then we can easily determine this. In fact, we can easily determine the value $f(x)$ based upon this. For example, generically, on $BB(n)$-th step we will simulate all programs of length $BB(n)$ or less exactly till $BB(n)$ number of steps. We will find that the smallest program that halts on this step is of length $n$ (and hence we will output $f(BB(n))=n$).