Skip to main contentCal State San Bernardino
>> [CNS] >> [Comp Sci Dept] >> [R J Botting] >> [CS546/646] >> 10 [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:55 PDT 2006

Contents

    10

      Schedule
      Date Meet'g Study(2 pts) Bring(5 pts) Topic(5 pts) Notes
      Mon May 1 9 Web2 URL Recursive Functions Acker(10 pts Bonus)
      Wed May 3 10 Chapter 9 sections 9.1, 9.2 Ex Undecidability & RE Project1 (10 pts)
      Mon May 8 11 Project2 (20 pts) - Turing Machines

      Project Status Reports

      Chapter 9 Undecidability 367

        9.1 A Language That Is Not Recursively Enumerable 368

        1. Recursively_enumerable::=`the languages that are accepted by a TM that may not always halt}.
        2. Recursive_language::=languages accepted by a TM that always halts.

        3. Decidable::=`problems/languages where a halting TM can decide if a string is accepted or rejected` -- there exists a TM which always halts and it Halts in an F state if and only if its input was in the language, and it halts in a non-F state if and only if its input is not in the language.

          Type of ProblemMachineAcceptsRejectsRuns for ever
          RegularFSALL_barNever
          RecursiveTMLL_barNever
          DecidableTMLL_barNever
          Undecidable?
          RETML?Perhaps
          not RENone

          Ch 9 pp 368 -- Enumeration of Binary Strings

          Why does a non-RE language prove undecidable?

          Ch 9 pp -- Where is Theorem 9.1

          9.1.1 Enumerating the Binary Strings 369

          Ch 9.1.1 pp 369 -- Enumerating Binary Strings

           The book says "...we shall need to assign integers to all the binary strings..." but they start counting with an empty symbol and not 0 or 1. Why do they do this?

          Ch 9.1.5 pp 372 -- Exercises for Section 9.1

          Exerciee 9.1.1(a) asks what string w37 is. The online solution gives 37 in binary (100101) and removes the leading 1 to get 00101 as the answer, but doesn't explain why.

          9.1.2 Codes for Turing Machines 369

          9.1.3 The Diagonalization Language 370
        4. L_d::={w[i] | for some i, w[i] is not in L(M[i])}

          Ch 9.1.3 pp 371 -- Diagonalization Language

           can you explain how the diagonal values tell whether TM accepts the code?

          Ch 9.1.3 pp 370-371 -- Diagonalization language

          I am a bit confused with this definition, could you go over how this 'diagonalization' language represents acceptance of strings during class?

          Ch 9.1.3 pp 371 -- Figure 9.1 Diagonal

          when it comes to the table that represent the diagonal on page 371 The book states that if fig 9.1 were the correct table, then the complemented diagonal would begin 1,0,0,0.....I was just wondering how they come up with this conclusion.It's a bit unclear to me.

          Ch 9.1 pp 371 -- Diagonalization and Figure 9.1

          Can you please go over Figure 9.1 and explain why the diagonal shows whether a string is accepted or not?

          Ch 9.1.3 pp 370-372 -- Diagonalization Language

          Could you go over the diagonalization language? I\'ve seen this proof multiple times, but I still have no idea how or why it works.

          9.1.4 Proof that L_d is not Recursively Enumerable 372

          Theorem 9.2

          9.1.5 Exercises for Section 9.1 372

        9.2 An Undecidable Problem That is RE 373

          9.2.1 Recursive Languages 373

          9.2.2 Complements of Recursive and RE languages 374

          Theorem 9.3 If a language is recursive so is it's complement
        1. L_bar = co_L = { w | w is not in L }

          Theorem 9.4 If L and L_bar is RE then L is recursive.

          9.2.3 The Universal Language 377
        2. L_u::=the Universal language that encodes all pairs of strings where the first represents a machine and the second is a word accepted by that machine.
        3. U::TM=The universal machine -- that recognizes L_u.

          Ch 9.2.3 pp 377 -- Universal Language

           What is the difference between Multi-tape Turing Machine and Universal Language Turing Machine?

          Ch 9.2.3 pp 379 -- The Universal Language

          Could you show us an example of a more efficient universal TM, by drawing it up on the board?

          9.2.4 Undecidability of the Universal Language 379

          Error in Proof of Theorem 9.6

           The Reduction of L_d to L_u_bar has a missing component/step. The M' machine must check the syntax of the incoming word as well as copy it. If w is not a string that represents a TM then M' should Accept w without running the hypothetical machine M.

          Ch 9 pp 380 -- L_u is not RE

           Can you explain the proof on page 380 about how L_u is RE but not recursive.

          9.2.5 Exercises for Section 9.2 381

      . . . . . . . . . ( end of section Chapter 9 Undecidability 367) <<Contents | End>>

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

    Notes


    (Project): Working in a team of 3 or 4 people design, code, and test a simple Turing Machine simulator.
  1. Process
    1. Start by thinking about the design and developing tests for your code...
    2. (Project1): First deadline: bring a progress report to class and present it. Grading: pass/fail. Any running set of tests will pass.
    3. (Project2): Second deadline: bring a report on the final status, present it, and hand in a hard copy for grading.


    (Ex): Do as many of the relevant exercises as you have time for. You may work in a team of up to 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

  2. FSA::="Finite State Acceptor/Automata", a theoretical machine with a finite set of states.
  3. 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.
  4. PDA::="Push down Automata", a machine with a finite control and a single stack for remembering intermediate data. Kind of like half a TM.
  5. RJB::=The author of this document, [ ../index.html ]
  6. |-RJB="Richard J Botting, Comp Sci Dept, CSUSB".
  7. Schedule::= See http://www.csci.csusb.edu/dick/cs546/schedule.html.
  8. Search::= See http://www.csci.csusb.edu/dick/cs546/lookup.php.
  9. Syllabus::= See http://www.csci.csusb.edu/dick/cs546/syllabus.html, and also see [ syllabus.html ] (my generic syllabus).
  10. TBA::="To Be Announced".
  11. TM::="Turing Machine".
  12. NTM::="Nondeterministic Turing Machine".
  13. nondeterministic::="A machine that can make choices as it runs and accepts an input iff any sequence of choices leads to acceptance."
  14. DTM::="Deterministic Turing Machine".
  15. runtime::=run_time,
  16. run_time::="The number of steps a TM takes before it halts when start on a given input".
  17. complexity::="The largest run_time for any word with a given length" , usually expressed as an assymptotic (Big-O) formula.
  18. P::@problem=class of problems that a DTM can compute in polynomial_time.
  19. NP::@problem=class of problems that a NTM can compute in polynomial_time.
  20. 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

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


  22. (LOGIC)|- (ei): Existential instantiation -- if P is true of something then we can substitute a new variable for it.
  23. (LOGIC)|- (eg): existential generalization -- if P is true of this thing then it is true of something!
  24. (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.
  25. (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.
  26. (LOGIC)|- (def): By definition of a term defined above.
  27. (LOGIC)|- (algebra): Either by using well known algebraic results, or by use a series of algebraic steps.
  28. (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