2 ms·
The algorithm in the article has an important bug. It’s a basic search: pop an element from a queue, see if it’s a match and, if not, push two new elements. If
by amluto 7y ago
The algorithm in the article has an important bug. It’s a basic search: pop an element from a queue, see if it’s a match and, if not, push two new elements. If the queue is empty, declare failure. Think about this for a moment. Each iteration, the queue length increases by one. Of course it’s never empty. So the algorithm will eventually declare success on a positive input and will run forever on negative input. It has to be this way, since PCP is equivalent to the halting problem. There is no algorithm that solves it correctly and always halts. This is the whole point.
This means that this program does not prove that parsing C++ is undecidable in the way the author thinks. There is no term that is a type or a value depending on the solution to an undecidable problem. Instead, there is a term that can not be resolved in finite time. This is a necessity property of pretty much any Turing-complete metaprogramming system.
(What I think is actually going on that’s a bit unique to C++ is that C++ cannot be parsed unambiguously. The fact that the grammar depends on whether a term is a type or value and that you can’t determine this from the AST without doing things like expanding templates is nasty.)