On Some Games Which Are Relevant to the Theory of Recursively Enumerable Sets
A. H. Lachlan · Annals of Mathematics · 1970
In ? 1 we shall describe a class of two-person infinite games called basic games which may be applied to the elementary theory T(9Z) of recursively enumerable (r.e.) sets. The theory T(ER) will be defined in ? 1 and has been studied previously by the author in [5] and [6]. A good source for background material is Rogers [9]. Our reason for studying basic games is that every theorem of T(ER) known at the present time can be proved by constructing an effective winning strategy for a suitable basic game. This contention will be supported in ? 2 by a number of examples. In ? 3 we discuss briefly the solution of a particular kind of basic game. In ? 4 we show that two natural subclasses of the class of basic games are not adequate for deriving all theorems of T(9I). In ? 5 we have summarized our reasons for thinking that the gametheoretic approach to recursion theory is a useful one, and have listed some open questions. I am grateful to the referee for many valuable suggestions regarding the format of this paper.