Some Relations between Classes of Low Computational Complexity
R. O. Gandy · Bulletin of the London Mathematical Society · 1984
In 1978 I believed that I had established the results of this paper; in 1980 I tried unsuccessfully to recover the certainly uncouth, possibly fallacious proofs so that they could be included in the Festschrift for Professor Specker's 60th birthday. The reasonably concise proof given here is new. 1. Preliminaries We say that a function F: f ^ m-> N is 0-bounded if there is a number a such that F(xlt...,xJ b => F(xlt...,xm) b => F(xlt...,xm) of number-theoretic functions we shall always mean a collection which contains the successor function, the case function C {Cxyuv = x if u = v, Cxyuv = y\\fu^v) and which is closed under explicit definition. #„. denotes the set of relations whose characteristic functions are in ( 6. In [2] Grzegorczyk introduced the hierarchy S n of primitive recursive functions. For n = 0,1, 2, S n is, roughly speaking, the smallest class closed under n-bounded recursion. This statement becomes exact if we enlarge S ° to the class S o+ by adding Max {xj, x2} as an initial function. It is an idiosyncracy of Grzegorczyk's definition that Max ^ 0; thus S ° is not a class. But S ° and S ' o+ contain the same relations: