問題タブ [turing-machines]

私は形式言語理論で私のコースのためにチューリングマシンを研究しています、教授は「TM」の背後にあるロジックを詳細に確認するために次のアルゴリズムで実行することを推奨しましたが、コンパイルしようとすると機能しません次のエラー。

コードは次のとおりです。

このプログラムが機能しないのはなぜですか？

2 テープ チューリング マシンを使用して w#w を決定する必要があります。最後の部分、つまり # の後の部分を 2 番目のテープにコピーし、文字ごとに比較して、これら 2 つの部分が同じかどうかを確認する必要があることはわかっています。

私の問題は、# の後の部分を 2 番目のテープにコピーする方法です。

何か案は ？

w = (a|b)^*

これはウィキペディアの決定可能性の定義です

計算可能性理論では、決定不可能な問題は、特定のはい/いいえの答えが必要なインスタンスのファミリで構成されているため、入力として問題のインスタンスが与えられた場合、有限数の後に必要な答えを終了して出力するコンピュータープログラムはありませんステップの。より正式には、決定不能な問題とは、言語が再帰集合でない問題です。

再帰セットは、再帰的に列挙可能なセットのサブセットです。再帰セットの外にある、再帰的に列挙可能な言語がいくつかあります。では、再帰的に列挙可能な言語が決定不能ではないのはなぜでしょうか?

多くのものの削減は、対称的ではありません。私はそれを証明しようとしていますが、うまくいきません。

2つの言語AとBが与えられた場合、Aは次のように定義されます。

そしてB=A_TM、A_TMは決定不可能ですが、チューリング認識可能です！

次の削減が与えられた場合：

（ラテックスを使用していないことをお許しください。私はラテックスを使用した経験がありません）

ご覧のとおり、A <= B（AからA_TM）への削減が可能であり、うまく機能します。しかし、なぜB<=Aが不可能なのかわかりません。

明確にして説明してもらえますか？

ありがとうロン

ラムダ計算がチューリング完全であるという事実をどのように主張しますか（可能な限り最も簡単な方法で）？

チューリングマシン M1、M2、M3 が存在し、それらが認識する言語はそれぞれ L(M1)、L(M2)、L(M3) であるとします。次の言語 L = {(M1, M2, M3) : L(M1), L(M2), L(M3) は等しくない} 言語は決定可能ですか? 再帰的に列挙可能？それともどちらでもない？

こんにちは私は可算性に疑問があります。特定のものが可算であるかどうかを調べる必要があるのはなぜですか。それを見つけることに使用はありますか？また、数えられないことがある場合、それを解決するチューリングマシンがないことを意味しますか？

ハイパーグラフを使用して非決定論的チューリング マシンを実装または表現することについて説明している論文、テキスト、またはその他のドキュメントを知っている人はいますか? それらは実際に同等ですか？

たとえば、ハイパーグラフは、非決定論的なチューリング マシンの状態遷移を適切かつ完全に表現できると確信しています。しかし、私はこれまでのところ、これを確認できる印刷物を見つけることができませんでした. これは明らかな関係のように思えますが、先行技術を見つけられないという事実は、私が間違った方向に進んでいると考えさせます. (私が見つけたものが、それが何を言っているのかを理解するのに十分にアクセスできない場合もあります。) ;-)

質問する理由: 私は、ピア ツー ピア ネットワークで分散データ ストレージと分散計算を行うオープン ソース パッケージに取り組んでいます。必要な機能をサポートする最も原始的なデータ構造を探しています。これまでのところ、分散型ハイパーグラフは有望に見えます。私の推論は、ハイパーグラフが非決定論的チューリング マシンと同じくらい一般的なものをサポートできる場合、より高いレベルのチューリング完全な DSL をサポートできるはずだということです。（「非決定論的」な部分が私にとっても価値があるかもしれない他の理由があり、分散データおよび/または計算結果のバージョン管理に関係しています。ただし、ここでは論文を避けようとしています。）

部分的な回答:

• opencog 関係者は、ハイパーグラフがさまざまなコンピューティング モデルにどのように適合するかについて、興味をそそる議論をしました。これはどうやら HypergraphDB パッケージの開発に関連していたようです: http://markmail.org/message/5oiv3qmoexvo4v5j
• MathOverflow では、ハイパーグラフでできることについて議論する質問があります。チューリングについてはまだ言及されていませんが、追加しようとしています: https://mathoverflow.net/questions/13750/what-are-the-applications-of -ハイパーグラフ
• ハイパーグラフが非決定論的チューリング マシンを表すことができる場合、エッジに重み付けされたハイパーグラフは確率論的チューリング マシンと同等になると思います。 http://en.wikipedia.org/wiki/Probabilistic_Turing_machine

私はこれら2つの違いを理解するのに本当に苦労しています。私の教科書から、それは本質的に次のように違いを説明しています

言語がチューリング認識可能な言語の補数である場合、その言語は共チューリング認識可能です。

私が理解していないこの定義の部分は、チューリング認識可能な言語の補完である場合、それはどういう意味ですか?

それが別の言語の補数であるかどうかをどのように正確に判断しますか?

を受け入れる非決定性チューリングマシンのプログラムを説明するように求められる宿題の問題がありますL = {a^n: n is prime}。どうすればいいのかわかりません。私はnを知っていますか？sを単項桁として使用してaカウントしますか？文字列を無視して、主にnをテストすることはできますか？またはプライム値がわかっているので、それらのセルの場所だけが状態を受け入れており、通常のようにデータを読み取ることができますか？

どうすればいいですか？