Can we compute everything?

-
Jonathan Ben-Artzi , Imperial College London
Fine Hall 314

It is often desirable to solve mathematical problems as a limit of simpler problems. However, are such techniques always guaranteed to work? For instance, the problem of finding roots of polynomials of degree higher than two was only solved in the 1980s (Newton's method isn't guaranteed to converge)! Doyle and McMullen showed that this is only possible if one allows for multiple independent limits to be taken, not just one. Theycalled such structures "Towers of Algorithms". In this talk I will apply this idea to other problems (such as computational quantum mechanics, inverse problems, spectral analysis), show that Towers of Algorithms are anecessary tool, and introduce the Solvability Complexity Index -- a measurement of the complexity of a given problem. An important consequence is that solutions to some problems can never be obtained as a limit offinite dimensional approximations (and hence can never be solved numerically). If time permits, I will mention connections with analogous notions in logic and theoretical computer science. This is joint work with Anders Hansen (Cambridge), Olavi Nevalinna (Aalto) and Markus Seidel (Zwickau).