Editing Theory of computation (section)

{{short description|Academic subfield of computer science}}
{{Distinguish|Computational theory of mind}}
{{For|the journal|Theory of Computing{{!}}''Theory of Computing''}}

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 [[algorithmic efficiency|efficiently]] they can be solved or to what degree (e.g., [[approximation algorithms|approximate solutions]] versus precise ones).  The field is divided into three major branches: [[automata theory]] and [[formal language]]s, [[computability theory]], and [[computational complexity theory]], which are linked by the question: ''"What are the fundamental capabilities and limitations of computers?".''<ref>{{harvtxt|Sipser|2013|p=1}}: <blockquote> "central areas of the theory of computation: automata, computability, and complexity."</blockquote></ref>

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]].<ref name=Hodges-2012>{{cite book| first=Andrew | last=Hodges | author-link=Andrew Hodges | year = 2012 | title =Alan Turing: The Enigma | publisher=[[Princeton University Press]] |isbn=978-0-691-15564-7| edition=The Centenary }}</ref> 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]]).<ref>{{cite video | last = Rabin | first = Michael O. | author-link = Michael O. Rabin | title = Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View | date = June 2012 | url = http://videolectures.net/turing100_rabin_turing_church_goedel/ }}</ref> It might seem that the potentially infinite memory capacity is an unrealizable attribute, but any [[Decidability (logic)|decidable]] problem<ref name=Monk1976>{{cite book |author =Donald Monk |year =1976 |title =Mathematical Logic |publisher =Springer-Verlag |isbn =9780387901701 |url-access =registration |url =https://archive.org/details/mathematicallogi00jdon }}</ref> 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.