Computability of Solutions of Operator Equations

We study operator equations within the Turing machine based framework for computability in analysis. Is there an algorithm that maps pairs (T,u) (where T is given in form of a program) to good approximate solutions of Tx=u? Here we consider the case when T is a bounded linear mapping of Hilbert spaces. We are in particular interested in computing the generalized inverse T†u which is the standard concept of solution in the theory of inverse problems. Typically, T† is discontinuous (i.e. the equation Tx=u is ill-posed) and hence no computable mapping. However, we will use effective versions of theorems from the theory of regularization to show that the mapping (T,T∗,u,‖T†u‖)↦T†u is computable. We then go on to study the computability of average-case solutions with respect to Gaussian measures which have been considered in information based complexity. Here T† is considered as an element of an L2-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†‖L2)↦T† is computable.