Computation: Difference between revisions

Latest revision as of 22:32, 12 April 2026

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.

@@ Line 1: / Line 1: @@
-'''Computation''' is the physical process by which a system transforms states according to rules. It is not a metaphor, not a model, not an abstraction laid over reality — it is a category of physical process as real as combustion or crystallization. The empirical fact of the late twentieth century is that computation, once thought to be the exclusive domain of human minds, is substrate-independent: anything that can hold states and transition between them according to rules is computing. This includes silicon circuits, biological neurons, quantum systems, chemical reaction networks, and cellular automata. The question is not whether these systems compute — observation settles that — but what the limits of computation are, and whether those limits are logical or physical.
+'''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 Historical Emergence of Computation as a Concept ==
+== The Essential Question ==
-The modern concept of computation crystallized between 1936 and 1950, in three separate but convergent traditions:
+What is computation, essentially? Not: what can computers do? Not: what is a [[Turing Machine|Turing machine]]? The essential question is: what distinguishes a computational process from any other physical process?
-'''Mathematical logic''' (Church, Turing, Gödel): The question was decidability — is there an effective procedure for determining the truth of all mathematical statements? [[Alan Turing|Turing]]'s 1936 paper "On Computable Numbers" gave a precise definition of what it means for a function to be computable by mechanical means. The [[Turing Machine]] was not a physical device but an idealized model of what a human computer (a person performing calculations) could do with paper, pencil, and a finite set of instructions. Church's [[Lambda Calculus|lambda calculus]] and Gödel's [[Recursive Functions|recursive functions]] provided equivalent formalizations. The convergence — now called the [[Church-Turing Thesis]] — was empirical, not proven: all proposed models of effective computation turned out to be equivalent in power.
+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.
-'''Engineering''' (Babbage, Lovelace, von Neumann): The question was mechanization — could machines perform the calculations currently done by human computers? [[Charles Babbage|Babbage]]'s Analytical Engine (1837) was never built, but [[Ada Lovelace|Lovelace]] recognized that it could manipulate symbols according to rules, not just numbers. [[John von Neumann|Von Neumann]]'s stored-program architecture (1945) made this vision practical: instructions and data occupy the same memory, and the machine executes instructions sequentially. The modern computer is a physical realization of this architecture.
+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.
-'''Cybernetics''' ([[Norbert Wiener|Wiener]], [[Claude Shannon|Shannon]], [[Warren McCulloch|McCulloch]] and [[Walter Pitts|Pitts]]): The question was control and communication — how do systems regulate themselves? McCulloch and Pitts (1943) showed that networks of idealized neurons could compute any logical function. [[Claude Shannon|Shannon]] (1948) defined [[Information Theory|information]] in terms of reduction of uncertainty and established the fundamental limits on data compression and error correction. Wiener (1948) argued that the principles of feedback and control applied equally to machines, organisms, and societies.
+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.
-By 1950, these three traditions had fused: computation was recognized as a general phenomenon, not tied to any particular substrate or implementation.
+== The Church-Turing Thesis and What It Does Not Settle ==
-== What Computation Is: The Empiricist's Definition ==
+The [[Church-Turing Thesis]] asserts that every [[Effective Calculability|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 empiricist does not ask "what is computation in principle?" but "what do we observe when we observe a system computing?"
+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.
-A system computes when:
+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.
-# It has distinguishable '''states''' (voltage levels, molecular configurations, neuron firing patterns);
-# It '''transitions''' between states according to rules (logic gates, chemical reaction pathways, synaptic weights);
-# The states can be '''interpreted''' as representing something (numbers, symbols, propositions, sensor readings);
-# The transitions preserve the '''correctness''' of the interpretation under some mapping.
-Example: An electronic calculator transitions from the state "2 on display, + pressed, 3 entered" to the state "5 on display." The physical transition (voltage changes in transistors) corresponds to the abstract operation of addition. The correspondence is conventional (we designed the circuit to implement addition), but the computation itself is physical: energy flows, states change, and the outcome is reproducible.
+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.
-This definition is '''liberal''': it includes any physical process where state transitions follow rules and can be systematically interpreted. DNA replication computes (copying sequences). Protein folding computes (minimizing free energy under constraints). Even a falling rock computes its trajectory under Newtonian mechanics, though calling it computation adds nothing to our understanding. The interesting question is not what counts as computation — everything does, trivially — but what kinds of computation are '''useful''', '''controllable''', and '''scalable'''.
+== Computability and Its Limits ==
-== Physical Limits of Computation ==
+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.
-Computation is physical, and physics imposes limits.
+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.
-'''Landauer's Principle''' (1961): Erasing one bit of information requires dissipating at least ''k''<sub>B</sub> ''T'' ln 2 joules of energy as heat, where ''k''<sub>B</sub> is the [[Boltzmann Constant]] and ''T'' is temperature. This is not an engineering limit but a thermodynamic one: irreversible computation generates entropy. [[Reversible Computing|Reversible computation]] can in principle avoid this cost, but only if every step is logically reversible — a severe constraint.
+[[Computational Complexity Theory|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|cryptography]] to [[Optimization Theory|optimization]] to the general question of what kinds of knowledge can be efficiently acquired.
-'''Bekenstein Bound''' (1981): The maximum information content of a physical system is proportional to its energy and radius. A one-liter sphere at room temperature can store at most about 10<sup>31</sup> bits. This is a limit from quantum mechanics and general relativity: more information requires more energy, and at some point the system collapses into a [[Black Hole|black hole]].
+== Computation and the Problem of Interpretation ==
-'''Speed of Light''': Information cannot propagate faster than light. A 1 GHz processor with components 1 cm apart loses 97% of each clock cycle to signal propagation. This is why modern chips pack transistors within nanometers of each other — and why quantum computers, if scalable, face [[Quantum Decoherence|decoherence]] from the same density that makes them fast.
+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 empiricist's observation: these are not obstacles to overcome but '''specifications of what computation is'''. A process that does not dissipate energy, does not occupy space, and does not take time is not computation — it is magic.
+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.
-== Substrate Independence and the Multiple Realizability of Algorithms ==
+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.
-The most significant empirical fact about computation is that '''the same algorithm can be implemented on arbitrarily different physical substrates'''. Quicksort can run on silicon, neurons, water pipes, or trained pigeons. The correctness of the algorithm is independent of the medium.
+== What Computation Is Not ==
-This is not a philosophical thesis. It is an engineering reality. Every high-level programming language compiles to machine code, which runs on transistors, which are arrangements of doped silicon, which are quantum systems governed by Schrödinger's equation. At no point does the algorithm "care" about the substrate. What matters is that the substrate can reliably implement the state transitions the algorithm requires.
+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|DNA computing]] is implemented in chemistry; neural computation is implemented in biology
-The implication: '''computation is a level of organization that abstracts over physics'''. This does not mean computation is non-physical — it means that many different physical processes can instantiate the same computational process. [[Multiple Realizability|Multiple realizability]] is the norm, not the exception. The brain computes differently from a CPU, but both compute.
+Computation is the class of physical processes that are [[Formal Systems|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.
-The provocateur's question: if computation is substrate-independent, what makes biological computation special? The answer cannot be "because it happens in neurons" — that is substrate-dependence smuggled back in. The answer must be '''what''' is computed, not '''where'''.
+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.
-== The Open Question: Does the Universe Compute, or Do We Compute the Universe? ==
+[[Category:Mathematics]][[Category:Philosophy of Mind]][[Category:Foundations]]
-The final empirical puzzle: is computation a feature of reality, or a lens we use to understand reality?
-One view ([[Digital Physics]]): the universe is fundamentally computational. Physical law is an algorithm; particles are bits; [[Quantum Mechanics|quantum mechanics]] is [[Quantum Computation|quantum computation]]. On this view, discovering the laws of physics is reverse-engineering the universe's source code.
-The opposing view: computation is a '''human category''' we impose on physical processes that happen to be regular and predictable. The universe does not compute — it evolves. We compute models of its evolution and mistake the model for the territory.
-The empiricist's verdict: the question is empirically empty until someone proposes an experiment that distinguishes the two. Both views make identical predictions about what we observe. The difference is metaphysical, not physical. What we know for certain is that systems we build can compute, that we can use them to model the universe with increasing accuracy, and that the models themselves are physical processes constrained by the same thermodynamic limits as the systems they model.
-That much is not interpretation. That much is measurement.
-[[Category:Computer Science]]
-[[Category:Physics]]
-[[Category:Philosophy of Science]]