The aim of this course is to present the fundamentals of computability theory and computational complexity theory in a rigorous yet accessible way. Computability theory was one of the most beautiful and important developments of the 20th century mathematics, a development that is fundamental to many disciplines, including computer science, cognitive science, computational linguistics and artificial intelligence. Computational complexity theory, a daughter science of computability theory, is every bit as fundamental, and it too has important ramifications for these disciplines. But while there are many superb introductions to these subjects, they are both topics whose mastery requires a certain amount of mathematical maturity.
The aim of this course is to provide the necessary mathematical background for understanding these subjects, and then to present their fundamental concepts and results. We focus on the mathematical essentials, and motivate the keys concepts in a number of ways: historically, conceptually, and logically. It is our hope that after taking this course you will have a stronger mathematical skills (and in particular, a deeper understanding of what a mathematical proof is, and how to do them) a thorough understanding of fundamental results in computability and computational complexity and their relation to logic, and an appreciation of what these results have to say to computer science, computational linguistics, cognitive science, and and related disciplines.
Patrick Blackburn INRIA
Address: INRIA Nancy Grand-Est Equipe TALARIS, Batiment B 615, rue du Jardin Botanique 54602 Villers lès Nancy Cedex, France