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 <i>has</i> 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.<p>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.<p>(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.)