Computation
Encyclopedia
Computation is defined as any type of calculation
. Also defined as use of computer technology in Information processing
.Computation is a process following a well-defined model understood and expressed in an algorithm
, protocol, network topology
, etc. Computation is also a major subject matter of computer science
: it investigates what can or cannot be done in a computational manner.
vs analog, sequential vs parallel vs concurrent
, batch
vs interactive
.
In practice, digital computation is often used to simulate natural processes (for example,
Evolutionary computation
), including those that are more naturally described by analog models of computation (for example, Artificial neural network
).
called a computer
.
Examples of such physical systems include digital computers, mechanical computer
s, quantum computer
s, DNA computers, molecular computers, analog computer
s or wetware computer
s.
This point of view is the one adopted by the branch of theoretical physics called the physics of computation
.
An even more radical point of view is the postulate of digital physics
that the evolution of the universe itself is a computation - Pancomputationalism.
, a diversity of mathematical models of computers have been developed.
Typical mathematical models of computers
are the following:
Calculation
A calculation is a deliberate process for transforming one or more inputs into one or more results, with variable change.The term is used in a variety of senses, from the very definite arithmetical calculation of using an algorithm to the vague heuristics of calculating a strategy in a competition...
. Also defined as use of computer technology in Information processing
Information processing
Information processing is the change of information in any manner detectable by an observer. As such, it is a process which describes everything which happens in the universe, from the falling of a rock to the printing of a text file from a digital computer system...
.Computation is a process following a well-defined model understood and expressed in an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
, protocol, network topology
Network topology
Network topology is the layout pattern of interconnections of the various elements of a computer or biological network....
, etc. Computation is also a major subject matter of computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
: it investigates what can or cannot be done in a computational manner.
Classes of computation
Computation can be classified by at least three orthogonal criteria: digitalDigital
A digital system is a data technology that uses discrete values. By contrast, non-digital systems use a continuous range of values to represent information...
vs analog, sequential vs parallel vs concurrent
Concurrency (computer science)
In computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other...
, batch
Batch processing
Batch processing is execution of a series of programs on a computer without manual intervention.Batch jobs are set up so they can be run to completion without manual intervention, so all input data is preselected through scripts or command-line parameters...
vs interactive
Interactive computation
In computer science, interactive computation is a mathematical model for computation that involves communication with the external world during the computation...
.
In practice, digital computation is often used to simulate natural processes (for example,
Evolutionary computation
Evolutionary computation
In computer science, evolutionary computation is a subfield of artificial intelligence that involves combinatorial optimization problems....
), including those that are more naturally described by analog models of computation (for example, Artificial neural network
Artificial neural network
An artificial neural network , usually called neural network , is a mathematical model or computational model that is inspired by the structure and/or functional aspects of biological neural networks. A neural network consists of an interconnected group of artificial neurons, and it processes...
).
Computations as a physical phenomenon
A computation can be seen as a purely physical phenomenon occurring inside a closed physical systemPhysical system
In physics, the word system has a technical meaning, namely, it is the portion of the physical universe chosen for analysis. Everything outside the system is known as the environment, which in analysis is ignored except for its effects on the system. The cut between system and the world is a free...
called a computer
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...
.
Examples of such physical systems include digital computers, mechanical computer
Mechanical computer
A mechanical computer is built from mechanical components such as levers and gears, rather than electronic components. The most common examples are adding machines and mechanical counters, which use the turning of gears to increment output displays...
s, quantum computer
Quantum computer
A quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are different from traditional computers based on transistors...
s, DNA computers, molecular computers, analog computer
Analog computer
An analog computer is a form of computer that uses the continuously-changeable aspects of physical phenomena such as electrical, mechanical, or hydraulic quantities to model the problem being solved...
s or wetware computer
Wetware computer
A wetware computer is an organic computer built from living neurons. , at the Georgia Institute of Technology, is the primary researcher driving the creation of these artificially constructed, but still organic brains...
s.
This point of view is the one adopted by the branch of theoretical physics called the physics of computation
Physics of computation
The study of the physics of computation relates to understanding the fundamental physical limits of computers. This field has led to the investigation of how thermodynamics limits information processing, the understanding of chaos and dynamical systems, and a rapidly growing effort to invent new...
.
An even more radical point of view is the postulate of digital physics
Digital physics
In physics and cosmology, digital physics is a collection of theoretical perspectives based on the premise that the universe is, at heart, describable by information, and is therefore computable...
that the evolution of the universe itself is a computation - Pancomputationalism.
Mathematical models of computation
In the theory of computationTheory of computation
In theoretical computer science, the theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm...
, a diversity of mathematical models of computers have been developed.
Typical mathematical models of computers
Model of computation
In computability theory and computational complexity theory, a model of computation is the definition of the set of allowable operations used in computation and their respective costs...
are the following:
- State models including Turing MachineTuring machineA Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
, push-down automaton, finite state automaton, and PRAMPramPram may refer to:*Pram, Austria* Pram , a musical group* Pram , a type of shallow-draught, flat-bottomed ship * A type of dinghy with a flat bow* A type of wheeled baby transport... - Functional models including lambda calculusLambda calculusIn mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
- Logical models including logic programmingLogic programmingLogic programming is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy's [1958] advice-taker proposal, logic is used as a purely declarative representation language, and a...
- Concurrent models including actor modelActor modelIn computer science, the Actor model is a mathematical model of concurrent computation that treats "actors" as the universal primitives of concurrent digital computation: in response to a message that it receives, an actor can make local decisions, create more actors, send more messages, and...
and process calculi
History
The word computation has an archaic meaning (from its Latin etymological roots), but the word has come back in use with the arising of a new scientific discipline: computer science.See also
- ComputingComputingComputing is usually defined as the activity of using and improving computer hardware and software. It is the computer-specific part of information technology...
- Physical informationPhysical informationIn physics, physical information refers generally to the information that is contained in a physical system. Its usage in quantum mechanics In physics, physical information refers generally to the information that is contained in a physical system. Its usage in quantum mechanics In physics,...
- Real computationReal computationIn computability theory, the theory of real computation deals with hypothetical computing machines using infinite-precision real numbers. They are given this name because they operate on the set of real numbers...
- Reversible computation
- HypercomputationHypercomputationHypercomputation or super-Turing computation refers to models of computation that are more powerful than, or are incomparable with, Turing computability. This includes various hypothetical methods for the computation of non-Turing-computable functions, following super-recursive algorithms...