Professor solves 240 computer science exam problems in 4 hours [video]
I need to defend theory of computer science here, it seems. Please note that this computer <i>science</i>, not computer <i>engineering</i>. The idea of automata, regular languages, turing machines, and whatnot inform some of the most fundamental results of computer <i>science</i>.<p>At least in the fields where I work [compilers, formal verification], all of the above theory is common parlance. Everyone working on this stuff knows all of the above theory, since it forms the bedrock of a large part of what we do and how we think about the world. Knowing the complexity of the algorithms we use, the languages we parse, issues of decidability, etc. all crop up. That's because it's <i>science</i>, not <i>engineering</i>. GATE is meant as an entrance exam to pursue a graduate degree in computer <i>science</i>.<p>The fact that one does not need this during their day job is, dare I say it, irrelevant.  This feels to me like people complaining that number theory is completely useless in the 19th century; Indeed it was... until it wasn't, and we needed cryptography.<p>This stuff is useful <i>right now</i> in a 'how to think about the world' kind of way. Knowing the power differences between automata, transducers, push down automata, and turing machines is critical in disparate applications involving formal verification. The difference in power of these different representations impacts what we can "do" with them. The knowledge of this hierarchy fundamentally shapes how I view the world.