Recursively enumerable sets of positive integers and their decision problems

Introduction. Recent developments of symbolic logic have considerable importance for mathematics both with respect to its philosophy and practice. That mathematicians generally are oblivious to the importance of this work of Gdel, Church, Turing, Kleene, Rosser and others as it affects the subject of their own interest is in part due to the forbidding, diverse and alien formalisms in which this work is embodied. Yet, without such formalism, this pioneering work would lose most of its cogency. But apart from the question of importance, these formalisms bring to mathematics a new and precise mathematical concept, that of the general recursive function of Hrbrand-Gdel-Kleene, or its proved equivalents in the developments of Church and Turing. 1 It is the purpose of this lecture to demonstrate by example that this concept admits of development into a mathematical theory much as the group concept has been developed into a theory of groups. Moreover, that stripped of its formalism, such a theory admits of an intuitive development which can be followed, if not indeed pursued, by a mathematician, layman though he be in this formal field. It is this intuitive development of a very limited portion of a sub-theory of the hoped for general theory that we present in this lecture. We must emphasize that, with a few exceptions explicitly so noted, we have obtained formal proofs of all the consequently mathematical theorems here developed informally. Yet the real mathematics involved must lie in the informal development. For in every instance the informal "proof" was first obtained; and once gotten, transforming it into the formal proof turned out to be a routine chore. A simple example of such a function is an An address presented before the New York meeting of the Society on February 26, 1944, by invitation of the Program Committee; received by the editors March 25, 1944.