 |
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
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
Handouts
Textbooks
Free textbook:
- An Introduction to the Theory of Computation , by Eitan Gurari
Problem sets
Exams problems
This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.