让 T = {<M> | M 是一个 TM，只要它接受 w} 就接受 $w^R$。证明 T 是不可判定的
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.
这个问题我有两个答案 - 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>
- create a TM Q as follows:
On input x:
- if x does not have the form 01 or 10 reject.
- if x has the form 01, then accept.
- else (x has the form 10), Run M on w and accept if M accepts w.
- Run R on
- 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
未公开来源：
5.12 We show that ATM ≤m S by mapping ‹M, w› to ‹M'› where M' is the following TM:
- M' = “On input x:
- If x = 01 then accept.
- If x ≠ 10 then reject.
- 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.
但我不明白以下内容：
1-x和w的关系是什么？
2- 为什么我们考虑这两种情况 ‹M, w› ∈ A TM and ‹M, w› ∉ ATM?
3- 为什么如果 A 映射可归约到 S 这使得 S 不可判定？
谁能帮我澄清一下这些要点？
我觉得不适合在SO里面问，因为不是教育网站，但是我回答了
1-x和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- 为什么我们考虑这两种情况‹M, w› ∈ ATM 和‹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- 如果 A 映射可归约到 S，为什么这会使 S 不可判定？
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.
Let T = {<M> | M is a TM that accepts wr whenever it accepts w}.
Show that T is undecidable.
这个问题我有两个答案 - 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>
- create a TM Q as follows:
On input x:
- if x does not have the form 01 or 10 reject.
- if x has the form 01, then accept.
- else (x has the form 10), Run M on w and accept if M accepts w.
- Run R on
- 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
未公开来源：
5.12 We show that ATM ≤m S by mapping ‹M, w› to ‹M'› where M' is the following TM:
- M' = “On input x:
- If x = 01 then accept.
- If x ≠ 10 then reject.
- 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.
但我不明白以下内容：
1-x和w的关系是什么？
2- 为什么我们考虑这两种情况 ‹M, w› ∈ A TM and ‹M, w› ∉ ATM?
3- 为什么如果 A 映射可归约到 S 这使得 S 不可判定？
谁能帮我澄清一下这些要点？
我觉得不适合在SO里面问，因为不是教育网站，但是我回答了
1-x和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- 为什么我们考虑这两种情况‹M, w› ∈ ATM 和‹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- 如果 A 映射可归约到 S，为什么这会使 S 不可判定？
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.