Can we compute everything?

Carte non disponible

Date(s) - 13/10/2015
11 h 00 min - 12 h 00 min


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 three 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. They called 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 a necessary 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 of finite 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.

Joint work with Anders Hansen (Cambridge), Olavi Nevalinna (Aalto) and Markus Seidel (Zwickau).

Posts created 14

Articles similaires

Commencez à saisir votre recherche ci-dessus et pressez Entrée pour rechercher. ESC pour annuler.

Retour en haut
Secured By miniOrange