Theory Of Computing

Category: Computer Science Published: Saturday, 23 May 2015

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 By Sipser. This is a must have book in the library of any Computer Scientist. Highly recommended.

The following is a compilation of my solutions to assignments given in class.

Assignments


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


  1. Logic and Set Theory, taken from Professor John Watrous' Page
  2. Math for Computer Science
  3. Turing Machines Overview
  4. An example of a proof by structural induction
  5. Course Notes
  6. Notes on Reduction
  7. Regular Expressions, taken from Professor Mitsunori Ogihara's Page
  8. Convert NFA to DFA, taken from Professor John Watrous' Page
  9. Diagonalization, taken from Professor John Watrous' Page
  10. Halting Problem, taken from Professor Mitsunori Ogihara's Page
  11. Notes on Rice's Theorem, taken from Professor Luca Trevisan's Page
  12. Rice Theorem and Facts
  13. MidTerm Example Test
  14. Homeworks with solutions Example 1, taken from Professor Marvin K. Nakayama's Page
  15. 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.

Copyright © 2015 enriqueareyan.com.
All Rights Reserved. Joomla! is Free Software released under the GNU General Public License.