Theory of Computation
Automata, Turing machines, computability, and complexity.
0/5 complete
- Finite AutomataDFAs and NFAs — the simplest model of computation, with finite memory and no tape.easy
- Regular ExpressionsA pattern algebra for the regular languages — provably equivalent to finite automata.easy
- Turing MachinesAn unbounded tape, a movable head, and a transition function — the model of all computation.medium
- Computability and the Halting ProblemSome problems no algorithm can ever solve — proved by diagonalization and the halting problem.hard
- Complexity Classes — P, NP, and NP-CompletenessAmong the decidable problems, which are tractable? Verifying versus solving, and the P vs NP question.hard