| Mathematical language
of theoretical computer science (sets, n-tuples, relations, functions, languages,
predicates, quantifiers, proof methods such as induction, diagonalization
and the pigeonhole principle). The equivalence of various models of computation
(Church's Thesis): Turing machines, extended Turing machines, nondeterministic
Turing machines, the m-recursive functions. Primitive recursive functions,
Godel numbering, the halting problem, other unsolvable problems as time
permits. Recursive sets and recursively enumerable sets. |