入力文字列を越えてヘッドを越えないようにするマシンの切断性

Question

$ L_1={\ l_1= {\ langle m、w \ rangle：m \ text {は、入力文字列を超えてヘッドを移動しないtm} $
$ L_2={\ langle m \ rangle：m \ text {は、入力文字列を過ぎず、} \} \

を超えて移動しないTMです。

上記の2つの言語を考えてみましょう。どちらを決めるかを知りたいです。

$ l_1 $ は、 $ m $ であることを知っています。入力文字列 $ w $ を使用した可能な構成であるため、組み合わせ数を過ぎて決定して決定するためのチューリングマシン（TM）を作成できます。

しかし、 $ L_2 $ の場合、それをすることができますか？ $ L_2 $ のようなものは、可能な構成に制限がないようです。

Answer 1

停止問題、 $ \ mathsf {halt} $ $ \ overline {l_2} $ 。

TM $ T $ と入力 $ w $ 、新しいTM $ n $ 長さ $ n $ の入力で、 $をシミュレートします。 $ w $ $ n $ 手順で、次に停止します。 $ t $ $ n $ 手順、 $ n $ はその頭を永遠に右に移動します。

上記の減少にはギャップがあります。 $ n $ の場合 $ t $ $ w $ $ n $ の場合、それが左に移動したときに入力から出ることがあります（私たちは原点の右側に入力されると仮定します。 $ n $ のヘッド、clusubleの初期位置。このギャップは「テープの翻訳」の古典的なトリックによって解決することができます。シミュレーションが原点の左側への移動に関するものである場合、 $ n $ テープの電流を右に変換します。その後、 $ n $ は、起源の左側のセルであるかのように、原点になります。このようにして、 $ n $ が、シミュレートされた $ tの限り入力文字列から出ません。 $ w $ の$ は停止しません。 （ $ n $ を有効にするには、オリジンを認識するために、元のシンボルも指示する「複合」シンボルで常に原点をマークします。たとえば、元の場合は原点のシンボルは $ a $ 、 $ n $ に $ A_O $ 、 $ a $ ではないシンボルですが、 $ a $ 。 "Compys"シンボルは、 $ n $ の場合もテープの内容を変換するときにも使用されます。）

$ \ mathsf {halt} $ は決定できません、 $ \ overline {l_2} $ 決定できません。そのため、 $ L_2 $ は決まっていません。