mapreduceturing-machinesdecidable

Have a decider decides {<M>|M is TM and |L(M)|=n}, build a decider decides n-1


Is this possible? Suppose that we have a decider decides {|M is a TM and |L(M)|=n} Want to build a decider decides {|M is a TM and |L(M)|=n-1} If possible, how?


Solution

  • To see that we can decide |L(M)| = n - 1, imagine constructing a TM N for a language L(N) = L(M) U {a}, where a is a symbol not in the alphabet of the language L(M). N will accept exactly the strings that M accepts, plus this one other string that M could not possible accept. Therefore, N accepts n strings if and only if M accepts n - 1 strings. To decide whether |L(M)| = n - 1, then, it suffices to run our decider on N and see whether |L(N)| = n.