問題タブ [computation-theory]

FSA グラフで表現したい pac-mac に似たゲームを考えてみましょう。迷路 (テーブル) があり、ランダムな位置にベリーがあります。目標は、迷路内のすべてのベリーを食べることです。コントロールのために考慮しなければならないコマンドは、
GOAHEAD、LEFT、RIGHT、CHECKBERRY (パックマンの FRONT にベリーがあるかどうかをチェックする)、EAT、OFF-MAZE です。
最大 10 ステージが必要です...そして、連続して複数のギャップを設けることはできないことに注意してください。ありがとうございました

編集: 代替テキスト http://img338.imageshack.us/img338/2479/graphp.jpg

わかりました。グラフを作成しましたが、ギャップを越える方法が見つかりません。例: あるベリーの列の後の迷路で突然前にギャップがあり、次のベリーはそのギャップのすぐ下にあります. したがって、左または右に曲がっても、checkberryコマンドがTRUE値を返さないため、グラフがどのように見えるかわかりません。では、パックマンが食事をせずにギャップスクエアに移動する方法が必要ですが、前のものに移動するか、他の人に移動するかをどのように決定しますか?

動機: 関数の代わりに自然数を使用することで、一次関数のない言語でおもちゃの関数型プログラミングを使用できるようにしたいと考えています。

ユニバーサル関数は関数 f : N -> (N -> N) であり、同等に f : N * N -> N であり、可能なすべての計算可能な関数を列挙します。つまり、f(k) が 2 乗関数であるような数 k があり、f(j) が n 番目の素数関数であるような数 j があるということです。

このような関数を作成するには、任意のチューリング完全言語 (プログラミング言語コンパイラ、ラムダ計算、チューリング マシンなど) を使用して、すべてのプログラムを列挙します。評価だけでなく、足し算、合成、カリー化などの関数の操作もできるようにしたいです。たとえば、2 つの関数 f,g のインデックスが与えられた場合、関数 f+g、または g で合成された f のインデックスは何かを知りたいです。これにより、「おもちゃの関数型プログラミング」が可能になります。

そのようなコード ライブラリを作成する良い方法は何ですか? 私は、10 の階乗を計算するのに苦労する最小限のチューリング ターピットを探しているわけでも、高度なコンパイラを書きたいわけでもありません。追加やループを書く可能性など、いくつかの基本的な機能が必要ですが、それ以上ではありません。

すべての高級言語でのソリューションを歓迎します。疑似コード、Haskell、および Python が推奨されます。任意精度の演算を想定できます。使用evalまたは類似のものは許可されていません。

明確化: 列挙型関数は、すべての部分再帰 (計算可能な)関数で構成されます。これには、一部の入力で停止しない関数が含まれます。その場合、ユニバーサル関数はハングします。もちろんこれは避けられません。参照: m-再帰関数 - http://en.wikipedia.org/wiki/Μ-recursive_function。

まず、これは NFA を DFA に変換するアルゴリズムを求める質問ではありません。

ほとんどの場合、NFA とほぼ同じ数の状態を持つことになりますが、NFA と同等の DFA には最大で 2 ^{n 個の状態があることが知られています (そして証明されています)。}

NFA と同等の DFA が持つ状態数の推定値を予測するにはどうすればよいですか? ^{2 n 個}の状態を持つ同等の DFA を必要とする NFA の特定のタイプはどれですか?

これを尋ねる私の理由は、最小化を考慮せずに、2 ⁿ - 1 状態と「死んだ状態」を確実に生成するいくつかの NFA を「発明」できるようにするためです。

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

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

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

結果が引数の値のみに依存する場合に関数呼び出しを最適化できるおもちゃのコンパイラーを書いています。したがって、xorやconcatenateのような関数はそれらの入力のみに依存し、同じ入力でそれらを呼び出すと常に同じ出力が得られます。ただし、timeやrandなどの関数は「非表示」のプログラム状態に依存し、同じ入力でそれらを呼び出すと異なる出力が得られる場合があります。「同型」や「リエントラント」など、これら2つのタイプの機能を区別する形容詞が何であるかを理解しようとしています。誰かが私が探している言葉を教えてもらえますか？

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

私は複雑さの理論のコースを受講しており、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の数が等しい言語を認識します）。それらの擬似コードを簡単に書くことはできましたが、チューリングマシンを書くことははるかに困難であり（時間がかかります）、そのような問題をよりよく解決するのに役立つヒント、リソース、またはガイドラインがあるかどうか疑問に思いました。

大学で勉強している間、私は計算理論について多くを学ばなければなりませんでした。私はそのテーマを 3 学期勉強しました。苦労しましたし、忘れ物が多かったことを認めざるを得ません。

これは個人的な問題なのか、それとも（多かれ少なかれ）役に立たないことをたくさん学ばなければならなかっただけなのか、疑問に思っています。

私の質問は次のとおりです。計算理論の分野でどのトピックが最も重要だと思いますか。どの部分について学ぶ価値がありますか。通常の仕事ではどのトピックを使用しますか?

個人的には、言語の理論(特に正規言語 => 正規表現 - 適用できる場合と適用できない場合) と、さまざまな時間 (および空間) の複雑さ、特に O(n)について聞いてよかったです。表記。

しかし、次のことを含め、さらに多くのことを研究する必要がありました。

• 計算可能性理論
  • 停止問題
  • 半決定問題
• 複雑さの理論
  • p=np?
• 論理の理論
  • 命題計算
  • 述語ロジック

これらのトピックについて聞くのは興味深いことでしたが、それらを深く研究することがどれほど必要かはわかりません。

この質問は主観的なものであり、日々の仕事や個人的な経験によって答えが大きく異なることは承知しています. しかし、私が覚えているよりも興味深いトピックについて知りたい.

試験の復習をしているときに、Sipser 著「An Introduction to the Theory of Computation」という本からの次の質問に答えるのに苦労しています。残念ながら、本書にはこの問題の解決策はありません。

以下が正当なチューリング マシンではない理由を説明してください。

M = {

入力は、変数 x1、...、xn 上の多項式 p です。

1. x1、...、xn のすべての可能な設定を整数値にしてみてください
2. これらすべての設定で p を評価します
3. これらの設定のいずれかが 0 と評価された場合は受け入れます。それ以外の場合は拒否します。}

これは私を夢中にさせています！整数のセットが無限だからだと思いますか? これはどういうわけかアルファベットの許容サイズを超えていますか?

シプサの計算理論の本では、以下が与えられています：

小数部分および/または符号を含む可能性のある数値定数は、言語のメンバーとして記述される場合があります

（+ U-U e）（D + U D+。D*UD*。D+）

ここで、D = {0,1,2,3,4,5,6,7,8、9}は10進数のアルファベットです。生成される文字列の例は、72、3.14159、+ 7。、および-.01です。

ここで、D+またはD*の結合をとる目的が何であるか理解できませんか？さらに、なぜ3番目のドットが追加されるのですか？

誰かが私の疑問を解消してください。

交差法を使用して 2 つの dfa を結合するにはどうすればよいですか?