The alchemists wanted to create gold, Hilbert wanted an algorithm to solve Diophantine equations, researchers want to make deep learning robust in AI, MATLAB wants (but fails) to detect when it provides wrong solutions to linear programs etc. Why does one not succeed in so many of these fundamental cases? The reason is typically methodological barriers. The history of science is full of methodological barriers — reasons for why we never succeed in reaching certain goals. In many cases, this is due to the foundations of mathematics. The Solvability Complexity Index (SCI) hierarchy provides a foundations programme that determines the boundaries of what computational mathematics can achieve in different fields including optimisation, artificial intelligence (AI), computational quantum mechanics, computer assisted proofs, computational PDEs, inverse problems etc. For example, one can answer long standing questions such as:
• Can one design an algorithm that computes spectra of Schrodinger operators and never makes a mistake?
• Is it possible to quickly solve linear programs accurately with irrational inputs — that is — can this be done in polynomial time in the number of variables and correct digits in the solution (the extended Smale’s 9th problem)?
Or current questions such as:
• If one can prove that neural networks exist with great approximation qualities in deep learning, can they be computed by an algorithm?
• Can one detect when modern AI algorithms make mistakes?
• Why does commercial software such as MATLAB and MOSEK fail to detect when when they provide wrong solutions to basic optimisation problems?
• Can one find an algorithm for semidefinite programming (SDP) that is 100% reliable so that it can be used in computer assisted proofs in pure mathematics?
In this talk we will use these examples to explore the wonderful world of the mathematics of “why things don’t work” and to understand why — occasionally — things do work.