Katana VentraIP

Theory of computation

In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., approximate solutions versus precise ones). The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?".[1]

Not to be confused with Computational theory of mind.

In order to perform a rigorous study of computation, computer scientists work with a mathematical abstraction of computers called a model of computation. There are several models in use, but the most commonly examined is the Turing machine.[2] Computer scientists study the Turing machine because it is simple to formulate, can be analyzed and used to prove results, and because it represents what many consider the most powerful possible "reasonable" model of computation (see Church–Turing thesis).[3] It might seem that the potentially infinite memory capacity is an unrealizable attribute, but any decidable problem[4] solved by a Turing machine will always require only a finite amount of memory. So in principle, any problem that can be solved (decided) by a Turing machine can be solved by a computer that has a finite amount of memory.

History[edit]

The theory of computation can be considered the creation of models of all kinds in the field of computer science. Therefore, mathematics and logic are used. In the last century, it separated from mathematics and became an independent academic discipline with its own conferences such as FOCS in 1960 and STOC in 1969, and its own awards such as the IMU Abacus Medal (established in 1981 as the Rolf Nevanlinna Prize), the Gödel Prize, established in 1993, and the Knuth Prize, established in 1996.


Some pioneers of the theory of computation were Ramon Llull, Alonzo Church, Kurt Gödel, Alan Turing, Stephen Kleene, Rózsa Péter, John von Neumann and Claude Shannon.

and Jeffrey D. Ullman (2006). Introduction to Automata Theory, Languages, and Computation. 3rd ed Reading, MA: Addison-Wesley. ISBN 978-0-321-45536-9 One of the standard references in the field.

Hopcroft, John E.

(2007). An introduction to formal language and automata. Narosa Publishing. ISBN 9788173197819.

Linz P

(2013). Introduction to the Theory of Computation (3rd ed.). Cengage Learning. ISBN 978-1-133-18779-0.

Michael Sipser

(1989). An Introduction to the Theory of Computation. Computer Science Press. ISBN 0-7167-8182-4. Archived from the original on 2007-01-07.

Eitan Gurari

Hein, James L. (1996) Theory of Computation. Sudbury, MA: Jones & Bartlett.  978-0-86720-497-1 A gentle introduction to the field, appropriate for second-year undergraduate computer science students.

ISBN

Taylor, R. Gregory (1998). Models of Computation and Formal Languages. New York: Oxford University Press.  978-0-19-510983-2 An unusually readable textbook, appropriate for upper-level undergraduates or beginning graduate students.

ISBN

Lewis, F. D. (2007). A textbook covering the topics of formal languages, automata and grammars. The emphasis appears to be on presenting an overview of the results and their applications rather than providing proofs of the results.

Essentials of theoretical computer science

Ron Sigal, Elaine J. Weyuker, Computability, complexity, and languages: fundamentals of theoretical computer science, 2nd ed., Academic Press, 1994, ISBN 0-12-206382-1. Covers a wider range of topics than most other introductory books, including program semantics and quantification theory. Aimed at graduate students.

Martin Davis

(There are many textbooks in this area; this list is by necessity incomplete.)

at MIT

Theory of Computation

at Harvard

Theory of Computation

- A theory of interactive computation. The main web source on this subject.

Computability Logic