Does there exist a strictly increasing function $f$ from $\mathbb{N}$ to $\mathbb{N}$ which grows faster than all computable functions, but which does not have the following property: For all computable functions $g$, there exists an $n$ such that for all $m$ greater than or equal to $n$, $g(f(m)) < f(m+1)$? From what I understand, the Busy Beaver function does have that property. I am interested in the existence of a function that does not have that property.
Is there a function that grows faster than all computable functions but does not have this property?
Asked
Active
Viewed 111 times
0
-
4Sure, and easily: Take $f(2n)=BB(n), f(2n+1)=f(2n)+1$. Can you see why this satisfies all your conditions? – Steven Stadnicki Jan 03 '22 at 23:14
-
2(Incidentally, this sort of 'interleaving' is a very common technique for many constructions within complexity theory and recursion theory; it's a good abstract notion to have in your toolbook.) – Steven Stadnicki Jan 03 '22 at 23:22