Reference for checking primitive recursiveness

Question

There is a theorem that states a function $f$ can be computed with a Turing-machine in time $O(g)$ with primitive recursive $g$ (of the length of input) iff $f$ is primitive recursive.

Where can I find a reference for this theorem? Wikipedia seems to state it but gives no references, nor does my books.

Answer 1

This is known as a Ritchie-Cobham property, or a honesty property of primitive-recursive functions. See for instance Theorem VIII.8.8, page 297 in P.G. Odifreddi, Classical Recursion Theory, vol. 2, 1999.

Odifreddi refers to

• Kleene, General recursive functions of natural numbers, Math. Ann. 112:727--742, 1936,
• Cobham, The intrinsic computational difficulty of functions, Log. Meth. Phil. Sci. 2:24--20, 1964,
• Meyer, Depth of nesting and the Grzegorczyk hierarchy, Not. Am. Math. Soc. 12, 1965.

Answer 2

You can look at:

A. Grzegorczyk. Some classes of recursive functions. Rozprawy Matematyczne, (IV), 1953.

R. W. Ritchie. Classes of predictably computable functions. Trans. A.M.S., 106:139–173, 1963.

(I don't know if you can find them for free in Internet).

Or download the Robert Daley's Lecture Notes "Introduction to Theory of Computation" that contains a detailed explanation of the equivalence $PR \equiv LOOP \setminus WHILE$ (LOOP is a simple programming language).

Proof sketch

If $f \in PR$ then you can build a TM that computes $f$ and is time-bounded by a primitive recursive function. To prove it, you can use the derivation of $f$: start from constant/successor/projection functions and then use induction on the operators composition/primitive recursion.

Conversely, if you have a $TM_{PR}$ that computes a function in $O(g)\ with\ g\ \in PR$ then you can build a LOOP program that emulates TM on each input $x$: if $m$ is the string representation of $TM_{PR}$ then the LOOP program will:

Prog:
1) decode the transition table from m
2) build a representation of the tape / head position / current state
3) FOR g(|x|) DO
   3.1) simulate a single step of the TM (or do nothing if in a final state)
4) output the current representation of the tape

each step of Prog is primitive recursive (i.e. doesn't contain while / until); note that g used in the FOR statement is by hypothesis primitive recursive.

Prog is guarantee to end and correctly output $TM_{PR}(x)$ because $g(|x|)$ is a time bound for $TM_{PR}$.

Since $LOOP \setminus WHILE \equiv PR$ then the function computed by $TM_{PR}$ is in $PR$