Computation

A computation is any type of

Mechanical or electronic devices (or, historically, people) that perform computations are known as computers. The study of computation is the field of computability, itself a sub-field of computer science and mathematical logic.

Introduction

The notion that mathematical statements should be 'well-defined' had been argued by mathematicians since at least the

• All statements characterised in modern programming languages, including C++, Python, and Java.^[7]
• 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
  ).

The Physical process of computation

Computation can be seen as a purely physical process occurring inside a closed

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."^[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]

The semantic account

Philosophers such as Jerry Fodor^[11] 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

In the theory of computation, a diversity of mathematical models of computation has been developed. Typical mathematical models of computers are the following:

• State models including
  PRAM
• Functional models including lambda calculus
• Logical models including logic programming
• Concurrent models including
  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.^[13]: ch.1 He maintains that a computational system is a complex object which consists of three parts. First, a mathematical dynamical system ${\displaystyle DS}$ with discrete time and discrete state space; second, a computational setup ${\displaystyle H=\left(F,B_{F}\right)}$, which is made up of a theoretical part ${\displaystyle F}$, and a real part ${\displaystyle B_{F}}$; third, an interpretation ${\displaystyle I_{DS,H}}$, which links the dynamical system ${\displaystyle DS}$ with the setup ${\displaystyle H}$.^{[14]: pp.179–80}

See also

• Computability theory
• Hypercomputation
• Computational problem
• Limits of computation
• Computationalism

Notes

References