Editing Theory of computation (section)

=== Computability theory ===
{{main|Computability theory}}
Computability theory deals primarily with the question of the extent to which a problem is solvable on a computer. The statement that the [[halting problem]] cannot be solved by a Turing machine<ref>{{cite journal |last=[[Alan Turing]] |date=1937 |title=On computable numbers, with an application to the Entscheidungsproblem |url=http://www.turingarchive.org/browse.php/B/12 |journal= Proceedings of the London Mathematical Society |publisher=IEEE |volume=2 |issue=42 |pages=230–265 |doi=10.1112/plms/s2-42.1.230 |s2cid=73712 |access-date=6 January 2015}}</ref> is one of the most important results in computability theory, as it is an example of a concrete problem that is both easy to formulate and impossible to solve using a Turing machine.  Much of computability theory builds on the halting problem result.

Another important step in computability theory was [[Rice's theorem]], which states that for all non-trivial properties of partial functions, it is [[Decidability (logic)|undecidable]] whether a Turing machine computes a partial function with that property.<ref>{{cite journal |last=Henry Gordon Rice |date=1953 |title=Classes of Recursively Enumerable Sets and Their Decision Problems |journal= Transactions of the American Mathematical Society |publisher=American Mathematical Society|volume=74 |issue=2 |pages=358–366 |doi= 10.2307/1990888|jstor=1990888|doi-access=free }}</ref>

Computability theory is closely related to the branch of [[mathematical logic]] called [[recursion theory]], which removes the restriction of studying only models of computation which are reducible to the Turing model.<ref name=davis>{{cite book|author =Martin Davis |year = 2004 |title =The undecidable: Basic papers on undecidable propositions, unsolvable problems and computable functions (Dover Ed) |publisher =Dover Publications |isbn=978-0486432281|author-link = Martin Davis (mathematician) }}</ref>  Many mathematicians and computational theorists who study recursion theory will refer to it as computability theory.