algorithmcomputer-sciencecomplexity-theoryturing-machinescomputability

Let T = {<M> | M is a TM that accepts $w^R$ whenever it accepts w}. Show that T is undecidable

Let T = {<M> | M is a TM that accepts wr whenever it accepts w}.
Show that T is undecidable.

I have two answers to this question - San Diego:

5.9
Let T = { <M> | M is a TM that accepts wr whenever it accepts w }.

Assume T is decidable and let decider R decide T. Reduce from ATM by constructing a TM S as follows:

  • S: on input <M,w>
    1. create a TM Q as follows:
      On input x:
      1. if x does not have the form 01 or 10 reject.
      2. if x has the form 01, then accept.
      3. else (x has the form 10), Run M on w and accept if M accepts w.
    2. Run R on
    3. Accept if R accepts, reject if R rejects.

Because S decides ATM, which is known to be undecidable, we then know that T is not decidable

Undisclosed source:

  • 5.12 We show that ATM ≤m S by mapping ‹M, w› to ‹M'› where M' is the following TM:

    • M' = “On input x:
      1. If x = 01 then accept.
      2. If x ≠ 10 then reject.
      3. If x = 10 simulate M on w.
        If M accepts w then accept; if M halts and rejects then reject.”

    If ‹M, w› ∈ ATM then M accepts w and L(M') = {01,10}, so ‹M'› ∈ S.
    Conversely, if ‹M, w› ∉ ATM then L(M') = {01}, so ‹M'› ∉ S. Therefore,
    ‹M, w› ∈ ATM ⇔ ‹M'› ∈ S.

But I do not understand the following:

1- what is the relation between x and w?

2- why we consider the 2 cases ‹M, w› ∈ ATM and ‹M, w› ∉ ATM?

3- why if A is mapping reducible to S this makes S undecidable?

could anyone clarify these points for me?

Solution

  • I think it is not suitable for asking in SO because it is not a educational website, but I answered it.

    1- what is the relation between x and w?

    Answer 1: x is a symbol that used for using a symbol for operate. This symbol should not be in alphabet of language, just it. It hasn't any relation to w.

    2- why we consider the 2 cases ‹M, w› ∈ ATM and ‹M, w› ∉ ATM?

    Answer 2: For proofing a language like L is decidable or not, we need to determine a string like w is member of language or not. So we have to consider two type of string w∉L and w∈L.

    3- why if A is mapping reducible to S this makes S undecidable?

    Answer 3: It means the process of checking a string is in language in A and S is similar and if we can't find a algorithm for checking this for A, we can't find any algorithm for S.