4 ms·
It may take an infinite amount of time to solve the Post Correspondence Problem even with a finite number of dominoes, but you can't know whether it really will
by roywiggins 7y ago
It may take an infinite amount of time to solve the Post Correspondence Problem even with a finite number of dominoes, but you can't know whether it really will hang forever or whether you just haven't run your program long enough to find the answer. You don't need infinite space or time for the ones that are solveable, just an unknowably large amount.
So if you make a C++ program that compiles if the equivalent arbitrary Post Correspondence Problem is solvable, and compiles forever otherwise, you've proven that C++ compilation is not decidable.