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#.
发布评论
评论（1）
这个问题很模糊。对谁重要？
所有这些都值得我们学习。这是所有人类努力本质上都值得学习这一事实的一个特例。
如果您的问题是“哪些主题给我带来的好处大于我学习这些主题所花费的时间和精力的成本？”那么这个问题只有你自己才能回答。比如说，学习古希腊历史对我的好处，与它如何影响我完成工作的能力无关。
我使用你列出的所有主题——语言理论、渐近阶分析、可判定性、复杂性理论、定理证明系统等等。
我不会在正式意义上使用它们；我没有坐在办公桌前使用主定理来导出特定算法的阶次分析。我使用它们的意义在于，能够非常方便地采用提议的语言功能并快速计算出实现它是否需要编译器解决线性、多项式、指数、NP 困难或等价于的问题停机问题。
例如，很容易计算出 C# 3 中嵌套 lambda 的重载解析是 NP 困难的，但并不等同于停止问题。因此，我们知道（1）即使尝试在多项式时间内解决问题也是浪费时间，（2）至少我们知道可以在一定时间内找到解决方案，（3）我们可以想出简单的启发式方法来检测不良场景，并在需要时快速失败。
我个人不太使用证明系统，尽管将问题视为定理证明者的特殊情况是有帮助的。有各种各样的语言特性相当于你向定理证明者提出的问题，特别是在类型推断和流分析领域。幸运的是，C# 的任何功能实际上都不需要实现定理证明器；在这座大楼中实现的其他语言确实具有该属性，例如 F#。
The question is vague. Important to who?
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.
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#.