Misc,
Computability and Complexity in Games
(1995)
Abstract
The paper is organized as follows. In the next section there is a detailed description of the
Rabin model and an exhaustive discussion; there is also an introductory discussion and
statement of Jones’s variation of the Rabin game (Jones, 1974). The reason for the
disproportionately long §2 are twofold: one, it gives me a chance to describe the
imaginative way Rabin stripped away the noneffective content of the Gale-Stewart game;
secondly, via Jones’s modified version of Rabin’s model I get, eventually, the chance to
introduce, in the proofs, the busy beaver game. It may be useful, for the uninitiated in
recursion theory, to know how an explicit noncomputable function is actually constructed
and then to literally see the nature of the dimensional monstrosities inherent even in
deceptively simple-looking constructions. This background will prepare the sceptical
reader to the melancholy fact that most games, even when determined and playable, are
intractably complex.
