Editing Computation (section)

== Introduction ==
The notion that mathematical statements should be 'well-defined' had been argued by mathematicians since at least the [[1600s (decade)|1600s]],<ref>{{cite book | last=Couturat | first=Louis | title=la Logique de Leibniz a'Après des Documents Inédits | publisher=Paris | date=1901 | isbn=978-0343895099}}</ref> but agreement on a suitable definition proved elusive.<ref name="Davis Davis 2000">{{cite book | last1=Davis | first1=Martin | last2=Davis | first2=Martin D. | title=The Universal Computer | publisher=W. W. Norton & Company | date=2000 | isbn=978-0-393-04785-1}}</ref> A candidate definition was proposed independently by several mathematicians in the 1930s.<ref name="Davis">{{cite book | last=Davis | first=Martin | title=Computability & Unsolvability | publisher=Courier Corporation | date=1982-01-01 | isbn=978-0-486-61471-7}}</ref> The best-known variant was formalised by the mathematician [[Alan Turing]], who defined a well-defined statement or calculation as any statement that could be expressed in terms of the initialisation parameters of a [[Turing machine]].<ref>{{Cite news | last= Turing | first= A.M. |year = 1937 | title = On Computable Numbers, with an Application to the Entscheidungsproblem | orig-year = Delivered to the Society November 1936 | periodical = Proceedings of the London Mathematical Society | series = 2 | volume = 42 | pages = 230–65 | doi= 10.1112/plms/s2-42.1.230 | url = http://www.comlab.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf }}</ref> Other (mathematically equivalent) definitions include [[Alonzo Church]]'s ''[[Lambda calculus|lambda-definability]]'', [[Herbrand]]-[[Gödel]]-[[Kleene]]'s ''[[General recursive function|general recursiveness]]'' and [[Emil Post]]'s ''1-definability''.<ref name="Davis"/>

Today, any formal statement or calculation that exhibits this quality of well-definedness is termed '''computable''', while the statement or calculation itself is referred to as a '''computation'''.

Turing's definition apportioned "well-definedness" to a very large class of mathematical statements, including all well-formed [[equations|algebraic statements]], and all statements written in modern computer programming languages.<ref name="Davis Davis 2000 p. ">{{cite book | last1=Davis | first1=Martin | last2=Davis | first2=Martin D. | title=The Universal Computer | publisher=W. W. Norton & Company | date=2000 | isbn=978-0-393-04785-1 | page=}}</ref>

Despite the widespread uptake of this definition, there are some mathematical concepts that have no well-defined characterisation under this definition. This includes [[the halting problem]] and [[busy beaver|the busy beaver game]]. It remains an open question as to whether there exists a more powerful definition of 'well-defined' that is able to capture both computable and 'non-computable' statements.<ref group=note>The study of non-computable statements is the field of [[hypercomputation]].</ref><ref>{{cite journal | author=Davis, Martin | title = Why there is no such discipline as hypercomputation | journal = Applied Mathematics and Computation | volume = 178 | issue = 1 <!-- Special Issue on Hypercomputation --> | year = 2006 | pages = 4–7 | doi = 10.1016/j.amc.2005.09.066}}</ref>

Some examples of mathematical statements that are computable include:
* All statements characterised in modern programming languages, including [[C++]], [[Python (programming language)|Python]], and [[Java (programming language)|Java]].<ref name="Davis Davis 2000 p. "/>
* All calculations carried by an electronic [[computer]], [[calculator]] or [[abacus]].
* All calculations carried out on an [[analytical engine]].
* All calculations carried out on a [[Turing Machine]].
* The majority of mathematical statements and calculations given in maths textbooks.

Some examples of mathematical statements that are ''not'' computable include:

* Calculations or statements which are ill-defined, such that they cannot be unambiguously encoded into a Turing machine: ("Paul loves me twice as much as Joe").
* Problem statements which do appear to be well-defined, but for which it can be proved that no Turing machine exists to solve them (such as [[the halting problem]]).

Computation can be seen as a purely physical process occurring inside a closed [[physical system]] called a [[computer]]. Turing's 1937 proof, ''[[On Computable Numbers, with an Application to the Entscheidungsproblem]]'', demonstrated that there is a formal equivalence between computable statements and particular physical systems, commonly called [[computers]]. Examples of such physical systems are: [[Turing machines]], human mathematicians following strict rules, [[digital computer]]s, [[mechanical computer]]s, [[analog computer]]s and others.