Computability

A Standard Turing Machine that emulates a Nondeterministic one

Summary

Very nice course! Here are the notes (handwritten).

Coverage

  • Turing Machines (standard, with/without final state(s), multitape, multitrack, single-way, multiway) and their equivalences.
  • Nondeterministic Turing Machines and their equivalence with standard Turing Machines (see also image).
  • Recognizing/deciding a language
  • Macros
  • Turing-computable number-theoretic functions,
  • Primitive recursive functions, bounded minimization

Mu recursion is somehow not included in this summary.

Matthijs Muis
Matthijs Muis
Double BSc student in Mathematics and Computer Science