CAN EVERYTHING BE COMPUTED?- ON THE SOLVABILITY COMPLEXITY INDEX AND TOWERS OF ALGORITHMS

ABSTRACT. This paper addresses and establishes some of the fundamental barriers in the theory of computation and finally settles the long standing computational spectral problem. Due to the barriers presented in this paper, there are many problems, some of them at the heart of computa-tional theory, that do not fit into the classical frameworks of theory of computation. Hence, we are in need for a new extended theory capable of handling these new issues. Many computational problems can be solved as follows: a sequence of approximations is created by an algorithm, and the solution to the problem is the limit of this sequence (think about computing eigenvalues of a matrix for example). However, as we demonstrate, for several basic problems in computations (computing spectra of infinite dimensional operators, solutions to linear equations or roots of polynomials using rational maps) such a procedure based on one limit is impossible. Yet, one can compute solutions to these problems, but only by using several limits. This may come as a surprise, however, this touches onto the definite boundaries of computational mathematics. To analyze this phenomenon we use the Solvability Complexity Index (SCI). The SCI is the smallest number of limits needed in order to com-pute a desired quantity. In several cases (spectral problems, inverse problems) we provide sharp results on the SCI, thus we establish the barriers for what can be achieved computationally. For example, we show that the SCI of spectra and essential spectra of infinite matrices is equal to three, and that the SCI of spectra of self-adjoin