This is a rigorous undergraduate course on the Theory of Computation, using the classic text "Introduction to the Theory of Computation" by Michael Sipser. The course covers machine models and languages defined by Finite State Machines, Context-Free Languages, and Turing Machines.
There are four major theorems (and their uses) that we will study during this course, providing complete proofs: the pumping Lemma for regular languages, used to show that there are languages that are not regular; the existence of a Universal Turing Machine; undecidability of the Halting problem; and Cook's...
Completion of the lecture on Godel's first incompleteness theorem.
Published 05/02/14
Godel's first incompleteness theorem, requiring minimal background. You only need to know what an integer is, what a function is and that a computer program is a finite series of statements written in some finite alphabet.
Published 05/01/14
Completion of the method to minimize the number of states in a DFA for any regular language. A by-product is a proof that the minimizing DFA is unique for any given regular language.
Published 02/10/12