次の言語を受け入れるTMの存在を証明する

Question

私は問題にどのように近づくかという考えがありますが、それについてはわかりません。 チューリングマシンを考えると、実行がテープの無限のセルを使用するかどうかを確認する州の数を確認できます。 ただし、州の数と確認する必要があるものを使用できる方法はわかりません。 私を混乱させるのは、無限ループに入ることは必ずしもフィルムの無限の細胞の使用を必要としないということです。

$ l_k={ |\、m \、\、\、\、\、a \、\、tm \、\、\、\、\、\、\、\、\、\、\、\、\、\、k \、\、tape\、\、cells \、\、\、\、\、\、running \、\、\、on \、\、\、\ epsilon \} $

それを証明する： $ l ^ *=bigcup \ limits_ {k \、\ in \、\ mathbb {n}} l_k \、\ in \、\、\、\、\、\、\ setminus r $

Answer 1

言語 $ l ^ * $ <$ は、すべてのチューリングマシン $ m $ で構成されています。または設定を繰り返します。マシン $ m $ について、マシンをシミュレートすることによって、これらの可能性の1つが起こったことを簡単に観察することができます。