[Solved]: Showing undecidability

Problem Detail: 

I'm given the set $T = \{\langle M, w\rangle : M $ is a Turing Machine that accepts $w^\mathcal R$ whenever it accepts $w \}$ and I want to show it's undecidable but recognizable. (I'm using the bracket notation to denote the encoding of the TM and input string)

Given that I know the set $A = \{\langle M,w\rangle : M \text{ accepts } w \}$ is undecidable but recognizable, I'm trying to show that $A$ reduces to $T$. I start by assuming that $T$ is decided by a Turing Machine $R$ and then attempt to construct a new Turing Machine, $S$, that will decide $A$ by using $R$ as a subroutine.

To construct this new machine $S$, I will run $R$ on input $\langle M,w\rangle$. If $R$ accepts, then $\langle M,w\rangle$ is in $A$. However, $R$ rejecting doesn't necessarily mean that $\langle M,w\rangle$ isn't in $A$, since $M$ might reject $w$ reversed but accept $w$. So now I'm confused on how to actually construct the reduction. Any help would be great

Asked By : Brutus

Answered By : Denis Pankratov

I am interpreting the word "whenever" in the definition of $T$ to mean that $T$ consists of all pairs $\langle M, w \rangle$ such that either $M$ accepts $w$ and $w^R$ or $M$ rejects $w$ and $w^R$. Please, correct me if this is wrong.

I will show a reduction from $A$ to $T$. Input $\langle M, w\rangle$ will be transformed to $\langle M', w'\rangle$ as follows:

1. $w' = 0w1$
2. $M'$ on input $w'$ strips the first bit $b_1$ and last bit $b_2$ off $w'$. Let $w$ be the remaining string. If $b_1 = 0$ then $M'$ runs $M$ on $w$ and outputs accordingly. Otherwise, if $b_1 = 1$ then $M'$ simply accepts.

I claim that $\langle M, w \rangle \in A$ if and only if $\langle M', w' \rangle \in T$:

• If $M$ accepts $w$ then $M'$ on $0w1$ simulates $M$ on $w$ and accepts. Also, $M'$ on $(0w1)^R = 1w^R0$ immediately accepts, since the first bit is $1$. Thus, $\langle M', w' \rangle \in T$.
• If $M$ doesn't accept $w$ then $M'$ on $0w1$ simulates $M$ on $w$ and doesn't accept. However, $M'$ on $w^R = 1w^R0$ accepts. Thus, $\langle M', w' \rangle \notin T$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52987

3.2K people like this

 Download Related Notes/Documents