Introduction to the Theory of Computation: Prologue

Welcome everybody,

In an old tweet, I asked if anyone would be interested in blog posts explaining theoretical computing and the theory of computation. Although around 10 people only reacted to the tweet, I still decided to go on and start a series of blog posts explaining the matter.

The reason why I chose to do so is that, aside from being very important to understand for those majoring in CS, the theory of computation is a very interesting subject that will help the readers further expand their knowledge and understanding of how computers work at the very basic level.

Curriculum

The curriculum we will be following in order to deeply and thoroughly explain the fundamentals of the theory of computation is that included in the book dubbed “Introduction to the Theory of Computation”, written by Michael Sipser.

I will be explaining the chapters one by one in separate blog posts, and maybe divide a chapter into more than one blog post if it was found to be lengthy or mind consuming for the readers. Now, let’s start with the very first part of the book, where we briefly go over a simple overview of what’s actually covered under this course.

Automata, Computability, and Complexity

Those are the three main parts the book is concentrating on explaining and discussing, they can be grouped under the following question:

What are the fundamental capabilities and limitations of computers ?

Mathematicians have started researching into answering the above question since 1930, and since then computers have significantly advanced and helped bring the question out of the theoretical world and into the practical world.  The question can be answered and interpreted differently in each of these three areas, which will be covered throughout the course.

Complexity Theory:

Computer problems can be either easy or hard to solve. For example, the sorting problem is not as hard as the scheduling problem. Say that you have a million numbers that you want to sort in either ascending or descending order, this can be done by a regular computer in a relatively timely manner. But if we try to schedule a thousand classes into one timetable, considering some rules such as no two classes exist at the same time in the same room and that an instructor teaching two courses can’t exist in two classrooms simultaneously, this appears to be of much greater difficulty to calculate. In fact, a super computer would require centuries to determine an answer to that particular scenario. The following question is the main question asked when it comes to the complexity theory:

What makes some problems computationally hard and others easy ?

Although it may look like an easy question, computer scientists still don’t have a complete answer to that question so far. However, they were able to at least classify computer problems according to how computationally difficult they are, which allows us to find a way to give evidence that a problem is computationally hard although we don’t have the ability to prove so.

There are different approaches to be followed when one stumbles upon a problem that is computationally hard to solve. First, if the root of the problem can be clearly determined, some alteration to that root may result in reshaping the problem into an easier form that can be computed faster to solve the main problem. Second, if the first approach is out of hand, sometimes finding an approximate solution for the problem may do in relation with the main problem. Third, some problems are only hard to compute in their worst case scenario, and are easily computed in normal cases, which may be acceptable for some if they have no problem running slow sometimes but fast most of the time. There are also other ways, such as considering different types of computation, such as randomized computation.

An application that most of the readers can relate to is Cryptography. Unlike most of the cases, where we always seek to employ easier computational problems rather than harder ones because they are easier to solve, Cryptography seeks to employ hard problems as it’s main aim is to produce strings that are often unbreakable, or at least very costly to break. This can be easily illustrated in the bruteforcing process of a password, where we observe that a password that is 5 characters long would take much lesser time to bruteforce than another that is 7 characters long.

Computability Theory

Mathematicians such as Alan Turing, Alonso Church, and Kurt Gödel have discovered that certain basic problems cannot be solved by computers. For example, although a purely mathematical problem, determining whether a mathematical statement is true or false cannot be solved by a computer. An outcome of researching this area was the development of theoretical models of the computers we are using in modern times, such as Turing Machines and Finite Automata.

Complexity and computability theories are closely related. In short, the complexity theory is the one concerning the research in order to determine how computationally hard a problem is, whereas the computability theory is all about determining whether a problem can be computationally solved in the first place.

Automata Theory

This last part deals with how we define a mathematical model of a computer that are used in many areas of computer science. One model that I just mentioned is the Finite Automaton, which is used in text processing and compiler design. Another is Context-Free Grammar, which is used in designing programming languages.

From this theory, we will begin understanding the theory of computation. This is because the complexity and computability theories need to first define what a “computer” is, which we will go through by studying the automata theory.

With this we would come to the end of the first blog post in the series of the theory of computation. See you in the next post, where we will be going over some mathematical notions and basic terminologies.

Please leave your comments if anything is not clear enough or needs further explanation, Twitter DMs are available as well.

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s