問題タブ [turing-machines]

試験の復習をしているときに、Sipser 著「An Introduction to the Theory of Computation」という本からの次の質問に答えるのに苦労しています。残念ながら、本書にはこの問題の解決策はありません。

以下が正当なチューリング マシンではない理由を説明してください。

M = {

入力は、変数 x1、...、xn 上の多項式 p です。

1. x1、...、xn のすべての可能な設定を整数値にしてみてください
2. これらすべての設定で p を評価します
3. これらの設定のいずれかが 0 と評価された場合は受け入れます。それ以外の場合は拒否します。}

これは私を夢中にさせています！整数のセットが無限だからだと思いますか? これはどういうわけかアルファベットの許容サイズを超えていますか?

私はこの理論的な質問に対する答えを見つけるのに苦労してきました。それが直接プログラミングの質問ではない場合でも、それは本当に関連していると思います。

1000平方を超えることのできないチューリングマシンのタイプを想定します。そのようなタイプの認識可能な言語のセットと通常の認識可能な言語のセットとの間の関係は何でしょうか。

マシンのチューリングと停止問題について質問があります。

Atm = {(M,w) ここで、M はチューリング マシンで、w は入力} であり、
HALTtm = {(M,w) ここで、M はチューリング マシンであり、入力 w で停止するとします。

HALTtm <=m Atm であることを証明したい

いくつかの方法を試しましたが、解決には程遠いと思います。誰でもいくつかの手がかりを与えることができますか??

ターニング マシンのプロジェクトに取り組んでいますが、手順の概念化に問題があります。

私の理解に基づいて、数値をバイナリに変換しますが、数値の立方体をバイナリで見つけるにはどうすればよいですか。

また、立方体をテープに書き込むにはどうすればよいですか。

これまでのところ、0 ～ 9 のバイナリ バージョンを受け入れる状態図を作成する必要があると考えていますが、次はどうすればよいでしょうか。

別のプログラムをチェックするプログラムが存在できない理由について、論理的なアランチューリングの説明を見つけようとしています。

計算コースで学んだことを覚えていますが、今は解決策を見つけることができず、職場の誰かに説明する必要があります。

手伝ってくれてありがとう。

バックグラウンド

Von-Neumannアーキテクチャは、命令とデータがメモリに格納され、マシンが内部状態を変更することによって動作するストアドプログラムコンピュータを記述します。つまり、命令は一部のデータを操作し、データを変更します。したがって、本質的に、システムには状態が維持されます。

チューリングマシンのアーキテクチャは、テープ上のシンボルを操作することによって機能します。つまり、スロットの数が無限のテープが存在し、任意の時点で、チューリングマシンは特定のスロットにあります。そのスロットで読み取られたシンボルに基づいて、マシンはシンボルを変更して別のスロットに移動できます。これはすべて決定論的です。

質問

1. これら2つのモデルの間に何か関係はありますか？フォンノイマンモデルはチューリングモデルに基づいているか、チューリングモデルに触発されましたか？

2. チューリングモデルはフォンニューマンモデルのスーパーセットであると言えますか？

3. 関数型プログラミングはチューリングモデルに適合しますか？もしそうなら、どのように？関数型プログラミングはフォンノイマンモデルにはうまく役立たないと思います。

プログラミング言語に関連するチョムスキー階層のいくつかの側面を学ぼうとしていますが、まだドラゴンブックを読まなければなりません。

ほとんどのプログラミング言語は文脈自由文法 (CFG) として解析できると読みました。計算能力に関しては、プッシュダウン型の非決定性オートマトンに匹敵します。私は正しいですか？

それが本当なら、チューリングが完了している無制限文法 (UG) を CFG がどのように保持できるのでしょうか? プログラミング言語がCFGで記述されていても、実際にはチューリングマシンを記述するために使用されているため、UGを介して質問しています。

それは、少なくとも 2 つの異なるレベルのコンピューティングによるものだと思います。1 つ目は CFG の解析であり、言語の構造 (表現?) に関連する構文に焦点を当て、もう 1 つはセマンティック (意味、解釈) に焦点を当てています。チューリングが完了しているプログラミング言語の機能に関連しています。繰り返しますが、これらの仮定は正しいですか?

ニューラルネットの計算能力に興味があります。リカレントニューラルネットはチューリング完全であると一般に認められています。今、私はこれを証明するいくつかの論文を探していました。

私がこれまでに見つけたもの：

• ニューラルネットを使用したチューリング計算可能性、HavaT.SiegelmannおよびEduardoD.Sontag、1991年

  これは理論的な観点からのみ興味深いと思います。なぜなら、それは無限の正確さのニューロン活動を持っている必要があるからです（何らかの形で有理数として状態をエンコードするため）。

• S.フランクリンとM.ガーゾン、ニューラル計算可能性

  これには無制限の数のニューロンが必要であり、実際にはそれほど実用的ではないようです。

（私の別の質問は、そのような理論的結果と実践の間のこの種の問題を指摘しようとしていることに注意してください。）

私は主に、実際にシミュレートしてテストできるコードを実際に実行できるニューラルネットを探しています。もちろん、実際には、彼らはある種の限られた記憶を持っているでしょう。

誰かがこのようなことを知っていますか？

以前、ステート マシンについて話し合っていたのですが、何らかの入力で停止しないのではないかという質問がありました。重要で頻繁に言及されるステート マシンのプロパティのように思えますが、そのプロパティの名前が何なのか、一生わかりません。そのような用語はありますか？それは「停止可能」、「無限ループではない」、または何か他のものですか?

正規表現からチューリング マシンを生成するソフトウェアを開発しています。

[ 編集: 明確にするために、OP は正規表現を入力として受け取り、同じタスクを実行するためにチューリング マシンをプログラムで生成したいと考えています。OPは、正規表現を使用するのではなく、正規表現からTMを作成するタスクを実行しようとしています。]

最初に、私が行ったことを少し説明し、次に私の問題を説明します。

次のように正規表現をモデル化しました。

RegularExpression (インターフェース): 以下のクラスはこのインターフェースを実装します

単純 (例: "aaa"、"bbb"、"abcde"): これは部分式を持たないリーフ クラスです。

ComplexWithoutOr (例: "a(ab)*","(a(ab) c(b) )*"): このクラスには、RegularExpression のリストが含まれます。

ComplexWithOr (つまり: "a(a|b) ","(a((ab) |c(b) ) "): このクラスには Or 演算が含まれ、RegularExpression のリストが含まれます。これは、"a|b最初の例の " の部分と、2 番目の例の "(ab) |c(b) " です。

変数 (つまり: "awcw"、ここで w E {a,b}*): これはまだ実装されていませんが、Simple とは異なるロジックを持つリーフ クラスとしてモデル化することを目的としています。例の「w」の部分を表します。

上記のモデルを理解し、同意することが重要です。質問がある場合は、続きを読む前にコメントしてください...

MT 生成に関しては、さまざまなレベルの複雑さがあります。

簡単です。このタイプの式はすでに機能しています。文字ごとに新しい状態を生成し、右に移動します。いずれかの状態で、読み取られた文字が予期されたものではない場合、「ロールバック回路」が開始され、MT ヘッドが初期位置で終了し、最終状態ではない状態で停止します。

ComplexWithoutOr: ここに私の問題があります。ここで、アルゴリズムは部分式ごとに MT を生成し、それらを連結します。これはいくつかの単純なケースでは機能しますが、ロールバック メカニズムに問題があります。

私のアルゴリズムではうまくいかない例を次に示します。

"(ab) abac": これは、ComplexWithOr 式 "(ab) " ("ab" 内に Simple 式を持つ) と Simple 式 "abac" を含む ComplexWithoutOr 式です。

私のアルゴリズムは、最初に "ab" の MT1 を生成します。この MT1 は "(ab)*" のために MT2 によって使用されるため、MT1 が成功すると MT1 に再び入ります。つまり、MT2は失敗できません。

次に、「abac」の MT3 を生成します。MT2のアウトプットがMT3のインプットです。MT3の出力は実行結果です

ここで、この入力文字列を「abac」とします。ご覧のとおり、正規表現と一致します。では、MT を実行するとどうなるか見てみましょう。

MT1 は最初の "ab" で実行されます。MT1 は 2 回目の "ac" で失敗し、ロールバックして、MT ヘッドを 3 番目の位置 "a" に置きます。MT2は正しく終了し、入力はMT3に転送されます。"ac"!="abac" のため、MT3 は失敗します。したがって、MT は「abac」を認識しません。

問題を理解していますか？これに対する解決策を知っていますか？

私は Java を使用して開発していますが、言語は重要ではありません。アルゴリズムについて説明したいと思います。