Introduction to Theory of Computation

Educational level: this is a tertiary (university) resource.

Completion status: this resource is a stub, so not much has been done yet.

Subject classification: this is a mathematics resource.

Subject classification: this is an information technology resource.

Alan Turing (1912 – 1954) was a major figure in early computer science. He was an early thinker about artificial intelligence -- his famous paper "Computing machinery and intelligence" presented the Turing Test for detecting strong AI. Also, relevant to this course, he developed the idea of a Turing machine as the fundamental mathematical description of an algorithm. This memorial to Alan Turing can be seen at Bletchley Park.

Lecture notes

• COMP 2805 at Carleton University

Lectures

• Finite State Machines
• Closure and Nondeterminism
• The Pumping Lemma
• Minimizing FSMs
• Recitation 1
• Context Free Languages
• CFLs and compilers
• Recitation 2
• Pushdown Machines
• Recitation 3
• CFGs and NPDMs
• More lemmas, CYK algorithm
• Undecidability and CFLs
• Recitation 4
• The Bullseye (Hierarchy of Languages)
• Turing Machines
• Recitation 5
• The Halting Problem
• Decidability
• Complexity Theory, Quantified Boolean Formula
• Savitch's Theorem, Space Hierarchy
• Decidability/Complexity Relationship, Recursion Theorem

Textbooks

Free textbook:

• An Introduction to the Theory of Computation , by Eitan Gurari