Computation
![]() | This article possibly contains original research. (July 2022) |
Computation is any type of arithmetic or non-arithmetic calculation that follows a well-defined model (e.g., an algorithm).[1][2]
Mechanical or electronic devices (or, historically, people) that perform computations are known as computers. An especially well-known discipline of the study of computation is computer science.
Physical process
Computation can be seen as a purely physical process occurring inside a closed physical system called a computer. Examples of such physical systems are digital computers, mechanical computers, quantum computers, DNA computers, molecular computers, microfluidics-based computers, analog computers, and wetware computers.
This point of view has been adopted by the physics of computation, a branch of theoretical physics, as well as the field of natural computing.
An even more radical point of view, pancomputationalism, is the postulate of digital physics that argues that the evolution of the universe is itself a computation.
The mapping account
The classic account of computation is found throughout the works of Hilary Putnam and others. Peter Godfrey-Smith has dubbed this the "simple mapping account."[3] 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."[4]
The semantic account
Philosophers such as Jerry Fodor[5] have suggested various accounts of computation with the restriction that 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 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[clarification needed] by multiple realizers[clarification needed] and multiple mechanisms, and that the inputs and outputs of the mechanism also be 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.[6]
Mathematical models
In the theory of computation, a diversity of mathematical models of computers has been developed. Typical mathematical models of computers are the following:
- State models including Turing machine, pushdown automaton, finite state automaton, and 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 systems with discrete time and discrete state space.[7]: 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 .[8]: pp.179–80
See also
- Computationalism
- Real computation
- Reversible computation
- Hypercomputation
- Lateral computing
- Computational problem
- Multiple realizability
- Limits of computation
References
- ^ Computation from the Free Merriam-Webster Dictionary
- ^ "Computation: Definition and Synonyms from Answers.com". Answers.com. Archived from the original on 22 February 2009. Retrieved 26 April 2017.
- ^ Godfrey-Smith, P. (2009), "Triviality Arguments against Functionalism", Philosophical Studies, 145 (2): 273–95, doi:10.1007/s11098-008-9231-3
- ^ Piccinini, Gualtiero (2015). Physical Computation: A Mechanistic Account. Oxford: Oxford University Press. p. 18. ISBN 9780199658855.
- ^ Fodor, J. A. (1986), "The Mind-Body Problem", Scientific American, 244 (January 1986)
- ^ Piccinini, Gualtiero (2015). Physical Computation: A Mechanistic Account. Oxford: Oxford University Press. p. 10. ISBN 9780199658855.
- ^ Giunti, Marco (1997). Computation, Dynamics, and Cognition. New York: Oxford University Press. ISBN 978-0-19-509009-3.
- ^ Giunti, Marco (2017), "What is a Physical Realization of a Computational System?", Isonomia -- Epistemologica, 9: 177–92, ISSN 2037-4348