Computation: Difference between revisions
Jump to navigation
Jump to search
imported>Kvng m unpiped links using script |
imported>HyperAnd rv |
||
| Line 6: | Line 6: | ||
== Introduction == | == 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 = | 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 = https://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'''. | 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'''. | ||
| Line 15: | Line 15: | ||
Some examples of mathematical statements that are computable include: | 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]] | * 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 by an electronic [[computer]], [[calculator]] or [[abacus]] | ||
* All calculations carried out on an [[analytical engine]] | * All calculations carried out on an [[analytical engine]] | ||
* All calculations carried out on a [[Turing Machine]] | * All calculations carried out on a [[Turing Machine]] | ||
* The majority of mathematical statements and calculations given in maths textbooks | * The majority of mathematical statements and calculations given in maths textbooks | ||
Some examples of mathematical statements that are ''not'' computable include: | 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"). | * 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 | * Problem statements that 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. | 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. | ||