Foundations of Computing

Mathematical Background/Definitions
–    Problems/Solving Problems
–    Computational Models
–    Algorithms/Procedures

Computability Theory
–    Unlimited Register Machine (URM)
–    URM-Computability
–    Partial /Primitive Recursive Primitive Functions
–    Computable Functions

Other approaches to Computability
–    Turing Computability
–    Other Model’s Computability
–    Church-Turing’s Thesis

Computational Complexity Theory
–    Time Complexity: the classes P and NP
–    Space complexity: Savitch’s theorem, PSPACE
–    Intractability: hierarchy theorems; exponential space completeness