Computability and Complexity in Games

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.