2
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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$.
$\endgroup$

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.