Computing Traditions

During the last few decades two traditions of computing have grown and grown further apart.Firstly, there is the tradition of discrete computation. It has its roots in work in mathematical logic at the turn of the century involving the decidability of the arithmetic. Abstract computational devices such as the Turing machine and computability concepts such as recursive function are legacies of this tradition.Secondly, there is the long-standing tradition of algorithmics results in algebra and analysis which we will refer to as the numerical tradition. Algorithms such as Gaussian elimination or Newton's method and negative results such as Galois' theorem on the non-solvability by radicals of polynomial equations of degree at least 5 are legacies of this tradition.The arrival of the digital computer set a stage in which both traditions could meet. The need of feasibility in practice for computable functions brought along the need for a complexity theory. But while the discrete tradition was very successful at building such a theory, at the end of the 80's there was little akin to complexity theory within the numerical tradition.This difference in the theoretical foundations for both traditions is apparent in the 1989 SIAM's John von Neumann Lecture given by Steve Smale.The goal of this talk is to survey some advances towards the laying of foundations within the numerical tradition. We will assume that the audience is familiar with the discrete tradition and is not necessarily a trained numerical analyst. Hence, we will try to provide intuitions for the main concepts proper to the numerical tradition and the way they interrelate. We will also be more succinct when dealing with concepts common in the discrete tradition.