Syllabus
Enumerable functions, their properties, equivalence of their various mathematical definitions. Recursive and recursively enumerable sets and predicates.
Turing Machines' ability to compute all recursive functions. Recursive functions, primitive recursive functions, predicates and sets. Emulation of Turing Machine by primitive recursive functions and predicates. Kleene's theorems. Semirecursive predicates. Predicates that are not recursive. Predicates that are not semirecursive. Creative and simple functions.
Annotation
Enumerable functions, possible definitions, properties. Recursive and recursively enumerable sets and semirecursive predicates.
Time and space complexity.