Computation	COMPUTABILITY AND COMPLEXITY FROM A PROGRAMMING PERSPECTIVE
Introductory course	NEIL D. JONES DIKU, University of Copenhagen
First week	neil@diku.dk
Course description	Central results in computability and complexity theory will be defined, established and proven from a programmer-oriented perspective. The first part concerns establishing which problems CAN and CANNOT be solved in any way at all, using computers. The second part studies which problems can and cannot be solved within given limits on computational resources such as memory space and running time. For example, it will be proven that there exist problems that, while solvable, cannot be solved efficiently, REGARDLESS of how clever one is at programming or mathematical analysis. In addition to giving more natural definitions, proofs and perspectives on classical theorems by Cook, Hartmanis, Savitch, etc., some new results come from the programming approach. One is that for a computation model more natural than the Turing machine, multiplying the available problem-solving time provably increases problem-solving power ({\em not true} for Turing machines). Another is that the classes of decision problems LOGSPACE and PTIME (from the famous P=NP? question) will be characterised by CONS-free programs on Lisp-like lists.
Prerequisites	Mathematical maturity, ability to think precisely
Literature	No specific recommendation