有一个决策者决定{<M>|M是TM和|L(M)|=n}，建立一个决策者决定n-1
Have a decider decides {<M>|M is TM and |L(M)|=n}, build a decider decides n-1
这可能吗？
假设我们有一个决策者决定 {|M 是一个 TM 并且 |L(M)|=n}
想要建立一个决策者决定{|M是一个TM并且|L(M)|=n-1}
如果可以，怎么做？
看到我们可以决定|L(M)| = n - 1，想象为语言 L(N) = L(M) U {a} 构造一个 TM N，其中 a 是不在语言 L(M) 的字母表中的符号。 N 将完全接受 M 接受的字符串，加上 M 不可能接受的另一个字符串。因此，当且仅当 M 接受 n - 1 个字符串时，N 接受 n 个字符串。决定是否|L(M)| = n - 1，那么，运行 我们对 N 的决策者就足够了，看看是否 |L(N)| = n.
这可能吗？ 假设我们有一个决策者决定 {|M 是一个 TM 并且 |L(M)|=n} 想要建立一个决策者决定{|M是一个TM并且|L(M)|=n-1} 如果可以，怎么做？
看到我们可以决定|L(M)| = n - 1，想象为语言 L(N) = L(M) U {a} 构造一个 TM N，其中 a 是不在语言 L(M) 的字母表中的符号。 N 将完全接受 M 接受的字符串，加上 M 不可能接受的另一个字符串。因此，当且仅当 M 接受 n - 1 个字符串时，N 接受 n 个字符串。决定是否|L(M)| = n - 1，那么，运行 我们对 N 的决策者就足够了，看看是否 |L(N)| = n.