状態と時間の移行ロジックとプログラムフロー？

StackOverflow https://stackoverflow.com/questions/163492

  •  03-07-2019
  •  | 
  •  

質問

いくつかの参照キーを使用して、アプリケーションのすべての可能な状態のインデックスを作成することが有用かどうか疑問に思います...

つまり、開始するプログラムがあり、可能な結果が非常に多い、たとえば8ということです。

ただし、各結果がより多くのロジック状態をステップスルーすることによって達成され、各ブランチ間が状態と見なされ、キーにマッピングされる場合。

大規模なプログラムでは大量のメモリを必要とする可能性がありますが、キーに直接アクセスできる場合（キーは時間またはロジックの深さに基づいている可能性があります）プロセス全体を新しいデータで繰り返します。

子のないノードが最終結果であり、ノードとその親または子の間のすべての分岐が「状態」であり、それぞれが異なるキーを持つツリーのように考えてください。そのため、プロセスの最終結果であるリーフは8つしかありませんが、子がなくなる前にロジックがツリーを下る深さに応じて、多くの「状態」が存在する可能性があります。

シミュレーション用かもしれませんが、大量のメモリが必要になります。

役に立ちましたか？

解決

ライアン、答えは間違いなくYESです。

最初の答えに反して、停止する問題は何も証明しません。実際、ライアン、あなたが提案していることは、 wrong という停止の問題が実際のデジタルコンピューターには当てはまらないことを証明しているので、私はこの例をまさにその証拠として使用しました。

決定論的なデジタルシステム（つまり、実際のデジタルハードウェアで実行されるプログラム）では、可能な状態の数は有限であるため、可能な状態はすべて列挙可能です。

ハッシュに必要なメモリの正確な量は次のとおりです。

（2）*（プログラム状態サイズ）*（初期状態の数）

初期状態はハッシュキーになり、最終状態はハッシュ値になり、初期状態ごとにキー/値のペアができます。

オペレーティングシステムの場合、「プログラム状態サイズ」 2 ^（すべてのシステムデバイスの合計ギガビットメモリ）。明らかに、このような大規模な汎用プログラムはハッシュするのに非実用的な量のメモリを必要とし、システムは自己参照/還元不可能に複雑であるため（つまり、次のユーザー入力は以前のシステム出力に依存します） p>

説明：

これは非常に便利です。すべての可能な初期状態にインデックスを付けて終了状態に関連付けると、任意のプログラムの実行時間が実質的にゼロになるためです！ゼロとは、非常に高速なO（1）実行時間-終了状態の検索にかかる時間（終了する場合）を意味します。

すべての可能な状態から開始してプログラムを実行すると、サイクルを示す一種の状態マップが提供されます。 初期状態が考えられる場合、可能性は3つ（実際には4つから3つに崩壊）しかないため、停止の問題は解決されます。

  1. プログラムは、可能なすべての状態を使い果たす前に、以前に遭遇した状態（初期状態以降）に再び入るため、論理的に永久にループします。
  2. プログラムは、「終了」として識別される状態に達します。以前に遭遇した状態に再入するか、すべての可能な状態を使い果たす前に（初期状態以降）。

  3. または4.最も単純なプログラムは初期状態から開始し、可能なすべての状態を一度だけ入力してから、（3）停止するか（4）以前に遭遇した状態に戻って永遠にループする以外の選択肢はありません。

    for（int i = 0; true; i ++）; // iは最大値に到達し、ゼロにロールオーバーします。この時点で初期状態に戻ります

したがって、基本的に、インデックスは次のように記述できます。

  • 初期状態ごとに、終了状態が1つまたは0個あります。

つまり、初期状態ごとに、プログラムは終了状態に達するか、 初期状態から既に遭遇した状態に再び入り、無限に循環します。

したがって、決定論的なデジタルハードウェアで実行されているプログラムの場合、そのすべての状態を決定することは絶対に可能です（ただし、多くの場合実用的ではない）停止するか永久にループするか。

  • 実用性は、有効な初期状態の数（入力制約で劇的にを減らすことができる）と、それらのそれぞれに対してプログラムを実行するのにどれだけ時間がかかるかによってのみ決まります終了し、結果の状態をハッシュテーブルに保存します。

プログラムの実行時間をO（1）操作に強制する以外に、状態をキャプチャする他の用途には、ゲームコンソールエミュレーターの状態保存機能とコンピューターの休止状態機能があります（ただし、一部のシステムメモリは、状態の完全な復元ではありませんが、状態を復元するコードに使用する必要があり、一部のメモリは保存されない可能性があります（GPUメモリなど）。

これが証明するのは

他のヒント

これは、一般的なプログラムでは解決できません。停止の問題は、プログラムが停止するかどうかを判断できないことを証明しています。特定の状態が可能かどうかを判断する問題は、停止する問題に還元可能であるため、解決することもできません。

このアプローチは、何に対しても完全に扱いにくいと思います。

検索の問題として、それは大きすぎます。各状態が10の結果につながる可能性があると仮定した場合（この数値は非常に低いと思いますが）、20歩先を見るには、2,000億の可能性を追跡する必要があります。

そして、ループ内のすべてのステップが分岐点としてカウントされることを忘れないでください。したがって、次のようなコードがある場合：

for (int i=0; i < 100; i++)
    some_function();

その後、可能な状態の数は（some_function内のブランチの数）^ 100

Joshは、この問題の曖昧さのために、この問題の最もリベラルなバージョンに答えることができないことは正しいですが、シナリオにいくつかの制限を設ければ、答えることができます。プログラムの状態とビジネスエンティティの状態には大きな違いがあります。

たとえば、DFA（State Machine）によって定義されたワークフロー指向のアプリケーションがあるとします。実際に、DFAの特定のポイントを何らかのIDに関連付けることができます。

はい、それは扱いやすいですが、制限なしではありません。

これは機能レベルで行われます。 メモ化と呼ばれる手法です。

kripke構造とモーダルロジックの研究。これは、モデリングプログラムで採用されているアプローチです。このアプローチを使用する古典的なシステムが何であるかを忘れています。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top