What Computation Is
Computation is the mechanical transformation of input symbols into output symbols by following a fixed, finite set of rules.
A definition without magic
Computation is the step-by-step manipulation of symbols according to rules that need no insight to apply. A process is a computation when each step is fully determined by the current state and a finite rulebook, and the whole thing could in principle be carried out by a clerk with paper who understands nothing of the meaning.
This framing separates what is being computed from how fast and on what. The same function can be computed by a person, a mechanical adder, or a silicon chip. Complexity theory studies which functions can be computed at all, and how much time and memory the fastest method needs.
Inputs, outputs, and functions
A computation realizes a function: it maps each input to at most one output. "Add two integers" and "is this number prime" are functions. The job of a model of computation is to say precisely which functions are realizable and at what resource cost.
Why a formal model is needed
Intuition about "following steps" is too vague to prove things with. To prove that some tasks are impossible or expensive, we need an exact model. The Turing machine is the standard choice because it is simple enough to reason about yet powerful enough to capture everything real computers can do.
- Determinism: the next step follows from the current configuration
- Finiteness: the rulebook is finite even when the input is arbitrarily large
- Discreteness: symbols and steps are countable, not continuous
Computation versus physics
Physical systems also "process" information, but not every physical process is a useful computation. A plasma evolves under Maxwell and fluid equations, yet extracting answers from it means simulating those equations on a machine. That is why understanding a fusion device such as the Hyperion breeder still reduces to hard computational problems, covered in the complexity of simulation.