Showing a Problem Is Undecidable

200 Views Asked by At

How can I show that T is undecidable using only this information?

$$T = \{\langle M, w, r\rangle \mid M \text{ accepts } w^r \text{ when it accepts } w.\}$$

So, what it's saying is that the machine will accept the string w or length r if it initially accepts w, right?

How can I prove it's undecidable? My thought is, what if it does not accept w, then it cannot accept w^r, but there must be more to it than that.

1

There are 1 best solutions below

1
On BEST ANSWER

General tip for such questions: Don't search for obstacles in trying to prove decidability, but rather explore the consequences if the property were decidable.

I am assuming you mean the language:

$$T := \{\langle M, w, r\rangle \mid M \text{ accepts } w^r \Leftarrow M \text{ accepts } w\}$$

Given some TM $M$, let $M'$ be defined as follows: On input $0$, $M'$ accepts and halts. On input $00$, $M'$ simulates $M$ with empty input. On any other input, $M'$ accepts and halts. We can compute $M'$ from $M$.

Now note that $M \in H \Leftrightarrow \langle M',0,2\rangle \in T$, so if $T$ were decidable, we could decide the Halting problem.