# Modify Turing’s proof of the undecidability of the halting problem

Modify Turing’s proof of the undecidability of the halting problem to show there is no Turing machine P with the following two properties:

• For all Turing machines M, if M() accepts then P(⟨M⟩) accepts, while if M() rejects then P(⟨M⟩) rejects.
• P(x) halts for every input x. (In other words, if M() runs forever, then P(⟨M⟩) can either accept or reject, but it cannot run forever.)

Hey how can I address this question using the original proof of undecidability. The proof needs to be done using a Turing machine that is a decider. But the behavior of P isn't specify when it is looping forever, it can either accept or reject. That's the part I'm confuse about.

• Where did you encounter this task? Can you credit the original source? We require you to credit the original source of all copied material: cs.stackexchange.com/help/referencing. I don't know how to answer this without seeing what is referred to by "this proof".
– D.W.
Apr 7 at 17:59
• @D.W. Oh sorry, I made a typo in the question. Need to modify the original proof of the undecidability to proof that Turing machine P with the following two properties can not exist. Apr 7 at 18:37
• @JohnL. sadly no, I haven't been able to solve it. Apr 8 at 14:06
• @JohnL. If you have any tip, that would be extremely helpful. I'm kind of stuck at this point. Apr 8 at 18:21

### A proof of the halting problem

Here is a proof for undecidability of the halting problem.

Towards a contradiction, suppose there is a Turing machine (TM) $$H$$ such that for all TMs $$M$$ and all strings $$w$$, $$H(\langle M, w\rangle)$$ will output string "HALT" if $$M(w)$$ halts while $$H(\langle M, w\rangle)$$ will output string "RUN FOREVER" if $$M(w)$$ runs forever.

We construct a machine $$G$$ such that for all TMs $$M$$, $$G(\langle M\rangle)$$ does the following two steps.

1. The simulation step.
Simulates $$H(\langle M, \langle M\rangle\rangle)$$, which will output either "HALT" or "RUN FOREVER"
2. The negation step.
If the output is "HALT", runs forever.
If the output is "RUN FOREVER", halts.

Let us run $$G(\langle G\rangle)$$. There are two possible result of the simulation step.

• The simulated $$H$$ outputs "HALT".
Then in the negation step, $$G$$ will run forever.
Hence the entire run of $$G(\langle G\rangle)$$ ends up with running forever. By the assumption on $$H$$, $$H(\langle G, \langle G\rangle\rangle)$$ should output "RUNS FOREVER". However, the simulated $$H$$ outputs "HALT".
• The simulated $$H$$ outputs "RUNS FOREVER".
Then in the negation step, $$G$$ will halt.
Hence the entire run of $$G(\langle G\rangle)$$ ends up with halting. By the assumption on $$H$$, $$H(\langle G, \langle G\rangle\rangle)$$ should output "HALT". However, the simulated $$H$$ outputs "RUNS FOREVER".

There is a contradiction in both cases.

### A proof of the nonexistence of $$P'$$

Towards a contradiction, suppose there is a TM $$P'$$ with the following two properties.

1. For all TMs $$M$$ and all strings $$w$$, if $$M(w)$$ accepts then $$P'(\langle M,w\rangle)$$ accepts, while if $$M(w)$$ rejects then $$P'(\langle M,w\rangle)$$ rejects.
2. $$P'(x)$$ either accepts or rejects for every input $$x$$.

We construct a machine $$Q$$ such that for all TMs $$M$$, $$Q(\langle M\rangle)$$ does the following two steps.

1. The simulation step.
Simulates $$P'(\langle M, \langle M\rangle\rangle)$$, which will either accept or reject.
2. The negation step.
If the simulated $$P'$$ accepts, rejects.
If the simulated $$P'$$ rejects, accepts.

Let us run $$Q(\langle Q\rangle)$$. There are two possible result of the simulation step.

• The simulated $$P'$$ accepts.
Then in the negation step, $$Q$$ will reject.
Hence the entire run of $$Q(\langle Q\rangle)$$ ends up with rejecting. By the assumption on $$P'$$, $$P'(\langle Q, \langle Q\rangle\rangle)$$ should reject. However, the simulated $$P'$$ accepts.
• The simulated $$P'$$ rejects.
Then in the negation step, $$Q$$ will accept.
Hence the entire run of $$Q(\langle Q\rangle)$$ ends up with accepting. By the assumption on $$P'$$, $$P'(\langle Q, \langle Q\rangle\rangle)$$ should accept. However, the simulated $$P'$$ rejects.

There is a contradiction in both cases.

The proof above is basically the same as the first proof. The difference is that "HALT" and "RUNS FOREVER" are replaced by "accept" and "reject".

### The nonexistence of $$P$$

The nonexistence of $$P'$$ above implies the nonexistence of $$P$$ as stated in the question.

I will leave this implication for you to work out.