DIKU, University of Copenhagen 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.

**Computation**
**C**OMPUTABILITY AND **C**OMPLEXITY FROM A **P**ROGRAMMING **P**ERSPECTIVE
**Introductory course**
**First week**
neil@diku.dk
**Course description**
**Prerequisites**
Mathematical maturity, ability to think precisely
**Literature**
No specific recommendation