I would like to know whether knowledge of the theory of computation can help you to be a better practitioner. Is it enough to obtain some depth of knowledge of algorithms and data structures, or would it help to also know automata (for compilers, types, programming languages), computability and complexity?

If it would be wise to obtain more knowledge, what references can I read. For undergraduate education, I know basic stuff such as Hopcroft, Sipser, Ullman.

  • 11
    $\begingroup$ It is at least widely believed that more knowledge of any kind helps with just about anything. A better question would be the the contrapositive form: Is there a practical application which is impossible (or at least very difficult) without in depth theoretical knowledge? $\endgroup$ Commented Apr 5, 2013 at 14:10
  • 2
    $\begingroup$ yes, its a symbiosis. eg analyzing complexity of algorithms can be very theoretical and yet very applied/practical at the same time. note, similar to this question from opposite angle, how important is it to know how to program for TCS $\endgroup$
    – vzn
    Commented Apr 5, 2013 at 18:05
  • $\begingroup$ I would have to say no, as a practitioner, you mostly need experience, and the theory of computation is not that helpful. It might be helpful to have some experience in deductive reasoning, but you don't need to study theory of computation for that, you can study just about anything which has a critical component. $\endgroup$ Commented Apr 5, 2013 at 18:27
  • 1
    $\begingroup$ I think you should ask this from practitioners as you want to know if it helps them. I think the question is kind of off-topic here. If you want to ask for books to read, then again it is more suitable for Computer Science or Software Engineering. $\endgroup$
    – Kaveh
    Commented Apr 8, 2013 at 21:22
  • $\begingroup$ I've found being able to do simple reductions by hand to be pretty helpful. Garey & Johnson is a really good reference. In general, it is certainly good to know whether the problem you're trying to solve is NP-complete, for example. $\endgroup$
    – 0xYUANTI
    Commented Apr 14, 2013 at 9:02


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.