Computable Analysis

Origin. Turing's computable reals (1936); Grzegorczyk (1955) and Lacombe (1955) independently gave the computable real functions; Pour-El and Richards, Computability in Analysis and Physics (1989); Weihrauch, Computable Analysis (2000), which established TTE as the standard framework. Computability on reals. TTE (Type-2 Theory of Effectivity). Computable real functions. Foundation of exact real computation.

Models. Reals as infinite sequences. Computable = Turing machine on sequences. Type-2 machines. Represented spaces. Algorithmic real analysis.

Formalism.

Computable real: x computable iff Turing machine outputs sequence of rationals converging to x. With known convergence rate. Infinite output.

Representation: δ: Σ^ω → X (representation of X). Names in Σ^ω (infinite strings). Named element: δ(p) = x. Multiple names possible.

Computable function: f: X → Y computable iff exists TM M: δ_X(p) = x implies δ_Y(M(p)) = f(x). Transforms names. Type-2 computation.

Non-computability examples: Equality on reals: not computable. Nor is the ordering x < y, nor the test x = 0. Maximum of a computable function on [0,1]: the value max f is computable — a computable f on a computable compact set has a computable modulus of uniform continuity, so a fine enough grid bounds the error. It is the argmax that is not computable, since it jumps when two peaks trade places. Intermediate value point: not computable in general. The root is computable when f changes sign simply; the failure is for functions that graze zero, where the choice of which root to return is discontinuous. None of these is really surprising once the main theorem below is in hand.

Weihrauch reducibility: f ≤_W g: f reducible to g. g solves f via computable transformations. Measures computational difficulty. Classification tool.

Represented spaces: (X, δ) = space + representation. Category of represented spaces. Morphisms = computable functions. Systematic framework.

Main theorem — computable implies continuous: Every computable function between represented spaces with admissible representations is continuous. There are no computable discontinuous functions; that is the central structural fact of the subject, not an incidental one. The reason is finite-information: a Type-2 machine has written finitely much output after finitely many steps, so it has committed to a neighbourhood of the answer on the strength of a finite prefix of the input, and that is exactly continuity. Classically this is Ceitin's theorem and Kreisel–Lacombe–Shoenfield; in TTE it falls straight out of the machine model.

Every non-computability above follows from it. Equality on ℝ, the argmax, the IVT root — each is a discontinuous assignment, so continuity alone rules them out before any computability argument begins. The surprise is not that they are uncomputable but that so much else is not.

Degrees of discontinuity: Since discontinuity is the obstruction, discontinuous problems are classified by how discontinuous they are. Weihrauch degrees do this: LPO (deciding x = 0), LLPO (choosing a side), and lim (the limit operator) are the standard milestones, and lim characterizes exactly the limit-computable functions — those computable with finitely many mind changes, equivalently computable relative to the halting problem. Hierarchy of discontinuity, indexed by the Borel/effective-Borel level of the problem.

Symbols.

Metatheory. The framework's central theorem is that computability implies continuity: a function between admissibly represented spaces is computable only if it is continuous, because a Type-2 machine has committed to a neighbourhood of its answer on a finite prefix of the input. Kreisel, Lacombe and Shoenfield (1957) and Ceitin (1962) had already proved the corresponding fact in the Russian school setting, where effective operations on constructive metric spaces are continuous. Grzegorczyk (1955) and Lacombe (1955) independently showed the standard candidate definitions of a computable real function agree, and that a computable function on a computable compact set has a computable modulus of uniform continuity. Specker (1949) exhibited a computable increasing bounded sequence of rationals whose limit is not a computable real, so computability is not closed under limits; Myhill (1971) gave a computable continuously differentiable function on [0, 1] whose derivative is not computable; Pour-El and Richards (1981) found computable initial data for the three-dimensional wave equation whose unique solution at time one is not computable. The Weihrauch degrees order these failures, with lim characterizing the functions computable relative to the halting problem.

Applies to. Exact real computation. Analysis algorithms. Foundations. Complexity.

Limitations. No discontinuous function is computable, so equality and order on ℝ, the sign test, and every argmax or root-selection that jumps are excluded outright rather than merely expensive — an algorithm that branches on a real comparison is outside the model, and the constructive workaround is a decision only up to a tolerance. Everything is relative to a representation, and the choice is not free: decimal or binary expansion is not admissible for ℝ, and under it even multiplication by three fails to be computable, which is why Cauchy names with a modulus are used instead. Only spaces admitting an admissible representation are in scope — second-countable and T₀ — so non-separable spaces such as ℓ^∞ and general Banach spaces fall outside, and much of functional analysis with them. The computable reals are countable, so the theory speaks about a measure-zero subset of ℝ. The base theory carries no resource bounds; complexity requires the separate second-order framework of Kawamura and Cook.

© 2026 Lingenic LLC