.Open 13 . Schedule .Table Date .Item Meet'g .Item $Study(2 pts) .Item Bring(5 pts) .Item $Topic(5 pts) .Item Notes .Row Wed May 10 .Item 12 .Item Chapter 9 section 9.3 .Item $Ex .Item Undecidability & $TM .Row Mon May 15 .Item 13 .Item Chapter 9 sections 9.4, 9.5.1, 9.6 .Item $Ex .Item Post Correspondence+ Programs .Row Wed May 17 .Item 14 .Item Chapter 10 sections 10.1 .Item $Ex .Item Intractable Problems P & NP .Close.Table . Emil Leon Post 1897 - 1954 .See http://www-groups.dcs.st-and.ac.uk/~history/Mathematicians/Post.html .Open 9.4 Post's Correspondence Problem 392 PCP::=`Post correspondence Problem`. The Wikipedia article .See http://en.wikipedia.org/wiki/Post_correspondence_problem gives the following informal description of the problem: .Net 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. .Close.Net You can visualise an instance of the $PCP as a set of dominoes. .Table .Row A[i] .Row B[i] .Close.Table The game is to put them in a row -- one at a time from Left to right -- .Table .Row A[i1] A[i2] A[i3] .Row B[i1] B[i2] B[i3] .Close.Table 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. .See http://odur.let.rug.nl/~vannoord/papers/diss/diss/node32.html . PCP Hint 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 tiles? . Interactive Example on the web .See http://www.cs.princeton.edu/introcs/77computability/pcp/pcp.php . More examples .See http://www.cs.princeton.edu/introcs/77computability/pcp1.png .See http://www.cs.princeton.edu/introcs/77computability/pcp2.png .See http://www.cs.princeton.edu/introcs/77computability/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. .Close .Open 9.5 Other Undecidable Problems 403 . 9.5.1 Problems About Programs 403 `Any nontrivial problem that involves what a program does must be undecidable`! . SKIP 9.5.2 Undecidability of Ambiguity for CFG's 404 . SKIP 9.5.3 The Complement of a List Language 406 . 9.5.4 Exercises for Section 9.5 409 Most of these are: solved on the WWW, difficult, too difficult, and/or about grammar theory. So here is an exercise on section 9.5.1 .Box Give three examples of non-trivial problems about programs that we would really like to solve but must be undecidable. .Close.Box .Close . 9.6 Summary of Chapter 9 410 . 9.7 References for Chapter 9 411 .Close 13 . Note (Ex): Do as many of the relevant exercises as you have time for. You may work in a team of upto 4 students and hand in one joint solution. Bring to class one written solution to an exercise. This must not be a solution to an exercise marked with an asterisk(*) to earn full credit. One of the authors will be invited to present the solution to the class -- failure will loose points. Students taking CS646 must hand in the solution to an exercise marked with an exclamation mark(!) to earn full credit. (Study): Read & think about the assigned items. Submit one question by selecting the submit button at the top of the web page. To earn complete credit you need to do this at least 90 minutes before the start of class. Hints. Read each section twice -- once the easy bits and then the tough bits. Use a scratch pad and pencil as you read. (Topic): To earn all the possible points you must: turn up on time, not leave early, present work when called upon, and take part in discussions.