Theory Of Computing
This is a graduate level course being offered at Indiana University as part of the foundational requirements for MS/PhD. I took this course on Spring 2012 with Prof. Dirk Van Gucht. The book we use for this course was Introduction to the Theory of Computation
The following is a compilation of my solutions to assignments given in class.
Assignments
- Assignment 1 - [Solution]
- Assignment 2-1 - [Solution]
- Assignment 2-2 - [Solution]
- Assignment 3 - [Solution]
- Assignment 4 - [Solution]
- Assignment 5 - [Solution]
- Assignment 6 - [Solution]
The following is a compilation of resources I found useful while taking the course and thinking about this subject. These are not necessarily resources given in the course. Some of this I found online or compiled myself. Feel free to contact me if you would like to add a resource to this page or have any suggestions.
Resources
- Logic and Set Theory, taken from Professor John Watrous' Page
- Math for Computer Science
- Turing Machines Overview
- An example of a proof by structural induction
- Course Notes
- Notes on Reduction
- Regular Expressions, taken from Professor Mitsunori Ogihara's Page
- Convert NFA to DFA, taken from Professor John Watrous' Page
- Diagonalization, taken from Professor John Watrous' Page
- Halting Problem, taken from Professor Mitsunori Ogihara's Page
- Notes on Rice's Theorem, taken from Professor Luca Trevisan's Page
- Rice Theorem and Facts
- MidTerm Example Test
- Homeworks with solutions Example 1, taken from Professor Marvin K. Nakayama's Page
- Homeworks with solutions Example 2, taken from Professor Marvin K. Nakayama's Page
My take on the subject
The thing I found more interesting about Theory of Computing is not actually what in principle computers can do, but what they can't. This is the first serious, mathematically rigorous course that emphasizes the limitations of computing rather than focusing on the usual (seemingly) infinite capacity of modern computers. To really understand how to use a tool you not only need to know what can you do with it but also what you cannot. Any computer scientist that wants a more profound understanding of their field should really take a course of this nature. The main results is to understand the halting problem. The main tool to do so is to use diagonalization, a proof technique invented by Cantor.