Prove that the following problem is undecidable by a reduction from the halting problem:

Question

Prove that the following problem is undecidable by a reduction from the halting problem:

“Does a given Turing Machine M accept any string of form a^2k for k ≥ 1?”

I'm having trouble understanding the intuition behind the Halting problem reduction, could someone please explain in an intuitive and easy to understand why this is the case? I've watched some videos and studied some material online but a, having a hard time with this concept.

Answer 1

A simple application of Rice's theorem would make things easy but let's just pretend we only know the existence of a universal machine that can simulate all others. Now onto the argument, let's suppose towards a contradiction that the set, let's call it S, is decidable. This means that there is a turing machine U that can decide if some arbitrary machine M accepts an input of the form a^2k. In other words our machine accepts of the machine M accepts and otherwise rejects.

Well if such a machine existed so would a machine U' which does the following:

1.It verifies that the input is of the a^2k type or of the a^2k-1 type(this is just a context-free problem).

• if the input is of the form i = a^2k it just runs U on M(i) to see what happens, if it accepts accept and if it rejects, run M(i) and if it rejects then accept. Otherwise do nothing.
• if the input is of the form i = a^2k-1, we acknowledge the fact that there is a machine M' that runs just like M(a^2k-1) but on input a^2k, then we do the same analysis as in the previous bullet.

Now using machines U and U' we can build another machine H that decides the halting problem as follows:

Provided we can assume that we can code machines as strings of the form a^k we do the following to decide the halting problem for any machine M on input i: run U(U'(M(i)))

• accept if it returns "accept"
• otherwise, reject.