Acomputation is any type ofarithmetic or non-arithmeticcalculation that is well-defined.[1][2] Common examples of computation aremathematical equation solving and theexecution of computeralgorithms.
Mechanical or electronic devices (or,historically, people) that perform computations are known ascomputers.Computer science is an academic field that involves the study of computation.
The notion that mathematical statements should be 'well-defined' had been argued by mathematicians since at least the1600s,[3] but agreement on a suitable definition proved elusive.[4] A candidate definition was proposed independently by several mathematicians in the 1930s.[5] The best-known variant was formalised by the mathematicianAlan Turing, who defined a well-defined statement or calculation as any statement that could be expressed in terms of the initialisation parameters of aTuring machine.[6] Other (mathematically equivalent) definitions includeAlonzo Church'slambda-definability,Herbrand-Gödel-Kleene'sgeneral recursiveness andEmil Post's1-definability.[5]
Today, any formal statement or calculation that exhibits this quality of well-definedness is termedcomputable, while the statement or calculation itself is referred to as acomputation.
Turing's definition apportioned "well-definedness" to a very large class of mathematical statements, including all well-formedalgebraic statements, and all statements written in modern computer programming languages.[7]
Despite the widespread uptake of this definition, there are some mathematical concepts that have no well-defined characterisation under this definition. This includesthe halting problem andthe 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.[note 1][8]
Some examples of mathematical statements that are computable include:
Some examples of mathematical statements that arenot computable include:
Computation can be seen as a purely physical process occurring inside a closedphysical system called acomputer. 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 calledcomputers. Examples of such physical systems are:Turing machines, human mathematicians following strict rules,digital computers,mechanical computers,analog computers and others.
An alternative account of computation is found throughout the works ofHilary Putnam and others.Peter Godfrey-Smith has dubbed this the "simple mapping account."[9]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."[10]
Philosophers such asJerry Fodor[11] have suggested various accounts of computation with the restriction thatsemantic 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 ofpancomputationalism, the idea that everything can be said to be computing everything.
Gualtiero Piccinini proposes an account of computation based onmechanical 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[clarification needed] by multiple realizers[clarification needed] and multiple mechanisms, and that the inputs and outputs of the mechanism also bemultiply 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 thebrain or in aquantum computer. A rule, in this sense, provides a mapping among inputs, outputs, and internal states of the physical computing system.[12]
In thetheory of computation, a diversity of mathematical models of computation has been developed.Typical mathematicalmodels of computers are the following:
Giunti calls the models studied by computation theorycomputational systems, and he argues that all of them are mathematicaldynamical systems with discrete time and discrete state space.[13]: ch.1 He maintains that a computational system is a complex object which consists of three parts. First, a mathematical dynamical system with discrete time and discrete state space; second, a computational setup, which is made up of a theoretical part, and a real part; third, an interpretation, which links the dynamical system with the setup.[14]: pp.179–80
{{cite book}}:ISBN / Date incompatibility (help)