What about the fastest-growing non-computable function ? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T04:42:09Z http://mathoverflow.net/feeds/question/84820 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/84820/what-about-the-fastest-growing-non-computable-function What about the fastest-growing non-computable function ? Archimondain 2012-01-03T18:32:25Z 2012-01-03T19:09:41Z <p>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 ?</p> <p>More generally, do we have a sort of a fast-growing hierarchy for non-computable functions ?</p> <p>Thanks in advance for answers/paper ref. on the subject</p> http://mathoverflow.net/questions/84820/what-about-the-fastest-growing-non-computable-function/84822#84822 Answer by Joel David Hamkins for What about the fastest-growing non-computable function ? Joel David Hamkins 2012-01-03T18:41:28Z 2012-01-03T19:09:41Z <p>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$. </p> <p>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 <em>bounding</em> 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. </p> <p>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 <a href="http://mathoverflow.net/questions/3057/is-there-a-topology-on-growth-rates-of-functions/13780#13780" rel="nofollow">Is there a topology on growth rates of functions?</a>. 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. </p> <p>These concepts are also mentioned in several other MO answers, such as <a href="http://mathoverflow.net/questions/17473/measure-theory-for-regular-cardinals/17478#17478" rel="nofollow">here</a>. </p>