Editing Computation

{{short description|Any type of calculation}}

A '''computation''' is any type of [[arithmetic]] or non-arithmetic [[calculation]] that is well-defined.<ref>{{Cite web |date=2024-10-11 |title=Definition of COMPUTATION |url=https://www.merriam-webster.com/dictionary/computation |access-date=2024-10-12 |website=www.merriam-webster.com |language=en}}</ref><ref>{{cite web|title=Computation: Definition and Synonyms from Answers.com|url=http://www.answers.com:80/topic/computation|website=Answers.com|access-date=26 April 2017|archive-url=https://web.archive.org/web/20090222005439/http://www.answers.com/topic/computation|archive-date=22 February 2009|url-status=dead}}</ref> Common examples of computation are [[mathematical equation]] solving and the [[Execution (computing)|execution]] of computer [[algorithms]].

Mechanical or electronic devices (or, [[History of computing hardware|historically]], people) that perform computations are known as ''[[computer]]s''. [[Computer science]] is an academic field that involves the study of computation.

== 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.

== Alternative accounts of computation ==

=== The mapping account ===
An alternative account of computation is found throughout the works of [[Hilary Putnam]] and others. [[Peter Godfrey-Smith]] has dubbed this the "simple mapping account."<ref>{{Citation|last=Godfrey-Smith|first=P.|year=2009|title=Triviality Arguments against Functionalism|journal=Philosophical Studies|volume=145|issue=2|pages=273–95|doi=10.1007/s11098-008-9231-3|s2cid=73619367 }}</ref> [[Gualtiero Piccinini|Gualtiero Piccinini's]] summary of this account states that a physical system can be said to perform a specific computation when there is a mapping between the state of that system and the computation such that the "microphysical states [of the system] mirror the state transitions between the computational states."<ref>{{cite book|last=Piccinini|first=Gualtiero|title=Physical Computation: A Mechanistic Account|place=Oxford|publisher=Oxford University Press|year=2015|page=18|isbn=9780199658855}}</ref>

=== The semantic account ===
Philosophers such as [[Jerry Fodor]]<ref>{{Citation | last = Fodor | first = J. A. | year = 1986 | title = The Mind-Body Problem | journal = Scientific American | volume = 244 | issue = January 1986}}</ref> have suggested various accounts of computation with the restriction that [[semantics|semantic]] content be a necessary condition for computation (that is, what differentiates an arbitrary physical system from a computing system is that the operands of the computation represent something).  This notion attempts to prevent the logical abstraction of the mapping account of [[digital physics#Pancomputationalism or the computational universe theory|pancomputationalism]], the idea that everything can be said to be computing everything.

=== The mechanistic account ===
[[Gualtiero Piccinini]] proposes an account of computation based on [[mechanical philosophy]]. It states that physical computing systems are types of mechanisms that, by design, perform physical computation, or the manipulation (by a functional mechanism) of a "medium-independent" vehicle according to a rule. "Medium-independence" requires that the property can be instantiated{{clarify|date=February 2022}} by multiple realizers{{clarify|date=February 2022}} and multiple mechanisms, and that the inputs and outputs of the mechanism also be [[Multiple realizability|multiply realizable]]. In short, medium-independence allows for the use of physical variables with properties other than voltage (as in typical digital computers); this is imperative in considering other types of computation, such as that which occurs in the [[brain]] or in a [[quantum computer]]. A rule, in this sense, provides a mapping among inputs, outputs, and internal states of the physical computing system.<ref>{{cite book | last = Piccinini | first = Gualtiero | title = Physical Computation: A Mechanistic Account | place = Oxford | publisher = Oxford University Press | year = 2015 | page = 10 | isbn = 9780199658855}}</ref>

== Mathematical models ==
{{Main|Model of computation}}
In the [[theory of computation]], a diversity of mathematical models of computation has been developed.
Typical mathematical [[Model of computation|models of computers]] are the following:
* State models including [[Turing machine]], [[pushdown automaton]], [[finite-state automaton]], and [[Parallel random access machine|PRAM]]
* Functional models including [[lambda calculus]]
* Logical models including [[logic programming]]
* Concurrent models including [[actor model]] and [[process calculi]]
Giunti calls the models studied by computation theory ''computational systems,'' and he argues that all of them are mathematical [[dynamical system]]s with discrete time and discrete state space.<ref>{{cite book|last=Giunti|first=Marco|title=Computation, Dynamics, and Cognition|place=New York|publisher=Oxford University Press|year=1997|isbn=978-0-19-509009-3}}</ref>{{rp|ch.1}} He maintains that a computational system is a complex object which consists of three parts. First, a mathematical dynamical system <math>DS</math> with discrete time and discrete state space; second, a computational setup <math>H=\left(F, B_F\right)</math>, which is made up of a theoretical part <math>F</math>, and a real part <math>B_F</math>; third, an interpretation <math>I_{DS,H}</math>, which links the dynamical system <math>DS</math> with the setup <math>H</math>.<ref>{{Citation|last=Giunti|first=Marco|year=2017|title=What is a Physical Realization of a Computational System?|journal=Isonomia -- Epistemologica|volume=9|pages=177–92|issn=2037-4348|url=https://www.researchgate.net/publication/319631506}}</ref>{{rp|pp.179–80}}

== See also ==
* [[Computability theory]]
* [[Hypercomputation]]
* [[Computational problem]]
* [[Limits of computation]]
* [[Computationalism]]

== Notes ==
{{reflist|group=note}}

== References ==
{{Reflist}}

[[Category:Theoretical computer science]]
[[Category:Computability theory]]