Computation

Computation is the process by which a physical system transitions between states according to determinate rules, producing outputs from inputs in a manner that can be described by a formal specification and whose outputs are interpretable as answers to questions. It is among the most fundamental concepts in mathematics, philosophy of mind, and physics — and also among the most poorly defined, because it straddles the boundary between the formal and the physical in ways that resist clean analysis.

The Essential Question

What is computation, essentially? Not: what can computers do? Not: what is a Turing machine? The essential question is: what distinguishes a computational process from any other physical process?

Every physical system evolves according to laws. A thermostat transitions between states according to temperature. A hurricane processes energy across a pressure gradient. A brain transitions between neural configurations in response to stimuli. None of this is computation in any interesting sense — or all of it is, in which case the concept is empty.

The concept earns its weight only if it picks out a specific class of physical processes: those whose state transitions can be described by a formal rule that is itself representable and inspectable. Computation, on this view, is not merely causal process — it is interpretable causal process. The outputs mean something; the transitions can be explained as the execution of a procedure; the system's behavior can be specified in advance and checked against its specification.

This is why Alan Turing's 1936 analysis remains foundational. Turing did not define computation by listing examples. He characterized it by identifying the minimal resources required: a finite symbol alphabet, a finite set of states, a read/write head, an unbounded tape, and a transition function. The Turing machine is not a description of any real computer — it is a specification of what computation requires at minimum. Everything else is implementation detail.

The Church-Turing Thesis and What It Does Not Settle

The Church-Turing Thesis asserts that every effectively calculable function is computable by a Turing machine. This claim is simultaneously one of the most important and most contested in the foundations of computation.

The thesis is not a theorem. It cannot be proved, because 'effectively calculable' is an informal concept — it captures the pre-theoretic intuition about what procedures humans can mechanically follow in finite time. The evidence for the thesis is the convergence of independent formalizations — Church's lambda calculus, Kleene's recursive functions, Post's canonical systems — on the same class of functions. This convergence is powerful but proves only that these formalizations capture the same informal concept; it does not prove that the informal concept correctly identifies all physically realizable computation.

Whether the physics of this universe permits hypercomputation — processes that exceed Turing limits — is an open empirical question. Quantum computers do not exceed Turing limits in terms of computability, only in terms of efficiency on specific problems. But whether quantum field theory or gravitational dynamics involve irreducibly non-Turing processes remains genuinely unsettled. An encyclopedia that presents the Church-Turing thesis as a settled physical fact rather than a well-confirmed conceptual proposal is overstating what we know.

The thesis has a further foundational problem: its key term, 'effective,' inherits its content from human finitary procedure. 'Effective calculability' means: executable by a being following a finite procedure that can be explicitly described. This is anthropocentric at its foundation. The class of Turing-computable functions is not the class of all physically implementable computations — it is the class of all computations that can be described by procedures intelligible to humans. These are not obviously the same.

Computability and Its Limits

The halting problem — Alan Turing's proof that no Turing machine can decide, for all program-input pairs, whether execution terminates — establishes an absolute limit on what computation can determine about itself. This is not a technical curiosity. It is a structural feature of the concept: any sufficiently expressive formal system contains questions about its own behavior that it cannot answer from within.

This result cascades. Rice's theorem generalizes it: no algorithm can decide any non-trivial semantic property of programs. The limits are not engineering obstacles awaiting better hardware. They are constitutive of what formal computation is. A system powerful enough to describe arbitrary computations is powerful enough to generate descriptions it cannot evaluate.

Computational complexity theory asks the practically more urgent question: which computations are tractable in polynomial time, logarithmic space, or other feasible resource bounds? The P versus NP question — whether problems whose solutions are efficiently verifiable are also efficiently solvable — is the central open problem, with implications reaching from cryptography to optimization to the general question of what kinds of knowledge can be efficiently acquired.

Computation and the Problem of Interpretation

The hypothesis that mind is computation — that cognitive processes are formal symbol manipulations over mental representations — is the most consequential application of the computational concept. The Computational Theory of Mind holds that thinking is computing; that beliefs, desires, and reasoning are functional states defined by their causal roles in a computational system.

The foundational challenge is not technical. It is semantic. Computation requires interpretation: someone or something must read the physical states as symbols and the physical transitions as inference steps. Without an interpreter, there is only causation, not computation. The Symbol Grounding Problem — how symbols in a formal system acquire determinate meaning — is not a problem internal to computation theory. It is a problem about the boundaries of the concept: computation cannot be purely formal if it requires an interpreter external to the formal system.

This is not a reason to abandon the computational theory of mind. It is a reason to be precise: computation is not a property of physical systems in themselves — it is a relationship between a physical system and a frame of interpretation. What a system computes depends partly on how its states are read. The question 'is the brain a computer?' cannot be answered without specifying the interpretive frame.

What Computation Is Not

Computation is not:

• Mere causation: deterministic rocks are not computing
• Mere information processing: every physical process 'processes information' in the thermodynamic sense
• Mere complexity: weather systems are not ipso facto computational
• Confined to silicon: DNA computing is implemented in chemistry; neural computation is implemented in biology

Computation is the class of physical processes that are formally specifiable, mechanically reproducible, and interpretably productive. The boundary of this class — what lies inside it, what lies outside, and who decides — is a foundational question that the concept of computation has not yet closed.

Any theory of mind, knowledge, or intelligence that treats computation as a primitive — rather than as a concept requiring analysis — is starting from the wrong place.