I like to think of this class as the study of two questions:
The textbook we will be using is the Introduction to the Theory of Computation by Michael Sipser. I have a hard copy of the first edition, but I think the third edition is the newest. When I was taking this class, I didn't really like the book. I wanted to be taken seriously, and I thought the book held my hand too much. As I grew up I realized that this book is actually amazing. In a course like this, I would recommend you just start reading through the book until you get stuck. It practically reads itself to you. It makes really hard topics very easy and understandable. I may reference other material from other sources.
This class has some large number of prerequisites, most of which I disagree are nessessary. All that you really need for this class is strong mathematical maturity. This is mostly unlike any course you have taken before.
The material for this class is pretty laidback, but I don't mind to make you sweat a bit.
|1-1||Introduction, DFAs and NFAs||notes|
|1-2||Closure and Regular Expressions||notes|
|2-1||Regexes are Regular, and the Pumping Lemma||notes|
|2-2||Myhill Nerode Theorem||notes|
|3-1||Regular and Context Free Grammars||notes|
|3-2||Chomsky Normal Form||notes|
|4-1||The Pumping Lemma for CFLS & Closure||notes|
|5-1||Every CFG has a PDA||notes|
|6-1||The Church-Turing Thesis||notes|
|7-2||The Halting Problem||notes|
|8-1||Some Decidable Problems||notes|
|9-1||Context Sensitive Languages & Computation Histories||notes|
|9-2||Post Correspondence Problem||notes|
|10-2||The Recursion Theorem||notes|
|11-2||Busy Beavers and Kolmogorov Complexity||notes|
As a member of the Georgia Tech community, I am committed to creating a learning environment in which all of my students feel safe and included. Because we are individuals with varying needs, I am reliant on your feedback to achieve this goal. To that end, I invite you to enter into dialogue with me about the things I can stop, start, and continue doing to make my classroom an environment in which every student feels valued and can engage actively in our learning community.