問題タブ [turing-machines]

チューリング マシンや PDA について勉強しているときに、最初のコンピューティング デバイスはチューリング マシンだと思っていました。

そこで、チューリングマシンという実用的なマシンが存在し、その状態を特殊なデバイス (フリップフロップなど) で表すことができ、磁気テープを入力として受け入れることができると考えました。

したがって、入力文字列が磁気テープでどのように表現されるかを尋ねましたが、答えと私の本に記載されている詳細から、チューリングマシンはやや仮説的であることがわかりました。

私の質問は、チューリング マシンを実際にどのように実装するかということです。たとえば、現在のプロセッサでスペル ミスをチェックするためにどのように使用されているかなどです。

チューリングマシンは時代遅れですか？それともまだ使われていますか？

私は今、計算理論のコースを取っています。概念はよく理解できます。私は問題を解決することができます。そして、実際のアプリケーションについて講師に尋ねたところ、これらの概念はコンパイラーの設計において確実に有用であり、不可欠であるとのことでした。しかし、少なくとも有意義な調査を行うには、これらの概念をコーディングでどのように使用できるかについての説明が必要です。

たとえば、独自の grep を設計したい場合。C で文字列関数を使用します。コーディングで正規表現を使用する方法がわかりません。

同じケースがチューリングマシンにも当てはまります。

2 つの数値を追加したい場合、なぜそれらの単項概念に従う必要があるのですか。ハードウェアはそれらの概念を実装していますか?

w^R は w の逆で、w は {0, 1}* です。そのため、TM は単語の後にこの単語の逆の単語が続き、その単語が続く単語を決定する必要があります。私は答えが欲しいのではなく、リードが始まり、正しい軌道に乗ることを望んでいます.

私はこの答えに近いと思いますが、それでも確認するために、実数の計算に取り組み、正確な結果を得ることができるチューリングマシン（少なくとも原理的には）を作成できますか？**たとえば、整数の平方根を見つけます。（その出力は実数になります）そのようなマシンを開発できないという私の論理は、実数は数え切れないほど無限であり、数え切れないほど無限の言語ではチューリングマシンを作成できないということです。

非決定性チューリングマシンを使用して、言語が状況依存であることをどのように示すことができますか？

線形拘束オートマトン（LBA）で受け入れられる言語は、状況依存言語であることを私は知っています。また、LBAは非決定性チューリングマシンです。

これらすべてをどのように関連付けて、言語が状況依存であることを示すことができますか？

演習テストを実行して、CS 理論試験の準備をしています。この問題では、言語が属する「ゾーン」を (RL/DFSA/NFSA)/(CFG/CFL/NPDA)/(NP)/(EXPTIME)/(DL/DTM/NDTM)/( TR) そして、言語が (CFG/CFL/NPDA) ゾーンを超えることを証明する方法がわからないことに気付きました。ここに 2 つの問題 (3 と 5) がありますが、それらは文脈自由言語のポンピング レンマに失敗するため、そのゾーンに入ることはできません。

編集: 答えは、3 と 5 の両方が NP に分類されるということですが、なぜですか?

たとえば、私はその言語を知っています

CFLのポンピング補題によって文脈自由ではありませんが、expではなくNPに分類されることをどのように証明しますか。時間、決定可能な言語、または認識可能なチューリング？

編集：いくつか掘り下げました、そして私がした一つの見落としは、NPの問題は非決定性チューリングマシンによって多項式時間で検証可能な問題であるということです。どうすればわかりますか：a：多項式時間でこの言語に存在するベリファイアがあり、b：NDTMがそれを認識できます

これは、チューリング完全であるとはどういう意味かについての質問だと思います。awk はプログラミング言語で、なんでもできると聞きましたが、物理的な制約もありませんか？つまり、Minecraft のレッドストーン コンピューターではファイルを削除できない可能性があります。同様に、AWK でグラフィックスを行うことはできないと思います。

AWK でグラフィックスを実行できるようにするには、どのような拡張機能が必要ですか?

この質問が愚かな時間の無駄である場合は、反対票を投じてください (よくわかりません)。

ありがとう！

関数、たとえば f が入力のすべての値に対して停止するかどうかをチェックするプログラムを書きたいと思います。要するに -

たとえば、JavaScript では、

JS でのソリューションは必要ありません。どの言語でもかまいません。

ありがとう。

これが決定可能かどうかに苦しんでいます：

A = {x は自然数の集合の要素 | x より大きいすべての y に対して、2y は 2 つの素数の和です}

チューリング マシンに供給されると、受け入れ状態に達することはなく、拒否しない限り無限にループするという事実を考えると、これは決定可能であると考える傾向があります。ただし、言語が決定可能であるためには、それを決定するためのアルゴリズムのみが存在する必要があることも知っています。必ずしもそれがどのように行われるかを知る必要はありません。これで、私の一部は決定可能だと思いますか？どちらかを証明する方法を知っている人はいますか？