algorithm - 让 T = {| M 是一个在接受 w} 时接受 $w^R$ 的 TM。证明 T 是不可判定的

Question

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

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

5.9
令 T = { <M> | M 是一个 在接受 w } 时接受 w ^{r的 TM。}

假设 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我们通过将‹<em>M, w ›映射到‹<em>M'›来 证明A _TM ≤<sub>m S ，其中M'是以下TM：

  • M' = “在输入x上：
    1. 如果x = 01 则接受.
    2. 如果x ≠ 10 则拒绝。
    3. 如果x = 10在w上模拟M。 如果M接受w然后接受; 如果M停止并拒绝，则拒绝。”
       

  如果 ‹<em>M, w › ∈ A _TM那么M接受w并且L ( M' ) = {01,10}，所以 ‹<em>M'› ∈ S。
  相反，如果 ‹<em>M, w › ∉ A _TM则L ( M' ) = {01}，所以 ‹<em>M'› ∉ S。因此，
  ‹<em>M, w › ∈ A _TM ⇔ ‹<em>M'› ∈ S。

但我不明白以下内容：

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

2- 为什么我们考虑 ‹<em>M, w › ∈ A _TM和‹<em>M, w › ∉ A _TM这两种情况？

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

谁能为我澄清这些观点？

Answer 1

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

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

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

2- 为什么我们考虑 ‹M, w› ∈ ATM 和 ‹M, w› ∉ ATM 这两种情况？

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

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

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