4 ms·

The Halting Problem is typically used because it was one of the first proven as undecidable, same reason in P vs. NP questions often use SAT. C++ templates, Ha

The Halting Problem is typically used because it was one of the first proven as undecidable, same reason in P vs. NP questions often use SAT. C++ templates, Haskel templates, Lisp macros, etc... are all examples of metaprogramming facilities that would be considered TC, and thus subject to Rice's Theorem (To avoid HP). But last I saw the code that was generated was the problem, not the primitives. As the languages are TC, a parser not being so doesn't remove the issue with this CVE.

stcredzero 4y ago
But last I saw the code that was generated was the problem, not the primitives. Good! So, if what we want the compiler compiler to do is, say, just to produce an output isomorphic to the input, then this also reduces the complexity of what we're asking to do. I think this falls well inside what we could automate with some kind of guarantee of correctness. A good mental habit for programmers is to constantly ask, "Can the stated problem be reduced in scope, such that we satisfy the goal?"