Busy Beaver is an uncomputable function that grows quicker than any computable function. That means there exist functions f such that for all computable functions g: g in O(f). There is an upper bound on the order of computable functions.
The question is whether or not there is a computable function like that. So, is the set of orders of computable functions closed or open?
And if yes, do we know examples of such functions?
-
$\begingroup$ I don't think the big-O notation is very suitable for problems that have non-elementary complexity. For instance the Ackermann function $f(x)$ is computable but it is not a bound for the Ackermann+1 function $f'(x) = f(x+1)$. $\endgroup$Janmar– Janmar2022年06月29日 09:37:52 +00:00Commented Jun 29, 2022 at 9:37
-
$\begingroup$ Taking $f' = nf,ドル an equivalent formulation asks for a computable $f'$ such that for all computable $g$ there exists a constant $N_g$ such that $g(n) \leq f'(n)$ for all $n \geq N_g$. $\endgroup$Yuval Filmus– Yuval Filmus2022年06月29日 09:39:39 +00:00Commented Jun 29, 2022 at 9:39
1 Answer 1
Suppose that such a computable function $f$ exists. The function $h(n) = nf(n) + n$ is also computable, but $h(n)$ is not $O(f(n))$.
We can similarly rule out a uniformly computable countable order, that is, a uniformly computable sequence of functions $f_i$ such that for each computable $g$, we have $g = O(f_i)$ for some $i$. Indeed, given such a sequence, the function $h(n) = n\max(f_1(n),\ldots,f_n(n))+n$ is computable and is not $O(f_i)$ for any $i$.
In contrast, if we remove uniform computability, then it is trivially possible to find such a sequence, namely take an enumeration of all computable functions. Taking $F_i = \max(f_1,\ldots,f_i)$, this even gives a computable scale of functions $F_1 \leq F_2 \leq \cdots$.