Postby **Moole** » Sat Jan 11, 2014 4:14 pm UTC

It never becomes uncomputable. The problem here is that is that, if we define a computable function, one can always make another computable one to grow much much faster, as you are doing. Also, worse, one can consider that, if one defines a sequence of computable functions, there is always a function growing faster than all of them - if f_{n} is the sequence, where each function grows faster than the last, F(n)=f_{n}(n) grows faster than all of them. This gives the nice implication that you can, from any initial sequence of functions, you can define an increasing sequence of computable functions corresponding to every countable ordinal, based off of any starting sequence of computable functions. This sort of makes an annoying problem: You cannot write down a largest computable function, nor can you write down a sequence containing a computable function larger than every other (yet, simultaneously, I think it is probably trivial to define a function for each ordinal containing a computable function larger than any given other).

I suppose you could define a hierarchy of functions as follows, taking an ordinal k:

f_{0}(x) = x+1

f_{k+1}(x)=f_{k}(f(x))

And for limit ordinals, choose an increasing function O_{k} such that, for any j<k, there exists an n such that O(n)>j.

f_{k}(x)=f_{O(x)}(x)

This has the following first few terms. For finite n:

f_{n}(x) = x+n

Then, regardless of choice of O_{ω}, it must hold that (where we'll just write ~ to say that it's at least this, possibly minus smaller terms)

f_{ω}(x) ~ 2x

f_{aω}(x) ~ 2^{a}x

Though my definition might not be strong enough, since, for f_{ω2}(x), we basically only get that the function's slope goes to infinity, but maybe not very quickly. Though, I don't know if that will cause issues... Maybe someone can prove that, for any computable function g, there exists an ordinal k such that, for all large enough x, f_{k}(x) > g(x), or come up with a better definition.

Mathematical hangover (n.): The feeling one gets in the morning when they realize that that short, elementary proof of the Riemann hypothesis that they came up with at midnight the night before is, in fact, nonsense.