を受け入れる非決定性チューリングマシンのプログラムを説明するように求められる宿題の問題がありますL = {a^n: n is prime}。どうすればいいのかわかりません。私はnを知っていますか？sを単項桁として使用してaカウントしますか？文字列を無視して、主にnをテストすることはできますか？またはプライム値がわかっているので、それらのセルの場所だけが状態を受け入れており、通常のようにデータを読み取ることができますか？
どうすればいいですか？
10417 次
2 に答える
5
最初に、どこかのメモリ位置を使用して、文字列が素数の長さであるかどうかにフラグを立ててから、ネスが提案したことを多かれ少なかれ行うことができます（ただし、彼の答え全体はよくわかりません）。
エラトステネスのふるいを使います。長さ 2 のヘルパー文字列で開始し、入力文字列とヘルパー文字列を右に 1 つ移動し、ヘルパー文字列の終了文字に到達するとヘルパー文字列の先頭に戻り、入力の終了文字に到達するまで続けます。ストリング。このようにして、ヘルパー文字列が入力文字列を分割しているかどうかを確認できます。次に、長さ 3 のヘルパー文字列に移動して、同じことを行います。ヘルパー文字列の長さがどれも入力文字列の長さを分割しない場合にのみ、入力文字列の長さが素数になります。1 つのヘルパー文字列の長さが入力文字列の長さを分割する場合は、フラグ メモリ スロットを使用してそれを示します。そして、アルゴリズムにフラグ メモリ スロットをチェックさせ、フラグが立てられている場合は、文字列を拒否できるようにすべての処理を中止します。
これで、入力の反復処理中の任意の時点で、内側のループからの非決定論的なジャンプが許可されるため、マシンは次の長さのヘルパー文字列のテストを開始できます。このように、ある意味では、すべての長さのヘルパー文字列が同時にテストされますが、フラグ スロットにフラグが立てられると、それらはすべて処理を停止し、文字列を拒否します。
最後の問題を 1 つ。文字列は、非素数であることが判明する前に受け入れられる場合があります (時間はここでは一種の非概念ですが)。あなたがその問題を解決できれば、あなたは私の一歩先を行っています。
PSドリニアスは悪です
于 2012-04-12T19:08:29.047 に答える
2
実際の無制限のエラトステネスのふるいを原点の左側にテープで配置できます。
非決定性により、各状態に複数の遷移規則を設定できます。したがって、 の増分で左に移動する場合n、各ポイントで次のいずれかを行うことができます。左に進み、 の増分でテープに印を付け続けますn。またはb。原点からやり直し、次のn.
次に、2 つのルールを使用して開始状態を作成します (おそらく、テープに記録されているのは s のみで他には何もないことを確認した後)a : ２の倍数のマーキングを開始し、ｂ．（ふるいがすでに設置されていると仮定します）sを数え、原点の左側にあるマークされた素数を使用して、受け入れるかどうかを決定します.a
したがって、最初のテープは、最終的........aaaaaaa.........に次のようになります.c.ccccc.ccc.c.ccc.c.ccc[p]cpcpp.OaaaaaaaA...x.y.z...([]テープの最終的なヘッド位置をマークします)。
于 2012-04-12T12:03:21.783 に答える