空の入力で2回の開始状態を訪れるTMSのセットが決定不可能であることを示す

Question

私はそれを証明しようとしています

$ l_1 = { langle m rangle mid m text {はチューリングマシンと訪問} q_0 text {少なくとも2回} varepsilon } notin r $。

停止の問題を減らすかどうかはわかりません。 $（ langle m rangle、w）$ for $（ langle m rangle、w）$ for $ m '$の新しいマシンを作成しようとしました。これは特定の$ Q_0 $ですが、私はスマートな構造には来ませんでした。たぶん、それが$ core $ではなく$ re $であることを示す方が簡単ですか？ $ re $であることは明らかであり、$ l_2^{c} $が$ re $ではないことを示す必要があります。

私は何をすべきか？

Answer 1

これをそれよりも複雑にしないでください。完全なソリューションを提供する代わりに、私はあなたに部分的な解決策を与えます。これにより、自分で詳細を解決できるようになります。

すべてのTMは、初期状態を1回訪れるTMに変換されます。そのために、新しい状態$ q^'_ 0 $を紹介します。これは新しい開始状態になります。次に、$ q^'_ 0 $から$ q_0 $から$ varepsilon $ -Transitionを追加します。これは、状態$ q'_0 $を「残す」唯一の方法です。

この変更されたマシンの場合、受け入れたランは初期状態を1回訪問し、受け入れた状態で終わります。残されているのは、マシンが受容状態になった後に$ q^'_ 0 $に戻るように、マシンをさらに変更することです。ただし、$ q^'_ 0 $が2回目に訪問されると、新しい受け入れ状態にジャンプすることを保証する必要があります。しかし、どのくらいの頻度で州を訪れたかを記録することは難しくありません。

別の状態を2回訪問したい場合は、この状態を訪れる最初にいつでも迂回することができます（マシンが「迂回」モードであることを記録します。通常の計算を再ルーティングするよりも、要求された状態を訪問する必要がある場合、この状態のコピーを訪問します。最後に、受け入れると、要求された状態に戻ります。概念的には、これは州をリラックスすることとそれほど違いはありません。