{<M> | 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が受け入れることができなかったこの他の文字列を正確に受け入れます。したがって、Mがn - 1文字列を受け入れる場合に限り、Nはn個の文字列を受け入れます。 | L（M）| = n - 1ならば、決定器をNで実行し、| L（N）| = n。