0
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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". $\endgroup$
    – D.W.
    Apr 7, 2023 at 17:59
  • $\begingroup$ @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. $\endgroup$
    – staz6
    Apr 7, 2023 at 18:37
  • $\begingroup$ @JohnL. sadly no, I haven't been able to solve it. $\endgroup$
    – staz6
    Apr 8, 2023 at 14:06
  • $\begingroup$ @JohnL. If you have any tip, that would be extremely helpful. I'm kind of stuck at this point. $\endgroup$
    – staz6
    Apr 8, 2023 at 18:21

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.