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. Type-2 computation. Representations. Reducibility. The main theorem — computable implies continuous — is what makes discontinuity the right measure of difficulty, and the Weihrauch degrees the right classification.

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

Limitations. Infinite objects. Model dependency. Representation sensitivity. Technical depth.

© 2026 Lingenic LLC