Wordを受け入れる前に、チューリングマシンが少なくともK> 2状態を通過するかどうかを確認する

Question

$ l={\ langle m、k \ rangle \ mid \ mid \ inest w \ in l（m）\ text {$ m $が少なくとも渡すような $ k> 2 $ $ w $} \} \}} $

この言語がREもコアもないことを証明するために縮小を考えてみてください。 この問題に近づく方法ヒント、または直感がありますか？

私は通常米を使うことができるかどうかを確認しますが、ここでの質問は言語それ自体についてではありません

Answer 1

明らかに $ L $ は受け入れられます（ $ m $ をシミュレートし、その数を追跡します。シミュレーション中に異なる状態が発生しました。私たちは今それが決まっていないことを示す。

$ l $ が決定できなかった場合は、次のように停止問題を解決できるようになります。 TM $ t $ と入力 $ x \ in \ sigma ^ * $ 、tmを構築する $ m $ それはその入力を無視する、 $ t $ を入力 $ x $ 、シミュレーションが完了したら、受け入れます。 $ m $ が受け入れる場合は、少なくとも $ 3 $ 異なる状態を走査することもできます。 $ t $ のシミュレーションを開始する前に、初期状態から別の状態に移行するだけで遷移するだけです。

$ \ langle m、3 \ rangle \ in l $ かどうかを確認します。答えが肯定的であれば、 $ m（w）の $ w \ in \ sigma ^ * $ があります。 $ を受け入れ、 $ t（x）$ x haltsを表示します。 答えがマイナスの場合、 $ m $ が停止することはありません。 $ t（x）$ x ではありません停止。