Definition 9.3.1: Post’s Correspondence Problem (PCP) is the decision problem: “given a finite alphabet _ and two k-tuples (kŤ1) of sequences A =
Example 9.3.1
a1 a2 a3 … = 10101101 … and
b1 b2 b3 … = 101011011 …
Previous slide | Next slide | Back to first slide | View graphic version |