問題タブ [turing-machines]

チューリングマシンの全体像がよくわかりません。

私は現在、忙しいビーバーチューリングマシンの製造を任されています。しかし、私が実際に得ていないのは、入力をシミュレートすることです。では、どのような入力をシミュレートしますか？たとえば、3つの状態のビジービーバーマシンがテープに書き込む1の数を尋ねられますか？チューリングマシンを書く必要があると思いますが、それを手に入れたらどうしますか？

どの文字列でシミュレートする必要がありますか？

チューリング マシンの定義では、命令表 (プログラム) を読み取り/変更することは禁止されています。まさに、チューリング マシンはそれ自身のプログラムにアクセスできません。

この制限を弱めることができれば、どのような利点が得られるでしょうか? マシンがそのプログラムを分析および/または変更できる場合。それは、チューリング計算可能なタスクのクラスを拡張しますか?

これは私の割り当てのタスクの 1 つです。忙しいビーバー関数をシミュレートできるチューリングマシンシミュレーションがあります。この問題を証明するためにいくつかの調査を行いましたが、まだ理解できていないので、ここで私を助けてくれると思います. 私が行く良い情報源、またはこれが良いと主張する方法の例.

皆さん、今日の目標はチューリング マシン シミュレータを構築することです。それが何かわからない人は、ウィキペディアの記事を参照してください。現在使用している状態テーブルは、そのページの一部である Formal Definitionの最後にあります。

このコードは、一連の「0」と「1」の文字列文字、マシンが開始する文字を表す整数、およびプログラムの状態を表す整数 (順不同) を受け取り、次の最終結果を出力します。文字列の操作と最終的な位置。例:

例 1:

例 2:

その他:

• コードは、必要に応じて文字列を拡張して、テープの「空白」への書き込みを適切に処理する必要があります。
• 指定されたステート マシンは、いかなる種類の「ブランク テープ」アクションも指定しないため、すべてのブランク値を 0 として扱います。
• 初期状態の文字列の評価を処理するメソッドのみをカウントする必要があり、そのデータをどのように出力するかはあなた次第です。
• テープ上で右に移動すると上に増加し (文字列位置 0 は一番左)、状態 0 は A、状態 1 は B、状態 2 は C です。

（できれば）最終編集： この質問で混乱とトラブルを引き起こしたことについて、心からお詫び申し上げます。リストした提供された状態テーブルを読み違えて、逆に取得しました。時間を無駄にしてしまったことをお許しください。それは完全に意図的ではありませんでした！

実数を決定する NFA はありますか?

# で区切られた 2 進数の合計を計算するチューリング マシンを作成するにはどうすればよいですか。111#101B、B は空白を表す? 結果はテープの最後に書き込むことができます。

アルゴリズムの擬似コードがすでにある場合、チューリングマシンが何をするかを説明するのに役立つガイドラインはありますか？

私は複雑さの理論のコースを受講しており、Cやアセンブリのようなものでコーディングする方法を知っていても、いくつかの言語（状態、遷移など）を決定または受け入れるチューリングマシンについて説明するのに時間がかかります。チューリングマシン（それに取り組んでいる）を十分に練習していないと思いますが、何か提案があればありがたいです。

編集

チューリングマシンのシミュレーターを作りたくありません。いくつかの言語を決定するために、紙にチューリングマシン（アルファベット、状態、遷移）を記述したいと思います。

これは、私が意味する簡単な例です。たとえば、0と1の文字列を調べ、その中のすべての0を1に変更するチューリングマシンを作成する必要があるとします。たとえば、テープ（入力）で11010から開始すると、テープ（出力）で11111で停止します。これで、高級言語では、次のようなものであることがわかります。

チューリングマシンの説明は、非公式に次のようなものです。

qとhaltの2つの状態があります。状態qにあり、1が表示されたら、変更せずに右に移動します。0が表示されている場合は、1に変更して、右に移動します。空白の記号（テープの終わり）が表示された場合は、停止状態になります。

正式には、状態に対して{q、halt}のようなものがあります。{（（q、1）->（q、1、R））、（（q、0）->（q、1、R））、（（q、＃）->（halt、0、L） ）}トランジションの場合。

現在、この問題は些細なことですが、より複雑な問題もあります（1進数を追加するか、a、b、およびcの数が等しい言語を認識します）。それらの擬似コードを簡単に書くことはできましたが、チューリングマシンを書くことははるかに困難であり（時間がかかります）、そのような問題をよりよく解決するのに役立つヒント、リソース、またはガイドラインがあるかどうか疑問に思いました。

私がマシンを持っている場合、それをマシン1と呼びます。これは、問題を解決することができます。それは単なるマシンであり、それ自体はチューリングマシンではありません。それは1つの特定の問題を解決することができます。これとまったく同じ問題が万能チューリングマシンで解決できる場合、私の元のマシン1は万能チューリングマシンでもありますか？

これは、すでに解決されているすべての問題に当てはまるわけではありません。この記述された特性を持っている問題はありますか？それが絶対に真実ではない場合、なぜですか？

誰かが解決すべき問題の例を挙げてもらえますか？この問題が私の元のマシン1で解決された場合、間違いなくこれをユニバーサルターニングマシンにしますか？それともそのような問題は存在しませんか？それが存在しない場合、なぜですか？

とても興味がありますが、わかりません…ありがとうございます。

編集：質問をより明確にしました。

私はそれらが現実のものではないことを理解しており、1 つを選択する代わりに 2 つのオプションがある場合は常に計算を分岐しているようです。しかし、たとえば、私がこれを言うなら：

「グラフ G からグラフ H への頂点の全単射 p を非決定論的に推測する」(ここでのコンテキストはグラフ同形性です)

それはどういう意味ですか？私は全単射を理解していますが、「非決定論的推測」と言っています。推測である場合、それはどのようにアルゴリズムのアプローチですか? それが機能することをどのように保証できますか？

チューリングマシンで処理できる言語とLBAで処理できない言語がありますが、LBAでは解決できないがTMでは解決できる有用で実用的な問題はありますか？

LBAは、有限のテープを備えたチューリングマシンであり、実際のコンピューターには有限のストレージがあるため、LBAで実行できない実用的な重要性は何もないように思われます。 線形拘束オートマトンには有限のテープだけでなく、入力のサイズの線形関数であるサイズのテープがあるという事実を除いて。有限性の線形性はLBAを何らかの方法で制限しますか？

LBAが対処できない問題はありますが、指数関数的に制限されたオートマトンは（そのようなものが存在する場合）可能ですか？