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!