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. Maximum of continuous function: not always. Intermediate value point: not computable. Surprising non-computabilities.

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.

Degrees of discontinuity: Computable discontinuous functions exist. Bounded limit computable. Hierarchy of discontinuity. Classification.

Symbols.

Symbol	Unicode	Meaning
Σ^ω	—	infinite sequences
δ	U+03B4	representation
≤_W	—	Weihrauch reduction
TTE	—	Type-2 effectivity

Metatheory. Type-2 computation. Representations. Reducibility. Discontinuity degrees.

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

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