Theory of Computation

Question

Hi, Can anybody please explain me use/importance of studying Theory of Computation.

I had course on the same subject during graduation but I did not study is seriouly.

I also found following link where some video lecture are available.

http://aduni.org/courses/theory/index.php?view=cw

Answer 1

The importance of Computation Theory will depend on what you do with your life. If you want to be a Computer Scientist, then it is an important basis for your future studies.

If you just want to be a Programmer or Software Engineer, then you will probably never use the knowledge again.

Answer 2

I think every computer science student should know some of computation theory, even you won't do any research.

Some concepts are just universal and you will encounter them again and again in other courses. E.g. finite state machines, you need to know them when you are learning string matching algorithms, and compilers. Another example, you will learn some reduction algorithms (transforming from one model to another model) in computation theory, these things teach you how to think abstractly and algorithmically.

Answer 3

The greatest of all human faculties is the power of abstraction. That is what separates us from the animal. The more we exercise this power the more successful we are in solving problems.

Playing Chess may seem a futile pastime to some and never of practical use to any but goes a long way to give the player the ability to think ahead every time an important decision is to be made.

Besides, it reveals the elegance and simplicity that is hidden beneath layers of ugly syntax and brain-dead code we sift through every day just to make a living.

Answer 4

Its really not without its practical aspects in regards to software engineering.

For example, you may be tempted to parse some programming language as input to your program with Regular Expressions. CS Theory proves why this is a bad idea (most programming language syntaxes are not Regular), and can never be overcome no matter how much you'd like to try.

Other examples may include NPC problems, etc.

Basically, CS Theory can teach you many important things with regards to reasoning. But it also describes the fundamental limits to programming and algorithms.

"Know your limits"

Answer 5

Shai Simonson's classes are really very good. I have listened to them. As he says in the initial lecture, 'Theory of Computation' is a study of abstract concepts. But these abstract concepts are really very important to better understanding of the field of Computing, as most of the concepts we deal with have lot of abstract and logical under pinnings. As John Saunders said in an above answer,you can become a programmer, even a good one if you know the programming language well. But the knowledge of what is going underneath will always makes you an enlightened one. So go ahead and learn it again (NB: I understand why you didn't study it seriously at college. Most of the teachers in our colleges aren't that good at explaining this topic (I too had a lousy teacher), but I assure you the teacher here is the best you can get,)

Answer 6

Theory of computation is sort of a hinge point among computer science, linguistics, and mathematics. If you have intellectual curiosity, then expose yourself to the underlying theory. If you just want to dip lightly into making computers do certain things, you can probably skip it. Me? I loved it. But I also liked topology, so I may not be a typical developer in that respect.

Answer 7

In addition to the usefulness of various tools (regular expressions, context free grammars, state machines etc.) in your daily life as a programmer, a good theoretical computer science course will have taught you how to model certain problems in a way that you can tackle effectively.

Solutions that seem clever to people without training in this discipline will seem natural and "the right way" to people who have. I recommend that you pay close attention to what's going on in your course since it will give you a very powerful toolset that will help you as a programmer and as an abstract thinker.

Answer 8

Some practical examples:

Before spending a lot of time on a problem you'll want to know:

• If the problem can't be solved.

• If there is a "good" (polynomial) solution, as some problems may don't have good" solutions (or at least, not ones we currently know of ;))

• (A bit less practical) you'll want to know if a problem is "harder" than other, that is, takes more time/space.