問題タブ [turing-machines]

同じ単語セットを出力する 2 つの異なる文法を教えてください。

図：

アルファベット {0,1} に対する文法 A と B が与えられた場合、文法 A が単語 0101001 を生成できる場合、文法 B も同様に生成できます。文法 B が 0101111 を生成できる場合、文法 A も同様に生成できます。そして、文法 A が 01001 を生成できない場合、B も生成できません。

しかし、ここで重要なのは、文法 A と B が互いに異なるということです。つまり、まったく異なるアルゴリズムを使用しています。次に、それらが生成する出力のセットは、他の出力の適切なサブセットではありません。つまり、対応する出力セットは同じカーディナリティを持つ必要があります。おそらくそれらは複雑度のクラスが異なりますが、それは問題ではありません。よろしければ、古典的なチューリング マシンのように、アルファベット {0,1} に関する文法を教えていただければ幸いです。

初心者のために説明すると、Brainfuckは 8 つのコマンドしかないチューリング完全言語であり、そのすべてが C で文字どおり同等のものを持っています。

パッケージマネージャーを備えたLinuxディストリビューションでは、Brainfuckインタープリターであるパッケージを見つけてインストールできるはずbeefなので、自宅で遊ぶことができます.

上記のように、Brainfuck には1 つの制御構造しかなく[…]、C に次のように変換されます。

IF VAR = 0 THEN GOTO 10これにより、BASIC からのすべての制御が可能になります。getchar()以下は、返されるまで呼び出します0:

しかし、改行文字だけを読みたい場合はどうすればよい\nでしょうか? これを単純に機能させる方法について頭を悩ますのに苦労ifした後、次のことを思いつきました。

(他に良い方法があれば教えてください)

\rに加えて、そのループから抜け出すことをテストしたいとしましょう\n。ループから抜け出す機会が 1 回しかない場合、どうすればどちらかをテストできますか? switch私の目標は、ネストされたifs またはsをエミュレートできるようにすることif/else ifです。

元のチューリングマシンの定義を次のように使用する場合：

...正方形にマークされた無限のテープの形で得られる無限のメモリ容量。それぞれに記号を印刷できます。いつでもマシンには1つのシンボルがあります。これはスキャンされたシンボルと呼ばれます。マシンはスキャンされたシンボルを変更でき、その動作はそのシンボルによって部分的に決定されますが、他の場所のテープ上のシンボルはマシンの動作に影響を与えません。ただし、テープはマシン内を前後に移動できます。これは、マシンの基本的な操作の1つです。したがって、テープ上のシンボルには、最終的にイニングが含まれる可能性があります。（1948年のTuring、p.61）

これらの操作を、アセンブラ/バイナリ命令を解釈できるプロセッサで実行される操作にマップする場合、どの操作がマップされますか？

（私は、この質問に固有のチューリングマシンからフォンノイマンマシンへのジャンプを知っています）

チューリングマシンとチューリング完全言語とは何かについて少し知っていますが、よりよく理解するために、誰かがチューリング完全ではない言語の例を挙げてもらえますか？（たぶん、チューリングではないマシンでも？）

したがって、言語が何らかの基準を満たしていれば、その言語はチューリング完全であると言うことができ、別のチューリング完全言語が実行できることは何でも実行できます。

理論的には、JavaScript またはBrainf_ckを使用して Google を実装できるということですか?

最近、私はNP問題、計算の複雑さ、理論について研究しています。ついにチューリングマシンの概念を理解できたと思いますが、疑問がいくつかあります。

非決定性チューリングマシンには、読み取られている特定の状態と記号に対して何をするかについていくつかのオプションがあり、ウィキペディアで述べられているように、常に最良のオプションを選択することを受け入れることができます

NTMは、これらのアクションのどれを実行する必要があるかをどのように「認識」しますか？それを見るには2つの方法があります。1つは、このマシンが「最も幸運な推測者」であると言うことです。そのような遷移がある場合、それは常に最終的に受け入れ状態につながる遷移を選択します。もう1つは、マシンが多くのコピーに「分岐」し、それぞれが可能な遷移の1つに従うことを想像することです。DTMにはそれがたどる単一の「計算パス」がありますが、NTMには「計算ツリー」があります。ツリーのいずれかのブランチが「受け入れ」条件で停止した場合、NTMは入力を受け入れたと言います。

私が理解できないのは、これは架空の機械なので、多項式時間でNP問題を解くことができると言うことから何が得られるのでしょうか。つまり、O（1）のNP問題を解決する魔法の機械を理論化することもできますが、それが存在しない可能性がある場合、それから何を得ることができますか？

前もって感謝します。

私は最も単純なチューリング マシンを理解し、実装しようとしています。

無限のテープ (先頭が 0 のポインターを持つ T という名前の配列としましょう) と命令テーブルがあります。

私の理解では、3 ステート 2 シンボルが最も単純なマシンです。3 状態 わかりません。READ/WRITE に 0 と 1 を使用するため、2 シンボル。

例えば：

ステップ 1 から始めて、Read が 0 の場合 { Write 1, Move Right) else {Write 0, Move Right) そしてステップ 2 に進みます - これは存在せず、プログラムを停止します。

3状態 とはどういう意味ですか? このマシンはチューリングマシンとして通用しますか? もっと単純化できますか？

なぜ、数piの有限接頭辞の言語がTMによって決定可能であるのに対し、その与えられた数の有限接頭辞を決定する実数のTMがあると言うのは誤りですか？

私は工学部の最終学年の学生です。私と私の友人は、最終年度のプロジェクトを「テンプレートメタプログラミングを使用したチューリングマシンのシミュレーション」にすることを決定しました。

「チューリングマシン」と「テンプレートメタプログラミング」とは何かは理解していますが、TMPを使用せずにチューリングマシンを設計すると、なぜシミュレーションが面倒になるのでしょうか。TMPを使用した場合、どのような利点が得られますか。また、TMPを使用せずに従来のアプローチを使用した場合、どのようなメリットが得られますか。

どのように進めるかについての提案はありますか？

私は関連する決定可能性/認識可能な問題に取り組んでおり、それを解決するには、チューリングマシンのエンコード/表現について明確にする必要があります。

チューリングマシンは正式には7タプルとして定義されていることを私は知っています。Uチューリングマシンと別のチューリングマシンを持っている場合、その一部（アルファベット、入力記号、受け入れ状態のセットなど） を認識Mするように設計するのは簡単ですか？UMM

M私の一部は、これらは有限集合であるため、それらを数えるのは簡単だと思いますが、無限にループする可能性なしに、定義の一部を列挙できるかどうか疑問に思います。