Computability of Banach Space Principles
by
Vasco Brattka
FernUniversität Hagen

We investigate the computable content of certain theorems which are sometimes called the ``principles'' of the theory of Banach spaces. Among these the main theorems are the Open Mapping Theorem, Banach's Inverse Mapping Theorem and the Closed Graph Theorem. From the computational point of view these theorems are interesting, since their classical proofs rely more or less on the Baire Category Theorem and therefore they count as ``non-constructive''. However, it turns out that these theorems admit computable versions of a certain degree of uniformity. For instance, the computable version of Banach's Inverse Mapping Theorem states that the inverse T^-1 of a linear computable and bijective operator T from a computable Banach space to a computable Banach space is computable too, whereas the mapping T --> T^-1 itself is not computable. Thus, there is no general algorithmic procedure to transfer a program of T into a program of T^-1, although a program for T^-1 always exists. In this way we can explore the border between computability and non-computability in the theory of Banach spaces. As application we mention the effective solvability of the initial value problem of ordinary linear differential equations. If time permits, we will briefly discuss the non-linear and the linear but non-separable case.

Date received: June 21, 2002