Abstract:

 
The "programming approach" to Computability and Complexity has been
advocated, in particular, by Neil Jones in his 1997 book of a similar
title. His book, and other related work, motivated me to design a
course on the theory of computation around this approach, which I give 
at the Academic College. The purpose of this talk is to publicize the
principles of this approach and their benefits from both the theoretical and
pedagogical points of view.

The essence of the approach is that we consider computer programs as
the object of study, replacing as much as possible abstract models (notably
Turing's machine) that have dominated Computability and Complexity theory
in the past.
 
As I will show, while this brings the theory of computation closer to
software science, it does not incur any loss of mathematical precision;
in fact (with proper choices!) it often makes the precise consturctions
easier.  Moreover, we are sometimes led to sharper formulations and to improved
insight, obtained by the cross-breeding of ideas from the two branches
of Computer Science.