Computer Science 313 Theory of Computation Exam 3, Winter 2005 Name: Pledged: Instructions: This is a closed book, closed

notes exam. The exam should be taken in one time block with a maximum of two hours. 1. (30 points) For the following languages, specify whether the language is decidable, recognizable but not decidable, or not recognizable. Give a reason for your answer fact from class, informal strategy, etc. a. A = {0n12n23n | n0} Decidable 1) Copy 0s to tape 2, 1s to tape 3, 2s to tape 4 2) Scan tapes 2,3,4, moving 1 cell at a time on tape 2, 2 at a time on tape 3,3 at a time on 4??? b. The complement of the language in part a. Decidable complement of decidable language is decidable c. ATM = {<M, w> | M is a Turing machine that accepts the string w} Recognizable (by universal Turing machine), not decidable in class d. The complement of ATM Not recognizable, else ATM would be decidable e. {<M, w> | M is a Turing machine and M neither accepts nor rejects w} Not recognizable. This is the complement of the Halting Problem which was shown to be not decidable. f. The complement of the language of part e Recognizable, not decidable Halting Problem g. {<M > | M is a TM and M accepts , the empty string} Recognizable, not decidable easy way to see this is with Rices Theorem h. {<D> | D is a DFA and D accepts , the empty string} Decidable just check that the start state is an accept state.

2. (25 points) a.Give a state-transition diagram for a Turing machine (of any type) that decides the language L = {s#t | s is the binary representation of a number n, and t is the representation of 2n}. First, give the overall strategy that you are using - do this even if you cannot complete the diagram. It might be good to write down two or three examples of strings in L first. Strategy: In class, we did w#w. Here you can first check that w#w as before, but then check that there is a 0 following the second w; should have w#w0. Ill let it go at that. Diagram: b. Short of giving detailed state-transition diagrams, we should be able to describe strategies for solving problems with Turing machines at a higher level, but with sufficient detail that people with Turing machine experience would be comfortable that the details could be worked out. For example, we might use steps such as copy the first set of zeroes to the second tape or retract the tape head or scan to the right to find the first 1. In this spirit, give a strategy for a Turing machine (of any deterministic type) that would decide the language L = {s#t#u | s,t,u are binary representations of k,m,n, respectively, and n = k+m} Strategy: First get s, t and u on separate tapes. Have another tape for carry, initialized to 0. Work from the right hand end of the three tapes. As we move right to left, at each bit position, we use the bits from s,t and the carry bit to produce a sum bit and a new carry bit. Each time, the sum bit should match the current bit in u, if not reject. If we reach the ends, matching at each position, accept. Fine tune for strings of different lengths.

3. (15 points) For this problem, you may use informal algorithm language, if you like. Suppose A and B are languages over = {0,1}. a. Suppose A and B are decidable with deciders M1 and M2. Give an algorithm for deciding AB. On input w, run M1 with input w. If it rejects, then reject. Otherwise run M2 with input w. If it rejects, reject; if it accepts, accept.

b.

With A and B as in part a, give a strategy for deciding AB, the concatenation of A and B. This is a little bit trickier. On input w, we test each spot where we might divide w in two, including the beginning and end. For each such spot, say w=uv, we run M1 with input u and M2 with input v. If there is any division of w that gives accept for both machines, we accept w. Otherwise, reject w.

c.

Suppose A and B are recognizable with recognizers M1 and M2. Give an algorithm for recognizing AB. This is even trickier. Here we can not just run a machine of a piece of the string because it might not ever stop when in fact another break point might work. One approach is to use non-determinism and guess the break point. Otherwise, you would need a scheme for doing 1 step of each machine for each break point, then 2 steps for each break point, etc.

4. (15 points) Answer true or false. Here A and B are languages. a. If A=L(P) for some non-deterministic, PDA, P then there must be a 2-tape Turing machine M, so that A=L(M). Context free languages are decidable b. If A=L(M) for some deterministic Turing machine M, then there is a, possibly non-deterministic, Turing machine M' that recognizes A. How about M = M? c. If A is decidable and B is recognizable, then AB is decidable. Use A={<M,w> | M is a Turing machine}, B= ATM , for example

T T F

d. If A is not decidable, then its complement is not recognizable. F Let A be the complement of ATM . Its not decidable, but complement is recognizable e. If A is decidable and BA, then B is decidable. ATM * F

f. If A is recognizable and B is decidable then AB must be recognizable. T The intersection of two recognizable languages is recognizable g. If A is countable, then the set of subsets of A is countable. F Shown in class that set of subsets of natural numbers in uncountable h. The set of languages over a fixed alphabet can be put into 1-1 correspondence with the set of Turing machines over that alphabet. F Set of languages is uncountable and set of Turing machines is countable i. {P | P is a legal Java program}is recognizable, but not decidable. Compilers decide this language context free. j. The Church-Turing thesis has to do with visiting European cathedrals. I just dont know. F ?

5. (10 points) a. Let H = {<M,w> | M is a Turing machine and M halts (accepts or rejects) on input w}. What do we know about H? H is recognizable, but not decidable the Halting Problem b. Let K = {<M> | M is a Turing machine and M is safe in that it halts on all input}. Suppose S is a Turing machine that decides K (S tests Turing machines to see if they are safe and gives yes/no answers.). Consider the following Turing machine T. T takes as input strings of form <M,w> where M is a Turing machine. On input <M,w>, T does the following 1) First, T constructs Turing machine M that on any input a) Erases its tape b) Puts w on its tape c) Simulates M on w 2) Feeds <M> to S and accepts or rejects <M,w> depending on what S does with <M> Describe the language decided by T. L(T) = {<M,w> | M is TM that halts on w} = H. What do you conclude about K? Why? Since T is a decider, we have a contradiction; so K is undecidable. 6. (5 points) Why do computer scientists have interest in the study of Turing machines when there are much better computers available today? Why not simply study modern computers? Write your answer as if you were giving a brief explanation to a computer science student who had not heard about Turing machines. VERY briefly, it is easier to show that certain problems can NOT be solved by TMs, and thus unsolvable by algorithm.