Proving a decision is undecidable

0
votes

I understand that HP is an undecidable problem because of the diagonalization argument.

In my book (kozen) the first example of a reduction to the halting problem is a machine that can decide whether or not the empty string ε is accepted.

from my book:

Suppose we could decide whether e. given machine a.ccepts E. We could then decide the halting problem as folIows. Say we are given a Turing machine M and string x, and we wish to determine whether M halts on X. Construct from M and x a new machine M' that does the following on input y:

  • (i) erases its input y;
  • (ii) writes x on its tape (M' has x hard-wired in its finite control);
  • (iii) runs M on input x (M' also has a description of M hard-wired in its finite control);
  • (iv) accepts if M halts on X.

Here already, numerous questions come to my mind. M' is not based (as far as the text tells at least) on the actual machine that decides whether ε is accepted or not.

Why do we erase the input y? Is x in M' arbitrary? And the biggest confusion comes from my question: Why can't I prove any decision problem this way: Make a machine M' that erases its input, writes x on the tape, runs M on the input x and accepts if M halts on x?

I'm trying to understand the relation between the decider for a machine to accept ε and the TM given by the book, but I can't seem to understand it, neither can my fellow students.

1
turing-machines

1 Answers

0
votes

Erasing the input is just to show that it is irrelevant. You could as well leave it there and write behind it.

x in M' is not arbitrary but "M' has x hard-wired in its finite control" for deciding the problem "given a Turing machine M and string x, and we wish to determine whether M halts on x."

The new machine always does the same independent of its input. Therefore, it either accepts ALL inputs or NONE. So it accepts the empty string IFF M accepts x. It is important to note that we are talking about only one computation of M but all the computations of M'.