計算モデルについて学ぶのに適したリソースはありますか?

Question

好奇心から、私が扱っているシステムがどのような計算モデルと機能的に同等であるかを特定し、同等であることを証明しようとしています。この問題に長く費やすほど、このシステムはチューリングと同等ではないと疑うようになります。チューリング マシンと再帰的に列挙可能な言語についてはよく理解していますが、機能が劣るオートマトン (例:プッシュダウンオートマトン）なので、どのように進めればよいかわかりません。

まず、さまざまな計算モデルについて学ぶための優れたリソースを誰かが推奨できますか?私は文法、言語、オートマトン、そしてそれらすべての等価性と差異を証明する方法に興味があります。理想的には、リソースは各モデルのすべての要素を詳細に分類し、それらを比較します。

第二に、システムをこれらの計算モデルに当てはめようとするときに使用すべき一般的なアプローチやフレームワークはありますか?

Answer 1

コンピューター サイエンスに関する優れた教科書をお勧めします (大学のコースでは、 シプサーの計算理論入門, 、私の意見では非常に良いです。また、 無料の教科書 これも同じことを教えてくれますが、私には経験がないので、お勧めできません）。

もう 1 つのアプローチは、おそらく Wikipedia を読むことでしょう。実際、何をどのような順序で探しているのかがわかっていれば、ウィキペディアの記事から多くのことを得ることができます。また、不明な点がある場合は、通常は Google で検索し、その特定の主題に関するその他のリソースを見つけることができます。

もちろん、これは ない 本物の教科書と同じくらい充実していますが、始めるには最適です。 今すぐ, 、しかも無料です。

出発点として、次のトピックについて読むことをお勧めします (リスト順)。

1. 決定論的有限オートマトン
2. 非決定性有限オートマトン, 、および DFA との同等性。
3. 通常の言語, 、および DFA との同等性。
4. プッシュダウン オートマトン
5. 文脈自由文法, 、およびプッシュダウン オートマトンと同等です。
6. チョムスキー階層
7. チューリングマシン

これは、人々が話題にするほとんどの計算モデルについての非常に簡単な紹介を提供するはずです。 2:コンピューター サイエンスに関する優れた教科書をお勧めします (大学のコースでは、 シプサーの計算理論入門, 私の意見では、これは非常に良いことだと思います）。もう 1 つのアプローチは、おそらく Wikipedia を読むことでしょう。実際、何をどのような順序で探しているのかがわかっていれば、ウィキペディアの記事から多くのことを得ることができます。また、不明な点がある場合は、通常は Google で検索し、その特定の主題に関するその他のリソースを見つけることができます。まずは次のトピックを読むことをお勧めします (リスト順)。1. 1: http://www.amazon.com/ Introduction- Theory-Computation-Second-Michael/dp/0534950973/ref=sr_1_1?ie=UTF8&s=books&qid=1263282346&sr=8-1

Answer 2

以下のリンクからビデオ講義は、計算の理論の入門を提供します。これは、このトピックに関する最も優れたリソースの一つです。

ビデオ講座教授シャイSimonsonするによって計算理論上

Answer 3

見つけるのが難しいかもしれない古いテキストは、ホップクロフトとウルマンの「オートマトン理論、言語、および計算の紹介」です。いくつかのエディションがありますが、複雑なものを導入する際のパンチが最も少ないという点で、79 年が最高だと聞いています。これは、小さいながらも正当な教科書であり、探しているものだけでなく、その分野全体を紹介しています。私がこれを提案するのは、他の情報源が除外している「トリッキーな」証拠の 1 つがあなたの鍵になるかもしれないという無駄な期待に基づいています。

より穏やかな出発点として、便利な「ベンチマーク」言語がいくつかあります。

• あなたのモデルの場合 できる 文字列内に同じ数の As と B が含まれるすべての文字列の言語を認識する場合、少なくとも FSM より強力です。
• それができないなら、それは 5月 FSMと同等であること。
• 同様に、あなたのモデルの場合、 できる 文字列内の As、B、C の数が同じであるすべての文字列の言語を認識すると、 もっと CFG や PDA より強力です。

これらの「ベンチマーク言語」は実際には機能を偽ったものにすぎません。1 つ目は基本的に 2 つの単項数が等しいかどうかを尋ね、2 つ目は 3 つの単項数が等しいかどうかを尋ねます。これらは素晴らしくシンプルで、特定のモデルの機能を上回るか下回ることがよく知られています。より複雑なマシンに対応する単純なものはわかりません。そのため、あなたは自分で判断する必要があるかもしれません。

線形境界オートマトンであるモデル「LBA」については、LBA ではなく TM で計算できる既知の自然言語は存在しないと私は考えていることに注意してください。この発言は曖昧な記憶に基づいて書かれているため、正式な証拠として受け取らないでください。:)

(最後に) 「ベンチマーク」言語は平等を確立していないことに注意してください。つまり、モデルが 2 つの単項数を比較できない場合は、 ない これは必然的に FSM と同等であることを意味しますが、さらに弱い可能性があります。言語は、それが権力よりも大きいか、または権力より小さいかを確立するだけです。

まったく（完全に）別の軌道で、シプサーの本は確かに次のことを証明しています。 等価 正規表現と FSM の間、および PDA と CFG の間。どのような種類の計算モデルを検討しているのかが非常に曖昧であるため、これがどれほど役立つかはわかりませんが、等価性について完全に決まっている場合は、これらが良い出発点になるかもしれません。