only if w ∈ L R . The machine that reverses a string and applies M is an lba.
Therefore, L R is context-sensitive.
6. We can argue from an lba. Clearly, there is an lba that can recognize any
string of the form wuw R . Just start at opposite ends and compare symbols to
get a match. Find the longest possible w, then compare its length with u.
Since there is an lba, the language is context-sensitive and a context-sensitive
grammar must exist.
Chapter 12
Section 12.1
3. Given M and w, modify M to get , which halts if and only if a special
symbol, say an introduced symbol #, is written. We can do this by changing
the halting configurations of M so that every one writes #, then stops. Thus,
M halts implies that writes #, and writes # implies that M halts. Thus,
if we have an algorithm that tells us whether or not a specified symbol a is
ever written, we apply it to with a = #. This would solve the halting
problem.
7. Given (M, w) modify M to so that (M, w) halts if and only if accepts
some simple language, say {a}. This can be done by M first checking the
input and remembering whether the input was a. Then M carries out its
normal computations. When it halts, check if the input was a. Accept if so,
reject otherwise. Therefore, accepts {a} if and only if M halts. Now
construct a simple Turing machine, say M 1 , that accepts a. If we had an
algorithm that checks for the equality of two languages, we could use it to
see if
. If
then (M, w) halts. If
then (M, w) does not halt and we have a solution to the
halting problem.
10. Given (M, w) we modify M so that it always halts in the configuration qf w.
If the given problem was decidable, we could apply the supposed algorithm