Computability and Complexity in Games

K. (Vela) Velupillai
Additional contact information
K. (Vela) Velupillai: Center for Computable Economics and Department of Economics and Queen's University of Belfast

Working Papers from University of California at Los Angeles, Center for Computable Economics

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.

New Economics Papers: this item is included in nep-cmp, nep-gth and nep-ind
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://cce.sscnet.ucla.edu/papers/vela/complexity/complexy.doc
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to cce.sscnet.ucla.edu:80 (A connection attempt failed because the connected party did not properly respond after a period of time, or established connection failed because connected host has failed to respond.)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wop:callce:_010

Access Statistics for this paper

More papers in Working Papers from University of California at Los Angeles, Center for Computable Economics Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().