.Open 10 . Schedule .Table Date .Item Meet'g .Item $Study(2 pts) .Item Bring(5 pts) .Item $Topic(5 pts) .Item Notes .Row Mon May 1 .Item 9 .Item Web2 .Item URL .Item Recursive Functions .Item Acker(10 pts Bonus) .Row Wed May 3 .Item 10 .Item Chapter 9 sections 9.1, 9.2 .Item $Ex .Item Undecidability & RE .Item $Project1 (10 pts) .Row Mon May 8 .Item 11 .Item $Project2 (20 pts) .Item - .Item Turing Machines .Close.Table . Project Status Reports .Open Chapter 9 Undecidability 367 .Open 9.1 A Language That Is Not Recursively Enumerable 368 Recursively_enumerable::=`the languages that are accepted by a TM that may not always halt}. Recursive_language::=`languages accepted by a TM that always halts`. 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. .Table Type of Problem Machine Accepts Rejects Runs for ever .Row Regular FSA L L_bar Never .Row Recursive TM L L_bar Never .Row Decidable TM L L_bar Never .Row Undecidable ? .Row RE TM L ? Perhaps .Row not RE None .Close.Table . 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 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 .Close .Open 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 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 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`. 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 .Close .Close Chapter 9 Undecidability 367 .Close 10 . Notes (Project): Working in a team of 3 or 4 people design, code, and test a simple Turing Machine simulator. .Set Notes You may use any language that can be demonstrated in class. You may choose any kind of user interface you like. Your $TM simulator does not have to have infinite memory capacity like a real $TM. Do the simplest thing that can possibly work. Consult with me in my office hours. .Close.Set Process .List Start by thinking about the design and developing tests for your code... (Project1): First deadline: bring a progress report to class and present it. Grading: pass/fail. Any running set of tests will pass. (Project2): Second deadline: bring a report on the final status, present it, and hand in a hard copy for grading. .Close.List (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.