I just try to prove that $BB(n)$ (BusyBeaver-Function) grows faster than any other computable function.
Maybe someone can check the proof?
$f(n)$ is a computable function which grows to infinity: $lim_{n\to\infty}{f(n)}=\infty$. $BB(n)$ is the BusyBeaver function.
I try to prove now: $lim_{n\to\infty}{\frac{f(n)}{BB(n)}=0}$ for any computable $f(n)$.
step 1
If $f(n)$ is computable there must be a turing machine with $C$ states which can compute $f(n)$. But it only contains the function $f(n)$ without an input, which means $BB(C)$ computes $f(0)$.
Current state: probably $BB(C)<f(C)$, because $BB(C)\geq f(0)$
step 2
We can now prepend a state to the turing machine from $BB(C)$ which just writes a single $1$ and then executes $f(n)$. So $BB(1+C)$ computes $f(1)$.
Current state: $BB(1+C)\geq f(1)$
step 3
$g(n)=2n$ is a computable function which means, there is a turing machine with $U$ states which computes this function. More specific: Of course it is possible to create a turing machines which just doubles a sequence of the symbol $1$.
Use now the function $g(n)$ to copy the single written $1$ in the $BB(1+C)$.
Then we have: $BB(1+U+C)$ which computes $f(2)$.
Just to repeat: $BB(1+U+C)$ does now the following things:
- Write $1$. (Needs one state)
- Copy the written $1$. (Needs $U$ states).
- Execute $f(n)$ (In this case: $=f(2)$) (Needs $C$ states)
step 4
$g(n)$ is cool, so just add it another time after the first $g(n)$. This needs additional $U$ states.
Then we have: $BB(1+U+U+C)=BB(1+2U+C)$ which computes $f(4)$.
Just to repeat: $BB(1+2U+C)$ does now the following things:
- Write $1$. (Needs one state)
- Copy the written $1$. (Needs $U$ states).
- Copy all written $1$s. (Needs $U$ states).
- Execute $f(n)$ (In this case: $=f(4)$) (Needs $C$ states)
step 5
It is possible to add $g(n)$ as many times as we like. Every time the input for the computed $f(n)$ is doubled.
This means: $BB(1+v*U+C)\geq f(2^v)$
step 6
We know: $lim_{n\to\infty}\frac{f(n)}{f(2^n)}=0$
Now we can replace the denominator:
$lim_{v\to\infty}\frac{f(1+v*U+C)}{BB(1+v*U+C)}=0$
Simplify:
$lim_{n\to\infty}\frac{f(n)}{B(n)}=0$
Hurray, the proof is (hopefully) done:)
Thank you for reading this and sorry for my english.
Just another short question:
If it is proven that $BB(n)$ grows faster than any computable function, then it also should be proven automatically that $BB^{-1}(n)$ grows slower to $\infty$ than any other computable function $f(n)$ which grows to $\infty$?
regards Kevin