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

Question

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.

Answer 1

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.