PROBLEM SET 7, CSC 280, 2006 DUE BEFORE CLASS, MON. MAR. 20 The seventh problem set is as follows. All 8 problems will be marked out of the same total. Answers to any 5 questions make a complete answer paper. However, you can do all questions to earn bonus points. (Bonus points = 0.5 times the extra marks obtained on the least successful extra problems tried.) Keep your eyes on the instructor's and the TAs' web site for any corrections or discussion. PROBLEM 1 ~~~~~~~~~ Prove that ALL_tm, defined as {| M is a TM that accepts all inputs}, is undecidable, using a reduction from A_tm (the acceptance problem for Turing machines). Problem 2 ~~~~~~~~~ Prove that RUNAWAY_tm, defined as {| M is a TM that never tries to move left on any input}, is DECIDABLE. Suggestions: don't make the mistake of supposing that such a machine must lack transitions that specify a leftward move; think first about solving this problem for a particular input (e.g., a blank tape) given to the TM under consideration. Problem 3 ~~~~~~~~~ Prove that ROAMAWAY_tm, defined as {| M is a TM and on all inputs, M scans an infinite amount of tape}, is undecidable. PROBLEM 4 ~~~~~~~~~ Prove that CFL_tm, defined as {| M is a TM such that L(M) is a CFL}, is undecidable. PROBLEM 5 ~~~~~~~~~ Prove that COMPLEMENTARY_tm, defined as {| M, M' are TMs such that each accepts exactly the inputs that the other doesn't accept, i.e., L(M) = complement of L(M')}, is undecidable. PROBLEM 6 ~~~~~~~~~ Prove by a reduction from A_tm that ANOREXIA_tm, defined as {| M is a TM that accepts only the empty string}, is undecidable. PROBLEM 7 ~~~~~~~~~ a. Prove that for any finite set of strings S over alphabet {0,1}, There is a CFG that generates {0,1}* - S (i.e., all binary strings except S). You may use results from the lectures or describe how to construct an appropriate grammar. b. Prove by a reduction from A_tm that ALL-BUT-THOSE_cfg, defined as {| G is a CFG with terminal alphabet {0,1} and S is a finite set of binary strings, and L(G) = {0,1}* - S}, is undecidable. PROBLEM 8 ~~~~~~~~~ a. Prove that HALT_lba, whose meaning should be clear, is DECIDABLE. b. Modify the proof of the undecidability of E_lba given in class (and in Sipser) to show that FIN_lba is undecidable, where this is defined as {| M is a TM and if it is treated as an LBA, L(M) is finite}. Hint: only a slight modification in L_x is needed!