Recursively enumerable sets of positive integers and their decision problems

Abstract

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 Gödel, 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 Hërbrand-Gödel-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. 2 We shall not here reproduce the formal definition of recursive function of positive integers.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.1 For "general recursive function" see {9] ([8] a prerequisite), [12] and [11]; for Church's "X-defineability, " [l] and [6]; for Turing's "computability," [24] and the writer's related [18].To this may be added the writer's method of "canonical systems and normal sets" [19 ].See pp.39-42 and bibliography of [6 ] for a survey of the literature and further references.Numbers in brackets refer to the bibliography at the end of the paper.1 Our present formal proofs, while complete, will require drastic systématisation and condensation prior to publication.