|
The theory of general purpose programming systems.
Recursive and partial-recursive functions;
recursive and recursively enumerable sets.
The Church-Turing thesis.
The recursion theorem, Rogers' translation theorem,
Rice's undecidability theorem.
The general theory of computational complexity:
there are no general solutions to natural optimization problems.
Complexity for specific models of computation:
the polynomial complexity classes P, NP, and PSPACE;
NP-hard and PSPACE-hard problems, inherently exponential problems.
|
