Logique transitoire d'état et de temps et déroulement du programme?

Question

Vous vous demandez s'il serait utile d'indexer chaque état possible d'une application à l'aide de clés de référence ...

Ce qui signifie, disons que nous avons un programme qui commence, n’a que très peu de résultats possibles, disons 8.

mais si chaque résultat est atteint en passant par beaucoup plus d'états logiques, et entre chaque branche est considéré comme un état et est mappé à une clé.

Cela peut prendre beaucoup de mémoire dans les programmes volumineux, mais si nous pouvions accéder directement à une clé (la clé pourrait être basée sur le temps ou la profondeur de la logique), nous pourrions alors parcourir instantanément toutes les situations possibles sans avoir à commencer. tout le processus à nouveau avec de nouvelles données.

Pensez-y comme à un arbre où les nœuds sans enfant sont les résultats finaux, et chaque branche entre un nœud et ses parents ou ses enfants est un "état", chacun indexé différemment. Ainsi, bien qu’il n’y ait que 8 feuilles ou résultats finaux du processus, il pourrait y avoir plusieurs "états" en fonction de la profondeur de la logique dans l’arbre avant de manquer d’enfants.

Peut-être pour des simulations, mais cela prendrait une tonne de mémoire.

Answer 1

Ryan, la réponse est définitivement OUI.

Contrairement à la première réponse, le problème persistant ne prouve rien. En fait, Ryan, ce que vous suggérez prouve que le problème critique faux ne s’applique pas aux vrais ordinateurs numériques, et j’en ai déjà fait preuve à cet égard.

Dans un système numérique déterministe (c’est-à-dire un programme fonctionnant sur du matériel numérique réel), le nombre d’états possibles est fini et, par conséquent, tous les états possibles sont énumérables.

La quantité exacte de mémoire requise pour le hachage serait:

(2) * (taille de l'état du programme) * (nombre d'états initiaux)

L’état initial correspond à votre clé de hachage et l’état final correspond à la valeur de hachage. Vous disposez alors d’une paire clé / valeur pour chaque état initial.

Pour un système d'exploitation, la " taille de l'état du programme " est 2 ^ (gigabits de mémoire total sur tous les périphériques du système). De toute évidence, un programme aussi volumineux et polyvalent nécessiterait une quantité de mémoire inutilisable pour le hachage, et ne serait de toute façon pas utile, car le système est auto-référençant / complexe de manière irréductible (la prochaine entrée de l'utilisateur dépend des données précédentes du système).

Explication:

Cela est très utile, car si vous indexez tous les états initiaux possibles et que vous les associez à l’état final, vous réduirez effectivement le temps d’exécution de TOUT PROGRAMME à zéro! Tout par zéro, j'entends un temps d'exécution très rapide en O (1) - le temps nécessaire pour rechercher l'état final (s'il se termine).

L'exécution d'un programme à partir de chacun des états possibles fournira une sorte de carte d'états montrant les cycles. Le problème d'arrêt est donc résolu car il n'y a que trois possibilités (en réalité quatre se réduisant à trois) compte tenu de l'état initial possible:

1. Le programme reviendra dans un état déjà rencontré (depuis l’état initial), avant d’épuiser tous les états possibles, et sera donc bouclé logiquement pour toujours.
2. Le programme atteint un état identifié comme "terminaison". avant de pouvoir revenir dans un état déjà rencontré ou d’épuiser tous les états possibles (depuis l’état initial).

3. ou 4. Le programme le plus simple commencera à partir d'un état initial, entrera tous les états possibles exactement une fois, puis n'aura d'autre choix que de (3) s'arrêter ou (4) de rentrer dans un état déjà rencontré et de mettre en boucle pour toujours .

   pour (int i = 0; true; i ++); // j'atteindrai la valeur maximale, je reviendrai à zéro, point auquel l'état initial sera rentré

Donc, en gros, votre index pourrait être décrit ainsi:

• Pour chaque état initial, il existe exactement un ou zéro états de fin.

En d’autres termes, pour chaque état initial, le programme atteint un état final ou rentre dans un état déjà rencontré depuis l’état initial et cycle indéfiniment.

Ainsi, pour tout programme utilisant un matériel numérique déterministe , il est absolument possible (mais souvent pas pratique ) de déterminer tous ses états. et si elle s'arrête ou boucle pour toujours.

• L'aspect pratique dépend uniquement du nombre d'états initiaux valides que vous avez (que vous pouvez réduire de manière drastique avec des contraintes d'entrée) et de la faisabilité de prendre le temps nécessaire pour exécuter le programme pour chacun d'eux. terminer et stocker l’état résultant dans la table de hachage.

Outre le fait de forcer la durée d'exécution d'un programme à une opération O (1), l'utilisation de l'état de capture inclut la fonction de sauvegarde de l'état dans les émulateurs de la console de jeu et la fonction de veille prolongée des ordinateurs (bien que la restauration de l'état ne soit pas parfaite, car certaines mémoires système). doit être utilisé pour le code qui restaure l'état et une certaine mémoire peut ne jamais être stockée (par exemple, une mémoire GPU)).

Cela prouve que tout programme peut être représenté par une table de hachage. Tout programme peut être représenté par une carte de transition d'état initiale à finale. Tous les programmes peuvent être simplifiés en une seule fonction avec une énorme empreinte mémoire!

Answer 2

Cela ne serait pas possible à résoudre pour un programme général. Le problème d’arrêt prouve qu’il est impossible de déterminer si un programme sera interrompu. Le problème de déterminer si un état donné est possible est réductible au problème bloquant et ne peut donc pas être résolu non plus.

Answer 3

Je pense que cette approche serait totalement intraitable pour, eh bien, tout.

En tant que problème de recherche, il est trop gros. Si nous supposons que chaque État peut aboutir à 10 résultats (même si je pense que ce nombre est vraiment faible), il ne nous reste plus maintenant que 200 milliards de possibilités à parcourir.

Et rappelez-vous que chaque étape d'une boucle compte comme une branche. Donc, si nous avons un code qui ressemble à ceci:

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

Le nombre d'états possibles est alors (nombre de branches dans une fonction) ^ 100

Answer 4

Bien que Josh ait raison de dire que vous ne pouvez pas répondre à la version la plus libérale de ce problème en raison de son ambiguïté, vous pouvez y répondre si vous placez certaines limitations dans votre scénario. Il existe une grande différence entre l'état de votre programme et l'état des entités commerciales, par exemple.

Par exemple, supposons que vous ayez une application orientée flux de travail définie par un DFA (machine à états). En fait, vous pouvez ensuite associer un point donné de ce DFA à un identifiant quelconque.

Alors oui, c'est faisable mais pas sans restrictions.

Answer 5

Ceci est fait au niveau de la fonction; c'est une technique appelée mémoization .

Answer 6

Étudiez les structures de Kripke et la logique modale. C'est une approche adoptée dans les programmes de modélisation. J'oublie ce que sont les systèmes classiques qui utilisent cette approche.