Theory of Computation

Introduction

Theory of computation is a scientific field that deals with the study of algorithms and their efficiency, as well as the fundamental capabilities and limitations of computers. It is a branch of theoretical computer science and mathematics, and is concerned with understanding what problems can be solved on a model of computation, how efficiently they can be solved, and to what degree they can be solved precisely or approximately.

History

The theory of computation has its roots in the work of pioneers such as Ramon Llull, Alonzo Church, Kurt Gödel, Alan Turing, Stephen Kleene, Rózsa Péter, John von Neumann, and Claude Shannon. It became an independent academic discipline in the last century, having been separated from mathematics.

Branches

The theory of computation is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory. These branches are linked by the question of what are the fundamental capabilities and limitations of computers.

• Automata theory deals with the study of automata, which are abstract machines that process symbols according to a set of rules. It covers topics such as grammars, languages, automata, and production rules (constraints).

• Computability theory studies the class of problems that can be solved by a Turing machine, which is a simple model of computation that can be analyzed and used to prove results.

• Computational complexity theory focuses on the efficiency of algorithms, and how to measure and compare their running time and space requirements.

Model of Computation

A model of computation is a mathematical abstraction of a computer that helps in performing a rigorous study of computation. The most commonly examined model is the Turing machine, which represents the most powerful possible "reasonable" model of computation.

Further Reading

For further reading, there are several textbooks aimed at computer scientists that cover the topics of automata theory, languages, and computation:

• Hopcroft, John E., and Jeffrey D. Ullman (2006). Introduction to Automata Theory, Languages, and Computation. 3rd ed. Reading, MA: Addison-Wesley. ISBN 978-0-321-45536-9
• Hein, James L. (1996). Theory of Computation. Sudbury, MA: Jones & Bartlett. ISBN 978-0-86720-497-1
• Taylor, R. Gregory (1998). Models of Computation and Formal Languages. New York: Oxford University Press. ISBN 978-0-19-510983-2

External Links

For more information, you can visit the following external links:

• Theory of Computation at MIT
• Theory of Computation at Harvard
• Computability Logic