Recursive functions of one variable
Julia Robinson · Proceedings of the American Mathematical Society · 1968
We say that the function F is obtained by general recursion from A, B, M, and TV if (i) FA=M, FB = NF and(ii) every natural number n belongs to (R(75M) for some k^Q.If F satisfies (i), then FiBkAt)=NkMt.If A and B satisfy (ii), then every natural number n is BkAt for some k and t.Hence F is uniquely determined.Furthermore if A, B, M, and N are computable functions, then given n, we can obtain k and t effectively so F is computable.Condition (ii) is satisfied if A is the zero function 0 and B is the successor function S.There is a function obtained by general recursion from 0, S, M, and N if and only if M is a constant function, say M = SmO.Then Ft = N'm.Thus, iteration is included in general recursion.If G is a permutation, then F = G~1 can be obtained by general recursion from GS, GO, S, and 0 since FGS = S, FGO = OF, and every n belongs to (R((GO)*GS) for k = 0 or k = l.More generally, if F is determined by FG = H where G assumes all values, then F is obtained by general recursion from GS, GO, HS, and 770 since FGS = HS, FGO = HOF, and the side condition holds as before.