So we can prove that the language say $A = \{ \langle M,w \rangle \mid \text{M is TM that accepts } w^R \text{ whenever it accepts } w \}$ is undecidable by assuming it is decidable and use that to construct a $TM$ deciding $A_{TM}$. So by contradiction $A$ is undecidable. But what if the language was $\{ \langle M,w \rangle \mid \text{M accepts } w \text{ but on input } w^R \text{halts and rejects} \}$?

I was thinking to prove that it's r.e, we can construct a Turing recognizer, say $K$, which recognizes this language by simulating $M$ on $w$ and do whatever $M$ does. But how does the machine know what's $w$ and $w^R$? Non determinism maybe? Or am I looking at it the wrong way?

And to prove that it's undecidable would we use the same approach as that for $A$?

  • 2
    $\begingroup$ Just to clarify, what if $w = w^{R}$? $\endgroup$ – Luke Mathieson Dec 10 '12 at 4:57
  • $\begingroup$ @LukeMathieson No pairs $\langle M, w \rangle$ where $w = w^{R}$ can be in this language. $\endgroup$ – Ben Dec 10 '12 at 23:53

Let $ A = \{\langle M, w \rangle \mid M \text { is a TM, } M \text { accepts } w \text { and on input } w^R \text { halts and rejects} \} $.

We prove that $A$ is not decidable by showing $\text{HALT}\le_m A$. The reduction works as follows. Let $\langle M, w \rangle $ be an instance of $\text{HALT}$, then we construct a Turing machine $M'$ based on $M$ and $w$. Let $M_{01}$ be some TM that accepts $01$ and rejects all other inputs. The TM $M'$ on input $v$ works now as follows

  1. $M'$ simulates $M(w)$
  2. When the simulation is finished simulate $M_{01}(v)$ and return the result of the simulation

The reduction maps $\langle M, w \rangle$ to $\langle M', 01 \rangle$.

We have now $$ \begin{align} \langle M, w \rangle \not \in \text{HALT} & \Rightarrow M' \text{cycles on every input} \\ & \Rightarrow \langle M', 01 \rangle \not \in A \end{align} $$ and \begin{align} \langle M, w \rangle \in \text{HALT} & \Rightarrow M' \text{acts as } M_{01} \\ & \Rightarrow M' \text{ accepts } 01 \text{ and rejects } 10\\ & \Rightarrow \langle M', 01 \rangle \in A \end{align}

| cite | improve this answer | |
  • $\begingroup$ No, if $w = w^R$, there simply is no M that both accepts w and rejects w. So the language does not contain any strings of the form <M, w> where w is a palindrome. But this means your reduction would always reject such <M, w>, even when M actually halts on w, so it's not a correct reduction from HALT. But why use Mlex and wmin at all? M' should just simulate M on w, then accept 01 and reject everything else. Then <M, w> is in HALT iff <M', 01> is in A. $\endgroup$ – Ben Dec 11 '12 at 12:13
  • $\begingroup$ @A.Schulz instead of using reduction, if I tried to prove it by contradiction and construct a hypothetical decider for A_{TM} using the outline provided by Ben. The decider for A_{TM} will construct M' which will behave as M on w (should accept w and reject w^R). If this simulation accepts then M' accepts. Run the decider for A on <M', w>. If this accepts, then the A_{TM} decider accepts. If it rejects, reject. This runs into trouble if w=w^R I think. $\endgroup$ – muddy Dec 11 '12 at 18:42
  • $\begingroup$ Thank you for your proof though! Much appreciated. $\endgroup$ – muddy Dec 11 '12 at 18:43

You can construct a recognizer that simply simulates M on w and then simulates M on $w^R$. This will halt in finite time for all that are in A (by definition), and then you can accept if the first simulation accepted and the second rejected. That suffices for the language being recognisable (recursively enumerable).

I'm not sure what you mean by "how does the machine know what's $w$ and $w^R$ ?" w is part of the input pair, and w^R is easily generated from it. The way you've defined the language A, you don't have to worry about guessing which is the one that M should accept and which is the one it should reject. But if the language was such that either M accepts w and rejects in finite time w^R or M rejects w in finite time and accepts w^R, then it's still easy. You do the same thing and accept if exactly one of the two simulations accepts, without caring which one.

I don't actually know a "standard" proof that $A$ is undecidable. But to prove your new language undecidable, I'd make a decider for A_TM that on input produces M' that rejects all other input than w and behaves as M on w. M' definitely rejects $w^R$ in finite time, so will be accepted by the decider for your language iff M accepts w. I imagine to prove $A$ undecidable you do the same thing but make M' accept all other strings, so it definitely accepts $w^R$ and accepts w iff the hypothetical $A$ decider accepts.

| cite | improve this answer | |
  • $\begingroup$ @muddy Hmm, actually my proof sketch is incorrect for your new language (it works for the original A that requires acceptance of $w^R$). If $w = w^R$ and M accepts $w$ then M' doesn't reject $w^R$, but <M, w> should be in A_TM. So you have to do something more complicated. I'll fix that tomorrow. $\endgroup$ – Ben Dec 11 '12 at 12:23

This is what I had mind to prove it's undecidable.

Let $ A = \{\langle M, w \rangle \mid M \text { is a TM, } M \text { accepts } w \text { and on input } w^R \text { halts and rejects} \} $

Assume $A$ is decidable. Let $H$ be a $TM$ deciding it.

Construct $TM$ $K$ deciding $A_{TM}$ as follows

$K$: ''On input $ \langle M, w \rangle :$

$ \hspace {20 mm}$ -Run $H$ on input $ \langle M, w \rangle $

$ \hspace {20 mm}$ -If $H$ accepts, then accept

$ \hspace {20 mm}$ -If $H$ rejects, then reject.''

Now $K$ decides $A_{TM}$ as it always accepts or rejects based on $H$ which will always accept or reject as it is also a decider.

$\Longrightarrow A_{TM}$ is decidable which is a contradiction.

$\Longrightarrow A$ is undecidable.

Is this right?

| cite | improve this answer | |
  • 1
    $\begingroup$ Your K is exactly equivalent to H, and just tells you whether for a given <M, w>, M accepts w and rejects w^R in finite time. But M could accept w and go in an infinite loop on w^R, or accept w^R. H would reject this pair, when A_TM requires a positive answer. So although it's a decider (assuming H exists), it doesn't decide A_TM. $\endgroup$ – Ben Dec 11 '12 at 0:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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