Theorem 9.3.1: PCP is undecidable if the alphabet has at least two letters.
A Turing machine description can be used to create aPCP whose matching establishes a direct correspondence between a PCP solution and a terminating run of the Turing machine. Hence analgorithm to decide the existence of a PCP solutionwould also decide Turing machine halting and istherefore impossible.
Previous slide | Next slide | Back to first slide | View graphic version |