Degrees of computability
Norman Z. Shapiro · Transactions of the American Mathematical Society · 1956
Introduction.In the theory of recursive functions, several decision problems have been proved unsolvable.A decision problem arises when we are confronted with a set TV of mathematical objects and a subset S of 7Y.We desire a mechanical procedure which will operate on elements of TV, deterfore not be everywhere defined in cases where some expressions do not represent elements of TV.Our purpose, in this work, will be the study of the relations, Ps, for various sets TV.We shall wish to determine, for particular sets S, whether Ps is recursive, and more generally, determine what the position of Ps is in the Kleene hierarchy(3).We shall also be interested in obtaining general resultsPresented to the Society, February 27, 1954, under the title Recursive sets of real numbers;received by the editors January 25, 1955.(') Many of the contents of this paper were submitted as the author's Ph.D. thesis to Princeton University in March 1955.They were obtained under the able direction of Alonzo Church and would never have existed were it not for the kind efforts of Joseph Nyberg, F. S. Nowlan, Joseph Landin, and Martin Davis.(2) Our notation is patterned after that used in [8].(3) See [3] or [5 J. 281(4) See [1].