|
The Inversion Problem for Computable Linear Operators
Vasco Brattka, in: STACS 2003, Lecture Notes in Computer Science 2607,
391-402, Springer, Berlin 2003
Abstract
Given a program of a linear bounded and bijective operator T,
does there exist a program for the inverse operator T-1?
And if this is the case, does there exist a general algorithm
to transfer a program of T into a program of T-1?
This is the inversion problem for computable linear operators
on Banach spaces in its non-uniform and uniform formulation, respectively.
We study this problem from the point of view of computable analysis
which is the Turing machine based theory of computability on
Euclidean space and other topological spaces.
Using a computable version of Banach's Inverse Mapping Theorem
we can answer the first question positively.
Hence, the non-uniform version of the inversion problem is solvable,
while a topological argument shows that the uniform version is not.
Thus, we are in the striking situation that any computable linear
operator has a computable inverse while there exists no general
algorithmic procedure to transfer a program of the operator into
a program of its inverse.
As a consequence, the computable version of Banach's Inverse Mapping
Theorem is a powerful tool which can be used to produce highly non-constructive
existence proofs of algorithms. We apply this method to prove
that a certain initial value problem admits a computable solution.
© 2003 Springer-Verlag Berlin
Electronical Versions