Computation Theory: Syllabus

Purpose:  The purpose of the Computation Theory set of modules is to introduce the theory of computation.  We will accomplish this by working through the material of a mathematical nature.  This is the first in the theoretical portion of reverse engineering.


After you complete the Computation Theory modules you should be comfortable with the following:

  • Finite Automata.
  • Context-Free Languages
  • Decidability
  • Reducability
  • Complexity

Comfortable requires a definition when we are referring to theoretical topics.  I’m using comfortable in the sense that if you were to sit down with someone and have a conversation about these topics you could explain what they are and what you can do with them.  Or you could open a book that discusses them and follow along without too much effort.

Comfortable does not mean you’ve memorized everything and can recite each definition word for word.  It doesn’t mean that you don’t have to look things up either.  Comfortable means that when you read a definition or look something up you understand what it means.


The text for this series of modules is Introduction to the Theory of Computation by Michael Sipser.  Unfortunately this book is not free but you can pick it up used for a more reasonable price than a university course.


When it comes to theoretical material it is important to not just read.  When you’re going through these modules take notes on paper.  Try to do the exercises in the modules and change things to see what happens.  It can be a different way of doing things at first but once you’re used to it it becomes helpful.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s