具有決定器決定{<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。