4
$\begingroup$

The Busy-Beaver trick provides a nice example of non-computable functions (let say from $\mathbb{N}$ to $\mathbb{N}$) which grows faster than any computable functions. But what can we say when we do not restrict ourselves to computable functions. My question could be, given a countable sets of functions, can we always find a function which grows faster than any function in this set ?

More generally, do we have a sort of a fast-growing hierarchy for non-computable functions ?

Thanks in advance for answers/paper ref. on the subject

$\endgroup$

1 Answer 1

14
$\begingroup$

An easy diagonalization shows that for every countable family of functions $g_n:\mathbb{N}\to\mathbb{N}$, there is a function $f$ eventually exceeding any one of them. Just let $f(n)=\sup_{k\leq n}g_k(n)+1$.

Although it may seem difficult to extend this idea to uncountable families of functions, the fact is that it is consistent with the ZFC axioms of set theory that one may do so. Specifically, the bounding number $\frak{b}$ is the size of the smallest family of functions $f:\mathbb{N}\to\mathbb{N}$ which are not (eventually) bounded by any single function. The observation above shows that the bounding number is uncountable, and it is clearly at most continuum, so under the continuum hypothesis the bounding number is precisely $\aleph_1$. The interesting thing, however, is that the bounding number can be strictly larger than $\aleph_1$, and indeed, by the method of forcing, it can be made as large as you like.

There are numerous interesting set-theoretic issues arising in connection with the bounding number and the other cardinal characteristics of the continuum, some of which I explain in my answer to the MO question Is there a topology on growth rates of functions?. Perhaps the most related to this question are the bounding and dominating numbers, which provide two distinct concepts of measuring the height of the order.

These concepts are also mentioned in several other MO answers, such as here.

$\endgroup$
2
  • $\begingroup$ well, I wasn't expected it to be so easy ;) $\endgroup$ Commented Jan 3, 2012 at 18:49
  • $\begingroup$ Thanks a lot, your answer about the topology on groth rates of functions looks very interesting $\endgroup$ Commented Jan 3, 2012 at 18:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .