article · 2008

TURING GAMES: A STUDY OF EQUIVALENCE BETWEEN GAMES AND COMPUTATION

Devang Thakkar

Cited by 0Abstract and details only

Abstract

Abstract. In this paper I try to explore the equivalence of Turing Machines and games. The main idea I am trying to achieve is that every computation is a game and vice versa. Now the basic model that computer science proposes for computation is the model of a Turing machine where in the machine has a state transition function which is a set of rules that define what state you should be in and an input tape which consists of symbols based on which future decisions are made. The model that I propose tries to achieve a smooth transition between a game and a Turing Machine and hence allows application of mathematical techniques of either field to be applied to the other. I provide the basis and examples of two transforms; one that converts a Turing machine into a game and second that converts a game to a Turing machine. The main question that might be arising in your mind right now is what purpose does this serve? The reasoning here is if I am able to generalize my transforms and make these reductions possible then I can use the relation between language strings and paths to equilibrium that I prove in this paper to provide useful reductions from hard problems arising in the fields of both computational complexity and game theory to simpler ones in the other field. Finally I provide various open questions for future work in this area and also some applications of the results proposed here.

Cite this paper

APA 7

Thakkar, D. (2008). TURING GAMES: A STUDY OF EQUIVALENCE BETWEEN GAMES AND COMPUTATION.

MLA 9

Thakkar, Devang. “TURING GAMES: A STUDY OF EQUIVALENCE BETWEEN GAMES AND COMPUTATION.” 2008.

Chicago

Thakkar, Devang. 2008. “TURING GAMES: A STUDY OF EQUIVALENCE BETWEEN GAMES AND COMPUTATION.”

Harvard

Thakkar, D. (2008) ‘TURING GAMES: A STUDY OF EQUIVALENCE BETWEEN GAMES AND COMPUTATION’.

BibTeX

@article{thakkar2008turing,
  title = {{TURING GAMES: A STUDY OF EQUIVALENCE BETWEEN GAMES AND COMPUTATION}},
  author = {Thakkar, Devang},
  year = {2008}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.