小编Int*_*ion的帖子

令 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 …