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

[edit | edit source]

* COMP 2805 at Carleton University

## Lectures

[edit | edit source]

* 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

[edit | edit source]

## Textbooks

[edit | edit source]

Free textbook:

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

## Problem sets

[edit | edit source]

## Exams problems

[edit | edit source]