具有决定器决定{<M> | M是TM和| L（M）| = N}，建立一个判定器判定N-1

Question

这是可能的？ 假设我们有一个决定器决定{| M是一个TM和| L（M）| = N} 要建立一个决定器决定{| M是一个TM和| L（M）| = N-1} 如果可能的话，如何？

Answer 1

看到我们可以决定| L（M）|假设为语言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。