A note on arbitrarily complex recursive functions (Q1106201)

\textit{M. Rabin} [Degree of difficulty of computing a function, Hebrew University Technical Report 2 (1960)] first proved that there exist almost everywhere arbitrarily complex recursive functions with range \(\{\) 0,1\(\}\) which was generalized to the machine independent case by \textit{M. Blum} [J. Assoc. Comput. Mach. 14, 322-336 (1967; Zbl 0155.015)]. This paper gives a best possible generalization of that result. Let \(\phi_ 0,\phi_ 1,..\). be an arbitrary acceptable programming system, \(\Phi_ 0,\Phi_ 1,..\). an arbitrary abstract complexity measure on \(\phi_ 0,\phi_ 1,... \). For any recursive functions f and g, f is finite variant of g iff \(\{\) \(x| f(x)\neq g(x)\}\) is finite; f is g-sparse iff \(\forall x[f(x)\neq 0\to f(y)=0\) for all y's such that \(x<y\leq x+g(x)]\). Main result: For any recursive functions g and h with g(x)\(\geq x\) for all x, there exists a \(\{\) 0,1\(\}\)-valued g-sparse recursive function f such that, for any program i, if \(\phi_ i\) is a finite variant of f then \(\Phi_ i(x)>h(x)\) for all but finitely many x.