Question

State whether the problem is decidable or undecidable.

If you claim the problem is decidable, then give a high-level, English description of an algorithm to solve the problem.

If you claim the problem is undecidable, then describe a proof-by-reduction to verify your claim. If your proof involves some kind of transformation of M into M’ , then provide a high-level, English description of your transformation. Be sure to specify precisely for each “box” in your proof, what are the inputs to that “box” (i.e., to that program) and what is The output of that “box”.

You are given, as input, some Turing Machine M. The problem is to determine whether M accepts every string that ends with the letter ‘b’.

Thanks a lot for your help!7

Answer 1

Define M' as a turing machine that takes a pair (M,w) as input, where M is a turing machine encoded in some form recognized by M' and w is the input to M.

M' stops and accepts (M,w) whenever the head of the simulated machine M moves to the left while processing input w

For a particular input to M' (M,w), construct the turing machine P as follows:

• P executes M' on (M,w)
• P stops and accepts any input if M' accepts (M,w)

We have reduced the Universal Turing Machine U to P. Since we know that L(U) is not decidable, we conclude that L(P) is not decidable. Consequently, M' is not decidable.

The proof is by contradiction. Assume that this problem is decidable, then we will show that ATM (the acceptance problem) is also decidable: ATM = { | M is a TM and M accepts w}. Let R be a Turing machine that decides the LEFTMOST problem. That is, R decides the language

LEFTMOST = { | M on input w ever attempts to move its head left when it's head is on the left-most tape cell }.

Now, the idea is to construct a Turing machine S that decides ATM in such a way that it uses R. We can do it as follows: On input , S first modifies machine M to M´, so that M´ moves its head to the left from the left-most cell only when M accepts its input. To ensure that during its computation M´ doesn't move the head left from the left-most position, machine M´ first shifts the input w one position to the right, and places a special symbol on the left-most tape cell. The computation of M´ starts with the head on the second tape cell. If during its computation M´ ever attempts to move its head to the left-most tape cell, M´ finds out that it did so by reading the special symbol and then puts the head back to the second cell, and continues its execution. If M would enter an accept state, then M´ enters a loop that forces the head to move always to the left.

After S has constructed M´ it runs the decider R on input < M´; w>. If R accepts then S accepts, otherwise if R rejects then S rejects. Therefore, ATM is decidable, which is a contradiction.