3 ms·

An efficient algorithm to compute lookahead sets for a LALR1 grammar is seriously intricate. The closure computation algorithm is definitely non-trivial. I don'

An efficient algorithm to compute lookahead sets for a LALR1 grammar is seriously intricate. The closure computation algorithm is definitely non-trivial. I don't know about the "Classification of Finite Simple Groups" but LALR1 lookahead computation results go into everything. Every computer, tablet, or phone carries at least 10 different copies of such lookahead set-sets. Does the "Classification of Finite Simple Groups" actually lend itself to doing anything useful? Can it be applied?

millstone 14y ago
I would classify the discovery of these algorithms as computer science, not programming. Had Dijkstra said that computer science is harder than pure mathematics, I would have characterized his point as "arguable." Perhaps the CS term had not come into wide use when he said what he did. Regarding your question, some proofs have immediate applications, and some do not. The CoFSG falls into the latter category. But when you ask if a piece of mathematics is useful, the only two fair answers are "yes" and "not yet." For example, quantum mechanics relies on group representation theory, which had been worked out earlier, with few applications. Another example is Grassmann's work on abstract vector spaces, which was considered somewhere between incomprehensible and useless for decades after publication. Now it's taught in first year linear algebra, and is central to physics and many types of engineering. As for the two theorems I listed, the Monster Group (discovered during the CoFSG) has connections to string theory, and the Poincaré Conjecture may have implications for the allowable shapes of the universe. So, while it's unlikely, it may be that these mathematics end up telling us something about the very nature of reality itself.
- eriksank 14y ago
  I agree that there is requirement for research results to be useful immediately. That would probably be counter-productive. However, there should be some hope that we will be able to apply them some day, even in a rather distant future ...

millstone 14y ago

I would classify the discovery of these algorithms as computer science, not programming. Had Dijkstra said that computer science is harder than pure mathematics, I would have characterized his point as "arguable." Perhaps the CS term had not come into wide use when he said what he did. Regarding your question, some proofs have immediate applications, and some do not. The CoFSG falls into the latter category. But when you ask if a piece of mathematics is useful, the only two fair answers are "yes" and "not yet." For example, quantum mechanics relies on group representation theory, which had been worked out earlier, with few applications. Another example is Grassmann's work on abstract vector spaces, which was considered somewhere between incomprehensible and useless for decades after publication. Now it's taught in first year linear algebra, and is central to physics and many types of engineering. As for the two theorems I listed, the Monster Group (discovered during the CoFSG) has connections to string theory, and the Poincaré Conjecture may have implications for the allowable shapes of the universe. So, while it's unlikely, it may be that these mathematics end up telling us something about the very nature of reality itself.

eriksank 14y ago
I agree that there is requirement for research results to be useful immediately. That would probably be counter-productive. However, there should be some hope that we will be able to apply them some day, even in a rather distant future ...