状态和时间超越逻辑和程序流程？
想知道使用一些参考键来索引应用程序的每个可能状态是否有用...
意思是，假设我们有一个启动的程序，只有这么多可能的结果，比如 8。
但是如果每个结果都是通过单步实现的通过更多的逻辑状态，并且每个分支之间被认为是一个状态并映射到一个键。
在大型程序中，它可能需要大量内存，但如果我们可以直接访问密钥（密钥可以基于时间或逻辑深度），那么我们可以立即遍历任何可能的情况，而无需启动整个过程再次使用新数据。
把它想象成一棵树，其中没有子节点的节点是最终结果，节点与其父节点或子节点之间的每个分支都是一个“状态”，每个分支的键控不同。 因此，虽然只有 8 个叶子或该过程的最终结果，但可能有许多“状态”，具体取决于逻辑在子级用完之前沿着树的深度。
也许用于模拟，但这需要大量内存。
Wondering if it would ever be useful to index every possible state of an application using some reference keys...
Meaning, say we have a program that starts, has only so many possible outcomes, say 8.
but if each outcome is attained through stepping through many more logic states, and in between each branch is considered to be a state and is mapped to a key.
It could take a lot of memory in large programs but if we could access a key directly (the key could be based on time or depth of logic), then we could instantly traverse through any of the possible situations without having to start the whole process over again with fresh data.
Think of it like a tree where the nodes with no children are final outcomes, and every branch between a node and it's parents or children is a 'state', each one keyed differently. So while there are only 8 leaves, or final outcomes of the process, there could be many 'states' depending on how deep the logic goes down the tree before running out of children.
Maybe for simulations, but it would take a ton of memory.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
这对于一般程序来说是不可能解决的。 停止问题证明不可能确定程序是否会停止。 确定给定状态是否可能的问题可以简化为暂停问题，因此也无法解决。
This would not be possible to solve for a general program. The halting problem proves that is impossible to determine whether a program will halt. The problem of determining whether a given state is possible is reducible to the halting problem, thus not solvable either.
我认为这种方法对于任何事情来说都是完全棘手的。
作为一个搜索问题，它太大了。 如果我们假设每个状态可以导致 10 个结果（尽管我认为这个数字非常低），那么仅仅向前看 20 步，我们现在就必须跟踪 2000 亿种可能性。
请记住，循环中的每个步骤都算作分支点。 因此，如果我们有如下所示的代码：
那么可能的状态数为 (some_function 内的分支数) ^ 100
I think this approach would be totally intractable for, well, anything.
As a search problem, it's too big. If we assume that each state can lead to 10 outcomes (though I think this number is really low), then to look just 20 steps ahead, we now have to keep track of 200 billion possibilities.
And remember that every step in a loop counts as a branch point. So if we have code that looks like this:
Then the number of possible states is (number of branches inside some_function) ^ 100
虽然乔希是对的，由于这个问题的含糊性，你无法回答这个问题的最自由的版本，但如果你对你的场景设置一些限制，你就可以回答它。 您的程序的状态与业务实体的状态之间存在很大差异。
例如，假设您有一个由 DFA（状态机）定义的面向工作流的应用程序。 实际上，您可以将 DFA 中的给定点与某种 id 相关联。
所以，是的，它很容易处理，但并非没有限制。
While Josh is right that you can't answer the most liberal version of this problem due to the ambiguity of it, you can answer it if you place some limitations on your scenario. There is a big difference between the state of your program and the state of say business entities.
For example, say you have a workflow oriented application that is defined by a DFA (State Machine). You actually could then associate a given point in that DFA with an id of some sort.
So yes it's tractable but not without restrictions.
Ryan，答案肯定是肯定的。
与第一个答案相反，停止问题并不能证明任何事情。 事实上，Ryan，你的建议证明了停止问题
错误并不适用于真正的数字计算机，而且我之前已经用这个例子作为证明。在确定性数字系统（即在真实数字硬件上运行的程序）中，可能状态的数量是有限的，因此所有可能状态都是可枚举的。
哈希所需的确切内存量为：
(2)*(程序状态大小)*(初始状态数)初始状态将是您的哈希密钥，最终状态将是哈希值，然后每个初始状态都有一个键/值对。
对于操作系统，“程序状态大小”是 2^（所有系统设备上的内存总千兆位）。 显然，如此大的通用程序需要不切实际的内存量来进行散列，并且无论如何都没有用，因为系统是自引用/不可简化的复杂性（即下一个用户输入取决于先前的系统输出）。
说明：
这非常有用，因为如果您索引每个可能的初始状态并将其与终止状态关联起来，您将有效地将任何程序的运行时间降至零！ 任何为零，我的意思是非常快的 O(1) 运行时间——查找终止状态（如果它终止）所需的时间。
从每个可能的状态开始运行程序，将提供一种显示循环的状态图。 因此解决了停止问题，因为给定任何可能的初始状态，只有三种（实际上是四种折叠为三种）可能性：
或4。最简单的程序将从初始状态开始，一次进入所有可能的状态，然后别无选择，只能（3）停止或（4）重新进入以前遇到的状态并永远循环。
for (int i = 0; true; i++); //i 将达到最大值，回滚到零，此时它将重新进入初始状态
所以，基本上，您的索引可以这样描述：
换句话说，对于每个初始状态，程序要么达到终止状态，要么
重新进入自初始状态以来已经遇到的状态并无限循环。
因此，对于在确定性数字硬件上运行的任何程序，绝对可能（但通常不切实际）确定其所有状态以及是否永远停止或循环。
除了强制任何程序的运行时间为 O(1) 操作之外，捕获状态的其他用途包括游戏机模拟器中的保存状态功能和计算机的休眠功能（尽管不是完美的状态恢复，因为必须使用一些系统内存）对于恢复状态的代码，某些内存可能永远不会被存储（例如GPU内存））。
这证明了任何程序都可以用哈希表来表示。
任何程序都可以用初始到最终的状态转换图来表示。
所有程序都可以简化为一个占用大量内存的大函数！
Ryan, the answer is definitively YES.
Contrary to the first answer, the halting problem does not prove anything. In fact, Ryan, what you're suggesting proves the halting problem
wrongdoes not apply to real digital computers, and I've used this very example as a proof of it before.In a deterministic digital system (i.e. a program running on real digital hardware), the number of possible states is finite, and therefore all possible states are enumerable.
The exact amount of memory required for the hash would be:
(2)*(program state size)*(number of initial states)The initial state would be your hash key, and final state would be the hash value, and then you'd have a key/value pair for each initial state.
For an operating system, the "program state size" is 2^(total gigabits of memory across all system devices). Obviously, such a large, general purpose program would require an impractical amount of memory to hash, and would not be useful anyway, since the system is self-referencing/irreducibly complex (i.e. next user input depends on previous system output).
Explanation:
This is highly useful, because if you index every possible initial state and associate it with the terminating state, you would effectively bring the running time of ANY PROGRAM to zero! Any by zero I mean a very fast O(1) running time -- the time it takes to look up the terminating state (if it terminates).
Running a program, starting from each of all possible states, will provide a kind of state map showing cycles. The halting problem is therefore solved, because there are only three (actually four collapsing to three) possibilities given any possible initial state:
or 4. The simplest program will start from an initial state, will enter all possible states exactly once, and then has no choice but to (3) halt or (4) reenter a previously encountered state and loop forever.
for (int i = 0; true; i++); //i will reach max-value, roll over back to zero, at which point it will have reentered the initial state
So, basically, your index could be described like this:
In other words, for each initial state, the program either reaches a terminating state or
reenters a state already encountered since the initial state and cycles endlessly.
So, for any program running on deterministic digital hardware, it is absolutely possible (but often not practical) to determine all its states and whether it halts or loops forever.
Besides forcing any program's running time an O(1) operation, other uses of capturing state include the save-state function in game console emulators and the hibernate feature of computers (although not a perfect restoration of state, since some system memory must be used for the code that restores the state and some memory may never be stored (e.g. GPU memory)).
What this proves is that any program can be represented by a hash table.
Any program can be represented by an initial-to-final state-transition map.
All programs can be simplified to one big function with a massive memory-footprint!
这是在函数级别完成的； 这是一种称为记忆化的技术。
This is done on the function level; it's a technique called memoization.
研究克里普克结构和模态逻辑。 这是建模程序中采用的方法。 我忘记了使用这种方法的经典系统是什么。
Research kripke structures and modal logic. This is an approach taken in modelling programmes. I forget what the classic systems that use this approach are.