UVa - cs302: Theory of Computation Spring 2008Exam 2 Final CommentsSee the preview comments for the grade distribution and answers to the other questions.Problem 1: Short Answers. (25) For each question, provide a correct, clear, precise, andconcise answer from the perspective of a theoretical computer scientist.b. [10] Explain the essence of the Church-Turing Thesis in a way that would be understand-able to a typical fifth grader.Answer: You know how you learn to solve long addition, multiplication, and divisionproblems in math class? Well, what you are really learning is called a “procedure”. Thatmeans, it is a series of instructions for what to do. The hard problem of adding two manydigit numbers is broken down into a series of steps. For example, you start by adding therightmost digits, writing down the answer at the bottom and if the sum is more than ten,writing the carry at the top of the next column. Then, you move left one position and addthe next column. If you follow the rules carefully, the instructions work no matter what thenumbers are — they could have hundreds of digits in them, but you can still add them byfollowing the same rules. The good think about the procedures you are learning in mathclass is that they always finish. There is a fancy name for a procedure that always finishes:it is called an “algorithm”.To do addition, you have rules that involve making decisions (for example, if the sum inone column is higher than 10, you need to carry the tens value), and keeping going (youkeep adding the columns from right to left until you are done), as well as a way to keeptrack of what you are doing (when you add a column, you remember in your head whatthe sum is, and you can do this because you learned how to add any two digits). It turnsout that thow three kinds of rules are all you need to do any computation! If you can keeptrack of what you are doing, make decisions, keep going, and have a big enough sheet ofpaper to write down everything you want, you can do every calculation. What you aredoing is very similar to what a computer does — computers are all around you: in yourvideo game machine, in your cell phone, in your iPod, etc. All of these computers mightseem very different, but other than differences in their screens and how much memorythey have (this is like the size of the paper you can write things on), what they can do isexactly the same, and it is exactly the same as what you can do following rules on paper.The difference is the computers can carry out the steps much faster, they never get bored,and they hardly ever make mistakes. This was understood way back before even yourparents were born (before there were any video games, cell phones, or iPods!) by AlonzoChurch and Alan Turing, who started out understanding what computers could do bythinking about how fifth graders do arithmetic.X2C-1Problem 2: Turing Machines. (25)b. [15] Define a cyclical Turing machine as a Turing machine with a one-way infinite tape (asin our standard Turing machine definition), except that the left edge behavior is defineddifferently. Instead of staying in the leftmost square, if a cyclical Turing machine wouldmove left past the left edge of the tape, the head moves to the rightmost non-blank square.Prove that the class of languages that can be recognized by a cyclical Turing machine isidentical to the class of languages that can be recognized by a regular Turing machine.Answer: To prove two computing models are equivalent, we need to show that each modelcan simulate the other model. So, we need to show that (1) a cyclical Turing machine (CTM)can simulate a regular Turing machine (RTM), and that (2) an RTM can simulate a CTM.(1) To simulate an RTM with a CTM, we need to avoid the cycling behavior. We can do thisby adding a previously unused symbol, %, to the tape alphabet. To simulate an RTM witha CTM, we add a new start state which walks to the end of the input, and then moves theoriginal input to the right one square by copying each symbol to the square to the right,and then moving two squares left to the next symbol. After this, the original first squareis not unused. Write a % in that square. Then, simulate the original RTM, starting on thesecond square, but with an additional transition rule for whenever the input symbol is %to move right one square. This simulates the normal left edge behavior of the RTM.(2) To simulate a CTM with an RTM, we need to simulate the cycling behavior. Doingthis correctly is a little tricky, since at the beginning we know the leftmost blank square isthe end of the input, but there is no way to ensure this is always the case. To avoid thisproblem, we add a special mark for the rightmost used square. This mark needs to bemaintained by the transition rules, so whenever the machine would move right from themarked square, it enters a new state that marks whatever is written on the new square. Inthe case where the marked square is overwritten with a blank, the rules needs to mark thesquare to its left as the new rightmost square. So, to simulate the CTM, at the beginningthe RTM finds the rightmost non-blank and adds a mark to it. As in case (1), we move allthe input to the right one square to make room for the % marker at the leftmost square. Atransition rule is added so that whenever the % is encountered, the machine moves to therightmost square by finding the square with the special mark.Thus, we can do the simulations in both directions, so the computing models are equiva-lent.Problem 4: Decidability. (30) For each part, state clearly whether the described languageis decidable or undecidable. Support your answer with a convincing proof. You may useany of the theorems we have proven in class or in the book, but you may not use Rice’stheorem in your proof unless you also include a proof of Rice’s theorem.b. [10] NOT SUBT M= {hA, Bi} where A and B are descriptions of Turing machinesand there is some string w which is accepted by A that is not accepted by B (that is, thelanguage accepted by A is not a subset of the language accepted by B).Answer: We show two different proofs which use reductions from different problems.X2C-2Proof by Reduction from EQT M. We show that N OT SU BT Mis undecidable by showingthat a decider for NOT SUBT Mcould be used to build a decider for EQT M.Assume N OT SU BT Mis decidable. Then, there exists a TM MNSthat decides NOT SUBT M.We can construct MEQthat decides EQT Musing MNS:MEQ(hA, Bi):1. Check that the