Type-2 Computability Theory
Here a (Cauchy-) real number is considered as an infinite sequence of approximations by integer fractions up to prescribable absolute error. This conception underlies both constructive mathematics as well as Turing's 1937 correction to the 1936 paper that introduced the machine now carrying his name. Computing, say, $\pi$, exactly thus takes 'infinite' time - although in practice one may and usually will abort after reaching a desired output precision of, say, 10-10 trillion. Computing a real function $f$ means to output a sequence as above for $y=f(x)$ upon input of a corresponding sequence for $x$. This has been shown equivalent to several other natural conceptions of function computation. Of course any approximation to $y$ being output after finite time can depend only on some finite part of the sequence for $x$ - which requires any computable function to be continuous. In particular most characteristic functions are uncomputable, thus rendering decidability a useless notion of computability for sets. Instead, motivated for instance by approximate renderings of fractals like Mandelbrot's, a closed set is considered recursive iff its Euclidean distance function is computable. Note that the hyperspace of closed sets has cardinality of the continuum; and in fact most such (technically: all QCB) spaces can naturally be equipped with a notion of computability by representing their elements as infinite binary or integer sequences. This permits to investigate the computable content of classical theorems in functional analysis. Selected References:- K. Weihrauch: Computable Analysis, Springer (2000).
- A. Grzegorczyk: On the Definitions of Computable Real Continuous Functions, pp.61-77 in Fundamenta Mathematicae (1957).
- V. Brattka, P. Hertling, K. Weihrauch: A Tutorial on Computable Analysis, pages 425-491 in (S.B. Cooper, B.Löwe., A. Sorbi, editors) New Computational Paradigms, Changing Conceptions of What is Computable, Springer (2008).