PCP::=Post correspondence Problem.
The Wikipedia article
[ Post_correspondence_problem ]
gives the following informal description of the problem:
- Given a dictionary that contains pairs of phrases, i.e., a list of words, that mean the same, decide if there is a sentence that means the same in both languages.
(End of Net)
You can visualise an instance of the PCP as a set of dominoes.
The game is to put them in a row -- one at a time from Left to right --
that the top halves
spell out the same string as the bottom halves. Notice you can reuse
any domino at any time that it fits.
An Example of how PCP is used
PCP is a useful starting place for proving a problem undecidable.
[ node32.html ]
Spend some time playing with some simple instances. Get a feel for
how complicated behavior arises from a very simple basis.
Then answer this question: what property distinguishes good starting
dominoes from impossible ones? What property distinguishes good finishing
Interactive Example on the web
[ pcp.php ]
[ pcp1.png ]
[ pcp2.png ]
[ pcp3.png ]
9.4.1 Definition of Post's Correspondence Problem 392
Ch 9.4.1 pp 392 -- Could please example 9.13 and how the table in figure9.12 applies to it.
Ch 9.4 pp -- PCP
Why does the PCP use languages but not turing machines?
Ch 9.4 pp 395 -- Partial Solutions
Can you give an example of how partial solutions are used to analyze PCP instances?
Ch 9.4 pp 392 -- Post's Correspondence Problem
If we would write a program like the example that you gave us on your site.
We would input a set of instructions. How long would you think it would
take to be undecidable. Would the program data duplicate its data over and over
into a continuous loop.
Hint -- Try exercise 9.4.1 BEFORE starting to read section 9.4.2
9.4.2 The Modified PCP 394
Ch 9.4 pp 392-395 -- PCP and MPCP
Can you explain the differences between MPCP and PCP ? Both in definition
and in properties.
Ch 9.4 pp 396 -- MPCP Theorem 9.17
Can you go through theorem 9.17 MPCP reduces to PCP I am having trouble wrapping my mind around it.
Ch 9.4 pp 395-396 -- Example 9.16
Could you go over how to construct an instance of PCP from MPCP?
Ch 9.4.3 pp 397-402 -- Reducing Lu to MPCP
Could you go over the reduction from Lu to MPCP?
9.4.3 Completion of the Proof of PCP Undecidability 397
9.4.4 Exercises for Section 9.4 403
Focus on these exercise rather than those in 9.5.4.