A note on arbitrarily complex recursive functions
\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.
- Almost-everywhere complexity hierarchies for nondeterministic time
- A characterisation of multiply recursive functions with Higman's lemma.
- The intrinsic difficulty of recursive functions
- Generating some classes of recursive functions by superpositions of simple arithmetic functions
- Embedding recursive functions in universal algorithms
- scientific article; zbMATH DE number 1222608 (Why is no real title available?)
- scientific article; zbMATH DE number 1354146 (Why is no real title available?)
- ‘Golomb-like’ nested recursions with Beatty function solutions
- A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
- A note on A.E. h-complex functions
This page was built for publication: A note on arbitrarily complex recursive functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1106201)
