問題タブ [turing-machines]

「チューリング完全」という表現はどういう意味ですか?

あまり理論的な詳細には立ち入らずに、簡単に説明していただけますか?

クラスでは、停止問題、チューリング マシン、縮約などについて学びました。多くのクラスメートは、これらはすべて抽象的で役に立たない概念であり、それらを知っていても意味がないと言っています (つまり、コースが終わったら忘れることができます)。何も失うことはありません）。

理論はなぜ役に立つのか? 日常のコーディングで使用したことがありますか?

現場で停止の問題に個人的に遭遇したのはいつですか? これは、同僚や上司が計算の根本的な限界に違反する解決策を提案したとき、または解決しようとしていた問題が実際には解決できないことに気付いたときです。

私が最近それを思いついたのは、型チェッカーを研究していたときでした。私たちのクラスは、完全な型チェッカー (型エラーなしで実行されるすべてのプログラムを受け入れ、型エラーで実行されるすべてのプログラムを拒否するもの) を書くことは不可能であることに気付きました。 . もう1つは、同じクラスで、型チェック段階でゼロによる除算が発生するかどうかを判断することは不可能であることに気付いたときです。実行時に数値がゼロであるかどうかをチェックすることも停止問題のバージョン。

チューリングマシンとは何ですか?なぜ人々はそれについて言及し続けるのですか? IBM PC だけで計算を行うことができます。なぜ誰もがこれらのマシンを気にするのですか?

私は最近、人工生命について読んでいて、 「コンウェイのライフ ゲームは、普遍的な機械として分類されるのに十分な複雑さを示している」という記述に出くわしました。私はユニバーサル マシンとは何かについて大まかにしか理解していませんでした。ウィキペディアは、ウィキペディアがかつてないほど理解に近づいただけでした。誰かがこの非常にセクシーな声明に光を当てることができるのだろうか?

コンウェイのライフ ゲームは、私には、いくつかの途方もない含意を伴う素敵な気晴らしのように思えます。それは私がすべき飛躍ですか？

JFLAPには、チューリング マシン遷移のショートカットがいくつかあります。これらのショートカットの 1 つを使用すると、現在のテープ シンボルが指定されたシンボルでない限り、移行できます。たとえば、トランジション !g,x;R は基本的に、「現在のテープ記号が g でない場合にこのトランジションを実行する」ことを示しています。

ここまでは順調ですね。しかし、私が望むトランジションは !□,~;R であり、これは基本的に「現在のシンボルが文字列の終わり (空のセル) シンボルでない限り右に移動する」というものです。問題は、「!□」の入力方法がわからないことです。

JFLAP オンライン ドキュメントには、次のように書かれています。

最初のショートカットは、「!」を使用するオプションが存在することです。「この文字以外の任意の文字」の意味を伝える文字。たとえば、トランジション (!a; x, R) に関して、ヘッドが「a」以外の文字に遭遇すると、その文字を「x」に置き換えて右に移動します。「!□」という表現は、コマンド入力時に「1」を入力するだけです。

最後の文が私に説明しようとしていることを実際にどのように行うのですか?

私は現在、チョムスキーのヒエラルキーと、ヒエラルキーの各レベルを認識するオートマトンのタイプを学習する離散数学テストの勉強をしています。ほとんどのコンピューター言語は階層の「レベル 2 と 1」に分類されると教えられていますが、正確にはそうではありません。

私の質問は次のとおりです。

1. 各レベルに属する機能は?

2. これは理論的根拠にすぎませんか？Dennis Ritchie や James Gosling のような言語設計者は、C や Java を設計する際にこの点を考慮する必要があったのではないかと思います。彼らは？誰かがこれをどのように適用しますか?

3. チューリング マシンは階層のレベル 0 を認識していると言われています。もしそうなら、レベル0に属する言語機能はありますか? これはもしかしたら自然言語処理なのかもしれませんね。

一部のプログラマーは、理論的なCSクラス（特に私の学生）との関連性をあまり認識していません。これが私が非常に関連性があると思うものです。今まで見たことがない人のために、バラバラに作り上げていきましょう...

A）プログラミングの問題は、言語に関する質問に言い換えることができます。

B）チューリングマシンは言語を認識します。

C）チューリングマシンは（大きな）整数としてエンコードできます。

D）したがって、可能なチューリングマシンの数は数え切れないほど無限です

E）セットのべき集合は、そのセットのすべての可能なサブセットです。

F）集合が可算無限である場合、そのべき集合はより大きくなります。つまり、可算無限です。

G）したがって、言語が無限である場合、その言語には数え切れないほどの数のサブセットがあります。これらのそれぞれが問題を表しています。しかし、これらの問題を解決するためのチューリングマシンは数え切れないほどあります。そして、チューリングマシンの問題を解決できなければ、解決することはできません。

結論...私たちはすべての問題のごくわずかな部分しか解決できません。

私の質問はほとんどここにあります...

私がこの議論を学生に提示するときはいつでも、彼らは数え切れないほど無限に数え切れないほど行き詰まります。彼らは一般的に強い数学の背景を持っていないので、カントールの対角化の議論を介して説明しようとすると、彼らの目を釉薬にする傾向があります。

通常、私は彼らが把握できる何かを与えるようにしています...カウント数直線の任意の部分に有限のボックスを配置し、それらの数の有限量をキャプチャします...しかし、の任意の部分に有限のボックスを配置します実数直線であり、無限の実数をキャプチャします。数えている数よりも実数が多いという一種の証拠。

最後に私の質問...無限の複数のレベルの概念を、その概念を聞いたことがなく、数学的に傾いていない可能性がある人々にどのように説明しますか？

最終編集：この質問をすることで多くのことを学び、フィードバックに感謝します。「コミュニティウィキ」が実際に何であるかを理解しようとして、私はあまりにも多くの時間を無駄にしました。今日私たちがしていることの多くは昨日の理論だったので、私が感じる理論の質問に対して、一部の人々には固有のバイアスがあることを学びました。しかし、この偏見は当然のことであり、理論の価値については意見が分かれていますが、問題はなく、生徒がどこから来ているのかを理解するのに役立ちます。BSコメントは不要だったと思います。

この質問は、世論調査や2009年の予測に関する質問ではなかったと思います。コーディングの質問とコーディングの答えだけが必要な場合は、その要件を再検討することをお勧めします。私はこの質問をコミュニティウィキに移動しましたが、力の不適切な使用によってそうせざるを得なかったと強く感じています。

チューリングマシンのテストを勉強していますが、次の関数計算機として機能するチューリングマシンを作成する必要があるという問題に悩まされています。

テープ入力が次のように分離されることを理解しています。

私のテープ出力は

XとYをテープに配置するにはどうすればよいですか？（マルチテープマシンの場合もあります）状態図はどのようになりますか？

注：私は単項を使用しており、1は0を表すために使用され、0は値としてではなく区切り文字として使用されます。

それで：

私は jflap に大きく基づいたコースでオートマトンのテストのために勉強しています。問題は、ドキュメントがあまりないことと、jlap で見つけた this や this のようなサンプル オートマトンでは、次のテストに備えるには不十分です。

詳細はどこで確認できますか? サンプルのチューリング マシンが遷移付きのグラフとして示されている他のリソースも役立ちます。