Computability of solutions of operator equations
Volker Bosserhoff · Mathematical logic quarterly · 2007
Abstract We study operator equations within the Turing machine based framework for computability in analysis. Is there an algorithm that maps pairs (T,u) (whereTis given in form of a program) to solutions ofTx=u? Here we consider the case whenTis a bounded linear mapping between Hilbert spaces. We are in particular interested in computingthe generalized inverse T†u, which is the standard concept of solution in the theory of inverse problems. Typically,T†is discontinuous (i. e. the equationTx=uisill‐posed) and hence no computable mapping. However, we will use effective versions of theorems from the theory ofregularizationto show that the mapping (T,T*,u, ‖T†u‖) ↦T†uis computable. We then go on to study the computability ofaverage‐case solutionswith respect to Gaussian measures which have been considered ininformation based complexity. Here,T†is considered as an element of anL2‐space. We define suitable representations for such spaces and use the results from the first part of the paper to show that (T,T*, ‖T†‖) ↦ T†is computable. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)