News for hackers. Stuff that matters.
Re:Proving that C++'s grammar is undecidable by ben509 on Tuesday April 28, 2020 @11:06PM (#23014856)
> The author says that a solution to the Post Correspondence Problem with infinite dominoes in finite time is impossible.

He doesn't say an infinite set, though:

> Turns out, there exists no algorithm that says “yes” or “no” to the Post Correspondence Problem in finite time, given any set of dominoes as input.

That means any finite set of dominos.

It's similar to the idea behind the halting problem, it's not checking whether an infinitely long program will halt, but whether any possible finite program will halt.

There are no comments on this comment yet.