Saturday, August 29, 2009

Theory of Computer Science - what is that?

We all know that computers solve problems. However, computers can only solve certain kinds of problems. They can't solve all of our problems! Even if we have unlimited processor speed and memory, there are still problems that can not be solved by a computer.

The Theory of Computer Science is the study of problems and the solutions to problems. The first line of business is to provide a set of mathematical abstractions for classifying and solving problems.

Let me clarify what I mean by a mathematical abstraction. One example is a PDA (Pushdown Automaton). Another example is a FSM (Finite State Machine). Here is a picture of a FSM.



This FSM is taken from Elaine Rich's book, Automata, Computability, and Complexity. If you look at the picture you will see some circles. These are states. We have state 1, 2, and 3. Some of the circles are two circles in one. These are acceptance states. As input the FSM takes a string. For example, lets put abbba into the FSM. The start state is state 1, because it has an arrow pointing into it that does not come from another state. So, the input {a} causes us to stay at state 1 because the arrow leaving state 1 with an {a} on it points back to state 1. The next input is a {b}. This causes us to move to state 2. Then we enter two more {b's} causing us to loop back to state 2 a few times. Lastly, we enter a final {a}, which causes us to move to state 3. State 3 is not an accept state. Recall that only the states with two circles are accept states. So, this means that the FSM above does not accept the string abbba. What strings would it accept? What strings would it not accept? Basically, this FSM accepts any string that does not have the pattern {ba} in the string.

I want to return to my point that FSM's are mathematical abstractions. There are many of these sorts of mathematical abstractions introduced in the theory of computer science. I wanted to give you a concrete example, but my main point is that the theory of computer science gives readers a set of mathematical abstractions for classifying and solving problems. The FSM is one and their are others. TCS (Theory of Computer Science) splits problems into groups based on which mathematical abstraction can be used to solve the problem.

Each mathematical abstraction (also known as a machine) coresponds to a language class. A language class is a grouping of strings that are members of the language. So, in our example above, the language accepted by the FSM are all strings that do not have a {b} that is followed by an {a}. Examples of strings that are accepted are: aaaaaabbbbbbbb, ab, bbbbbb, ab and the empty string. The empty string is accepted because state 1 is an accept state. The strings aba, abbbbabbbb, bbbba, and ba are all rejected by the FSM above.

Machines and languages are in a hierachy. FSM's are the most basic. For more intense problems, a Pushdown Automaton must be used. For problems too complex for a pushdown automaton a Turing machine must be used. If a language can be accepted or decided by a certain machine (aka mathematical abstraction) then it is placed in that category of languages. Regular languages can be accepted by FSM's. Context-free languages can be accepted by Pushdown Automatons. Decidable languages can be decided by turing machine's that always halt. Lastly, Semidecidable languages can be semidecided by turing machine's that halt on any string from the language.

The main idea for this post is to introduce the topic of the Theory of Computer Science. In conclusion, problems are classified into groups. This is accomplished by encoding individual problems into specific languages of strings. Mathematical abstractions are created and the languages are either able to be accepted by the machine or not. If a problem is able to be accepted by a certain machine then the problem is classified in that category of languages. Finally, some problems can not be solved by any of the theoretical machines. It can be shown that if a problem can not be encoded into a language of strings that can be accepted by a turing machine then it can not be solved by a computer.

I will write more posts soon to explain these different machines and languages.

Note: I am reading Elaine Rich's book, Automata, Computability, and Complexity. These are some of my notes and thoughts after reading chapters one, two, and three. All credit goes to her book for these notes.

No comments: