What can computers do in principle? What are their inherent theoretical limitations? These are questions to which computer scientists must address themselves. The theoretical framework which enables such questions to be answered has been developed over the last fifty years from the idea of a computable function: intuitively a function whose values can be calculated in an effective or automatic way. This book is an introduction to computability theory (or recursion theory as it is traditionally known to mathematicians). Dr Cutland (...) begins with a mathematical characterisation of computable functions using a simple idealised computer (a register machine); after some comparison with other characterisations, he develops the mathematical theory, including a full discussion of non-computability and undecidability, and the theory of recursive and recursively enumerable sets. The later chapters provide an introduction to more advanced topics such as Gildel's incompleteness theorem, degrees of unsolvability, the Recursion theorems and the theory of complexity of computation. Computability is thus a branch of mathematics which is of relevance also to computer scientists and philosophers. Mathematics students with no prior knowledge of the subject and computer science students who wish to supplement their practical expertise with some theoretical background will find this book of use and interest. (shrink)

Game theory has proved a useful tool in the study of simple economic models. However, numerous foundational issues remain unresolved. The situation is particularly confusing in respect of the non-cooperative analysis of games with some dynamic structure in which the choice of one move or another during the play of the game may convey valuable information to the other players. Without pausing for breath, it is easy to name at least 10 rival equilibrium notions for which a serious case can (...) be made that here is the “right” solution concept for such games. (shrink)

This is the second part of a two-part paper. It can be read independently of the first part provided that the reader is prepared to go along with the unorthodox views on game theory which were advanced in Part I and are summarized below. The body of the paper is an attempt to study some of the positive implications of such a viewpoint. This requires an exploration of what is involved in modeling “rational players” as computing machines.

Game-theoretic reasoning pervades economic theory and is used widely in other social and behavioural sciences. An Introduction to Game Theory International Edition, by Martin J. Osborne, presents the main principles of game theory and shows how they can be used to understand economics, social, political, and biological phenomena. The book introduces in an accessible manner the main ideas behind the theory rather than their mathematical expression. All concepts are defined precisely, and logical reasoning is used throughout. The book requires an (...) understanding of basic mathematics but assumes no specific knowledge of economics, political science, or other social or behavioural sciences. Coverage includes the fundamental concepts of strategic games, extensive games with perfect information, and coalitional games; the more advanced subjects of Bayesian games and extensive games with imperfect information; and the topics of repeated games, bargaining theory, evolutionary equilibrium, rationalizability, and maxminimization. The book offers a wide variety of illustrations from the social and behavioural sciences. Each topic features examples that highlight theoretical points and illustrations that demonstrate how the theory may be used. (shrink)

The 'Evolution of Cooperation' addresses a simple yet age-old question; If living things evolve through competition, how can cooperation ever emerge? Despite the abundant evidence of cooperation all around us, there existed no purely naturalistic answer to this question until 1979, when Robert Axelrod famously ran a computer tournament featuring a standard game-theory exercise called The Prisoner's Dilemma. To everyone's surprise, the program that won the tournament, named Tit for Tat, was not only the simplest but the most "cooperative" entrant. (...) This unexpected victory proved that cooperation - one might even say altruism - is mathematically possible and therefore needs no hidden hand or divine agent to create and sustain it. A great roadblock to the understanding of all sorts of behavior was at last removed. The updated edition includes an extensive new chapter on cooperation in cancer cells and among terrorist organizations. (shrink)