Skip to main contentCal State San Bernardino
>> [CNS] >> [Comp Sci Dept] >> [R J Botting] >> [CS546/646] >> 13 [Text Version]
[About] [Contact] [Grades] [Projects] [Submit] [Schedule] [Syllabus] [Search ]
Session: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] (13) [14] [15] [16] [17] [18] [19] [20]
Thu Jun 8 13:02:58 PDT 2006

Contents

    13

      Schedule
      Date Meet'g Study(2 pts) Bring(5 pts) Topic(5 pts) Notes
      Wed May 10 12 Chapter 9 section 9.3 Ex Undecidability & TM
      Mon May 15 13 Chapter 9 sections 9.4, 9.5.1, 9.6 Ex Post Correspondence+ Programs
      Wed May 17 14 Chapter 10 sections 10.1 Ex Intractable Problems P & NP

      Emil Leon Post 1897 - 1954

       [ Post.html ]

      9.4 Post's Correspondence Problem 392

      1. PCP::=Post correspondence Problem. The Wikipedia article [ Post_correspondence_problem ] gives the following informal description of the problem:
        Net
        1. 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.
        A[i]
        B[i]
        The game is to put them in a row -- one at a time from Left to right --
        A[i1]A[i2]A[i3]
        B[i1]B[i2]B[i3]
        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 ]

        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

        [ pcp.php ]

        More examples

         [ 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.

      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
          Give three examples of non-trivial problems about programs that we would really like to solve but must be undecidable.

      9.6 Summary of Chapter 9 410

      9.7 References for Chapter 9 411

    . . . . . . . . . ( end of section 13) <<Contents | End>>

    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.

    Standard Definitions

  1. FSA::="Finite State Acceptor/Automata", a theoretical machine with a finite set of states.
  2. ND::="Non-deterministic", a machine that can try out many possibilities and always guesses the right choice. Note: For a given problem a ND solution is simpler and easier to understand than a deterministic one. We study ND machines to discover how to use them as high-level designs for more complicated deterministic machines. Plus it's fun.
  3. PDA::="Push down Automata", a machine with a finite control and a single stack for remembering intermediate data. Kind of like half a TM.
  4. RJB::=The author of this document, [ ../index.html ]
  5. |-RJB="Richard J Botting, Comp Sci Dept, CSUSB".
  6. Schedule::= See http://www.csci.csusb.edu/dick/cs546/schedule.html.
  7. Search::= See http://www.csci.csusb.edu/dick/cs546/lookup.php.
  8. Syllabus::= See http://www.csci.csusb.edu/dick/cs546/syllabus.html, and also see [ syllabus.html ] (my generic syllabus).
  9. TBA::="To Be Announced".
  10. TM::="Turing Machine".
  11. NTM::="Nondeterministic Turing Machine".
  12. nondeterministic::="A machine that can make choices as it runs and accepts an input iff any sequence of choices leads to acceptance."
  13. DTM::="Deterministic Turing Machine".
  14. runtime::=run_time,
  15. run_time::="The number of steps a TM takes before it halts when start on a given input".
  16. complexity::="The largest run_time for any word with a given length" , usually expressed as an assymptotic (Big-O) formula.
  17. P::@problem=class of problems that a DTM can compute in polynomial_time.
  18. NP::@problem=class of problems that a NTM can compute in polynomial_time.
  19. polynomial_time::=An algorithm/TM is said to halt in polynomial time if the number of steps given n items of data is less than O(n^c) for some constant c.

    From Logic

  20. LOGIC::= See http://www.csci.csusb.edu/dick/maths/logic_25_Proofs.html


  21. (LOGIC)|- (ei): Existential instantiation -- if P is true of something then we can substitute a new variable for it.
  22. (LOGIC)|- (eg): existential generalization -- if P is true of this thing then it is true of something!
  23. (LOGIC)|- (given): a proposition that is assumed as part of a Let...End Let argument. Typically if A and B and C then D starts with assuming A,B, and C are given. They are called the hypotheses.
  24. (LOGIC)|- (goal): a proposition that we wish to prove. Typically the part after the then in an if...then... result. This is called the conclusion.
  25. (LOGIC)|- (def): By definition of a term defined above.
  26. (LOGIC)|- (algebra): Either by using well known algebraic results, or by use a series of algebraic steps.
  27. (LOGIC)|- (RAA): Reduce to absurdity. The end of a Let/Po/Case/Net that establishes the negation of the last set of assumptions/hypotheses.

End