A theorem on general recursive functions
Shih-Chao Liu · Proceedings of the American Mathematical Society · 1960
This theorem is an improved version of the result obtained by Myhill [1] as well as a similar one obtained by Routledge [2, Theorem 4]. As functions of one variable are concerned, the foregoing theorem is the same as Routledge's except that the well-ordering < referred to in this note is primitive recursive while it is defined by general recursive processes in Routledge's paper (see [2, Theorem 2 ]). Myhill's statement is, however, not sufficiently explicit. A more explicit statement of his result was supplied by Kleene in a letter to the author. The theorem in this note differs from Kleene's formulation only in that Kleene expressed f(n) as U(g(2n)) while here the function U is not used. This leads to the result f(n) =g(2n), which is, according to Routledge (see [2, ??8 and 9]), the best possible in the sense that we can no longer omit the function 2n and therefore can not simply equate f(n) and g(n). PROOF OF THE THEOREM. Let f(n) be any given general recursive function. According to a theorem by Kleene [3, p. 288] there are two primitive recursive functions K(n) and T(x, y) such that