Important topics in the theory of computation

Question

During my studies at university I had to learn a lot about the theory of computation. I studied the subject for three terms. I had a hard time and I have to admit that I forgot a lot.

I am wondering whether this is a personal problem, or if we just had to learn a lot of (more or less) useless stuff.

So my question is: What topics in the field of the theory of computation do you think are most important, which parts are worth learning about, and which topics do you use during your normal work?

Personally, I am glad that I heard about the theory of languages (especially the regular languages => regular expressions - when they can be applied and when not) and about the different time (and space) complexities, in particular the O(n) notations.

But we had to study a lot more, including:

• computability theory
  • halting problem
  • semidecidable problems
• theory of complexity
  • p=np?
• theory of logic
  • propositional calculus
  • predicate logic

It was interesting to hear about these topics, but I am not sure how necessary it is to study them in depth.

I know this question is subjective and the answers will differ a lot depending on your day-to-day work and personal experience. But I'd like to know about topics that might be more interesting than I remember.

Answer 1

I'm not sure I directly use at work anything I learned in theory of computation classes. But I don't think that's really the point. I don't directly use anything I learned in Euclidean geometry in high school in life either. But that was the most important class I took in all of grade school.

Theory of computation is a really interesting topic and knowing it well can only help you in life. I can't prove that, but I know it's true.

Sorry if that's not much of an answer.

Answer 2

What topics in the field of the theory of computation do you think are most important

The question is vague. Important to who?

which parts are worth learning about?

All of them are worth learning about. This is a special case of the fact that all human endeavours are inherently worth learning about.

If your question is "which topics provide benefits to me larger than the cost of my time and effort to study them?" then that's a question that only you can answer for yourself. The benefit to me of studying, say, ancient Greek history, has nothing to do with how it affects my ability to get my job done.

Which topics do you use during your normal work?

I use all the topics you listed -- language theory, asymptotic order analysis, decidability, complexity theory, theorem-proving systems, and so on.

I don't use them in a formal sense; I am not sitting at my desk using the Master Theorem to derive order analysis for specific algorithms. I use them in the sense that it is very handy to be able to take a proposed language feature and work out quickly whether implementing it would require the compiler to solve a problem that is linear, polynomial, exponential, NP-hard, or equivalent to the halting problem.

For example, it is pretty easy to work out that overload resolution in C# 3 on nested lambdas is NP-hard, but not equivalent to the halting problem. We therefore know that (1) it is a waste of our time to even try to solve the problem in polynomial time, and (2) at least we know that a solution can be found in some amount of time, and (3) we could come up with simple heuristics to detect the bad scenarios and fail fast if we needed to.

I don't personally use proof systems much, though it is helpful to think about problems as a special case of a theorem prover. There are all kinds of language features that are equivalent to problems you throw at a theorem prover, particularly in the field of type inference and flow analysis. Fortunately none of the features of C# actually require implementation of a theorem prover; other languages implemented in this building do have that property, like F#.