5.2 A Simple Undecidable Problem


Post Correspondence Problem:Begin with a collection of dominos. The task is to make a list of given deminos(repetitions permitted) so that the string we get by reading off the symbols on the top is the same as the string of symbols on the bottom. This list is called a match.

PCP={<P>PPCP=\{<P>|P is an instance of the PCP with a match}\}

PCPPCP is undecidable.


证明方法:computation histories


results matching ""

    No results matching ""