1
$\begingroup$

a friend of mine sent me a question which he can't solve and I didn't succeed to solve it as well.

Question: We define two languages:

$$ACCEPT=\{\langle M,w\rangle\ \ |\ M\ is \ a\ turing\ machine.\ M\ accepts\ w \}$$ $$REJECT=\{\langle M,w\rangle\ \ |\ M\ is \ a\ turing\ machine.\ M\ \ halts\ on\ w\ and\ rejects\ it \}$$

Note: $\overline{ACCEPT} \neq REJECT$

The question is to prove that $REJECT\leq_mACCEPT$ and vice versa.

What I think:

I had an idea to run $M$ on $w$ and return the opposite of what it returns but I think there's a problem because of the halts on w statement.

$\endgroup$
5
  • 1
    $\begingroup$ Can you be more explicit on what you think the problem is? $\endgroup$
    – Steven
    Apr 27, 2022 at 16:39
  • $\begingroup$ I had written an answer. However, Steven raised a good question. $\endgroup$
    – John L.
    Apr 27, 2022 at 16:45
  • $\begingroup$ @CSStudent "what I've written is true". If that means you have written a correct solution, why not post it as an answer here? It will be great to witness that you become a tearcher on this site! $\endgroup$
    – John L.
    Apr 27, 2022 at 17:18
  • $\begingroup$ @JohnL. Let's assume we're proving that $REJECT \leq_m ACCEPT$. If we follow the above solution then let's assume that $\langle M,w \rangle \notin REJECT$, For this, there are two cases, first, $M$ halts on $w$ and accepts it, and therefore $\langle M,w \rangle \in ACCEPT$. $M$ enters an infinite loop on $w$ and therefore $\langle M,w \rangle \in ACCEPT$ which is a contradiction to the second condition. $\endgroup$
    – Mohamad S.
    Apr 27, 2022 at 17:32
  • 1
    $\begingroup$ If $M$ does not halt on $w$, then $M$ does not accept $w$ (i.e., $\langle M, w \rangle \not\in \text{ACCEPT}$) $\endgroup$
    – Steven
    Apr 27, 2022 at 20:03

1 Answer 1

1
$\begingroup$

There might have been confusion on the meaning of "return the opposite of what it returns" when you run $M$ on $w$.

When $M$ runs forever, nothing can be returned by $M$. Then that rule does not make sense! Not only there is no way to specify "the opposite of" nothing, but also it is simply impossible to return, i.e., to halt.

By the way, note that there is huge difference between "halt and return nothing" and running forever. In the case of running forever, a running machine does not return anything, either. Note that "it returns nothing" might be ambiguous.

The right specification is to stipulate "return the opposite of what is returns when it halts". The condition "when it halts" should be present, although it might be skipped in sloppy writing or in well-understood context.

The better choice could be sticking to "accept", "reject", "halt" and "loop" and abandoning the word "return" when we are talking about decision problems.


Since the question involves Turing machines that can reject, let us define a Turing machine as an 8-tuple $\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},A, R\rangle$, where $Q,\Gamma ,b,\Sigma ,\delta ,q_{0}$ are as usual and $A$ and $R$ are the set of accepting and rejecting states respectively. A Turing machines halts means it either accepts or rejects and vice versa.

Here is a clearer description of the wanted reduction.

Given $\langle M,w\rangle$, switch the set of accepting states and the set of rejecting states in $M$ to obtain a new Turing machine $M'$. More specifically, $M$ is the same as $M'$ except that each accepting state in $M$ will be defined as a rejecting state in $M'$ and each rejecting state in $M$ will be defined as an accepting state in $M'$. More formally, if $M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},A, R\rangle$, then $M'=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},R, A\rangle$.

Let $f:\Sigma^*\to\Sigma^*$ be defined by $f(u)=\langle M', w\rangle$ if $u=\langle M,w\rangle$ and $f(u)=u$ otherwise.

We can check routinely that the map $f$ is a one-to-one Turing reduction from $REJECT$ to $ACCEPT$ as well as a one-to-one Turing reduction from $ACCEPT$ to $REJECT$.

$\endgroup$
1
  • 1
    $\begingroup$ Oh you’re right this ‘return’ may have confused me a little bit, my problem was mostly with infinite loops but thanks to you it’s more clearer for me now. $\endgroup$
    – Mohamad S.
    Apr 29, 2022 at 11:13

Your Answer

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

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