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. |
| Resource type: this resource is a course. |
| 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
Textbooks
Free textbook:
- An Introduction to the Theory of Computation , by Eitan Gurari
This article is issued from Wikiversity - version of the Thursday, July 04, 2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.