Undecidability of the following language

Question

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$?

Answer 1

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}

Answer 2

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.

Answer 3

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?