令 T = {<M> | M 是一个 TM，只要它接受 w}，它就接受 $w^R$。证明 T 是不可判定的

Question

令 T = {<M> | M 是一个 TM，只要它接受 w}，它就接受 w ^r。
证明 T 是不可判定的。

我对这个问题有两个答案 -圣地亚哥：

5.9
令 T = { <M> | M 是一个 TM， 只要它接受 w } 就接受 w ^r。

假设 T 是可判定的，让决策者 R 决定 T。通过构造一个 TM S从 A _TM减少如下：

• S：在输入 <M,w> 上
  1. 如下创建 TM Q：
     在输入 x 上：
     1. 如果 x 没有表格 01 或 10 拒绝。
     2. 如果 x 的形式为 01，则接受。
     3. 否则（x 的形式为 10），在 w 上运行 M，如果 M 接受 w，则接受。
  2. 运行 R
  3. 如果 R 接受则接受，如果 R 拒绝则拒绝。

因为 S 决定了 A _TM，已知它是不可判定的，所以我们知道 T 是不可判定的

未公开来源：

• 5.12 我们证明A _TM ? _m S通过映射 ‹ M , w › 到 ‹ M' › 其中M'是以下 TM：

  • M' = “在输入x 上：
    1. 如果x = 01 则接受。
    2. 如果x ? 10 然后拒绝。
    3. 如果X = 10模拟中号上瓦特。
       如果M接受w则接受；如果M停止并拒绝，则拒绝。”

  如果 ‹ M , w › ? 一个_TM然后M接受w并且L ( M' ) = {01,10}，所以 ‹ M' › ? 小号。
  相反，如果‹ M , w › ? A _TM然后L ( M' ) = {01}，所以 ‹ M' › ? 小号。因此，
  ‹ M , w › ? 一个_TM？‹ M' › ? 小号。

但我不明白以下内容：

1- x 和 w 之间的关系是什么？

2- 为什么我们考虑 2 种情况 ‹ M , w › ？一个_TM和 ‹ M , w › ? 一个_TM？

3- 为什么如果 A 映射可约到 S 这会使 S 不可判定？

有人可以为我澄清这些要点吗？

Answer 1

我认为它不适合在SO中提问，因为它不是一个教育网站，但我回答了。

\n\n

1-x和w之间有什么关系？

\n\n

\n

答案1： x是一个符号，用于使用符号进行操作。这个符号不应该出现在语言的字母表中，只是它。它与 w 没有任何关系。

\n

\n\n

2-为什么我们考虑两种情况 \xe2\x80\xb9M, w\xe2\x80\xba \xe2\x88\x88 ATM 和 \xe2\x80\xb9M, w\xe2\x80\xba \xe2\x88\x89自动提款机？

\n\n

\n

答案2：为了证明像 L 这样的语言是否是可判定的，我们需要确定像 w 这样的字符串是否是语言的成员。所以我们必须考虑两种类型的字符串 w\xe2\x88\x89L 和 w\xe2\x88\x88L。

\n

\n\n

3-为什么如果 A 映射可简化为 S 这会使 S 不可判定？

\n\n

\n

答案3：这意味着检查 A 和 S 中语言的字符串的过程是相似的，如果我们找不到 A 的检查算法，那么我们也找不到 S 的任何算法。

\n

\n