Busy beaver function

Let the following alphabet of Turing machines be fixed: $\left\{ \Lambda , \mid \right\}$. For the "busy beaver" function bb

Let the following alphabet of Turing machines be fixed: $\left\{ \Lambda , \mid \right\}$. For the "busy beaver" function bb

Show that the function arc grows unboundedly but is not monotonic: it is possible that $\operatorname {arc}(u)<\operatorname {arc}(v)$, even though the word $v$ is shorter than the word $u$.

Show that the function arc grows more slowly than every computable function: if a g.r.f. $f$ satisfies $f(x) \leqslant \operatorname {arc}(x)$ for all $x$, then $f$ is bounded.

Let $T(n)$ be the longest running time of a Turing machine with $n$ states on a blank tape. Prove that the function $T(n)$ is not computable.

Prove that the function $S(\pi (\mathfrak {M}), x)$ from the previous problem is not computable.

Let $f$ be the function defined in Example 5.40. Define $f^{*}$ to be its inverse function: $f^{*}(n)=(\max x)[f(x) \leq n]$. Prove that $f^{*}$ grows to infinity faster than any recursive function $g$. That is, for any recursive function $g$, there exists $n_{0}$ such that $f^{*}(n)>g(n)$ for all $n \geq n_{0}$. (The function $f^{*}$ is called the busy beaver function, which grows even faster than the Ackermann function.)

Let $\Gamma =\left\{ 0,1, \sqcup \right\}$ be the tape alphabet for all TMs in this problem. Define the busy beaver function $\operatorname {BB}: \mathcal{N} \longrightarrow \mathcal{N}$ as follows. For each value of $k$, consider all $k$-state TMs that halt when started with a blank tape. Let $\operatorname {BB}(k)$ be the maximum number of 1s that remain on the tape among all of these machines. Show that $\operatorname {BB}$ is not a computable function.