mapreduce - 让决策者决定 {|M 是 TM 和 |L(M)|=n}，建立一个决策者决定 n-1

Question

这可能吗？假设我们有一个决策者决定 {|M 是一个 TM 并且 |L(M)|=n} 想要构建一个决策者决定 {|M 是一个 TM 并且 |L(M)|=n-1} 如果可能，如何？

Answer 1

看到我们可以决定|L(M)| = n - 1，想象为语言 L(N) = L(M) U {a} 构造一个 TM N，其中 a 是不在语言 L(M) 的字母表中的符号。N 将完全接受 M 接受的字符串，以及 M 无法接受的另一个字符串。因此，N 接受 n 个字符串当且仅当 M 接受 n - 1 个字符串。决定是否|L(M)| = n - 1，那么，在 N 上运行我们的判定器并查看是否 |L(N)| 就足够了。= n。