状态和时间超越逻辑和程序流程？

题

想知道使用一些参考键来索引应用程序的每个可能状态是否有用......

意思是，假设我们有一个程序启动，只有这么多可能的结果，比如 8。

但是，如果每个结果都是通过逐步执行更多逻辑状态来获得的，并且每个分支之间都被视为一个状态并映射到一个键。

在大型程序中，它可能需要大量内存，但如果我们可以直接访问密钥（密钥可以基于时间或逻辑深度），那么我们可以立即遍历任何可能的情况，而无需启动整个过程再次使用新数据。

把它想象成一棵树，其中没有子节点的节点是最终结果，节点与其父节点或子节点之间的每个分支都是一个“状态”，每个分支的键控不同。因此，虽然只有 8 个叶子或该过程的最终结果，但可能有许多“状态”，具体取决于逻辑在子级用完之前沿着树的深度。

也许用于模拟，但这需要大量内存。

解决方案

瑞安，答案是肯定的。

与第一个答案相反，停止问题并不能证明任何事情。事实上，瑞安，你的建议证明了停机问题 ~~错误的~~ 不适用于真正的数字计算机，我之前已经用这个例子来证明它。

在确定性数字系统中（即在真实数字硬件上运行的程序），可能的状态数量是有限的，因此所有可能的状态都是可枚举的。

哈希所需的确切内存量为：

(2)*(program state size)*(number of initial states)

初始状态将是哈希键，最终状态将是哈希值，然后每个初始状态都有一个键/值对。

对于操作系统，“程序状态大小”是 2^（所有系统设备的内存总千兆位）。显然，如此大的通用程序需要不切实际的内存量来进行散列，并且无论如何都没有用，因为系统是自引用/不可简化的复杂性（即下一个用户输入取决于之前的系统输出）。

解释：

这是非常有用的，因为如果您索引每个可能的初始状态并将其与终止状态相关联，您将有效地将任何程序的运行时间降至零！任何为零，我的意思是非常快的 O(1) 运行时间——查找终止状态（如果它终止）所需的时间。

从每个可能的状态开始运行程序，将提供一种显示循环的状态图。 因此，停止问题得到了解决，因为给定任何可能的初始状态，只有三种（实际上是四种折叠为三种）可能性：

在耗尽所有可能的状态之前，程序将重新进入先前遇到的状态（自初始状态以来），因此逻辑上永远循环。
程序在有机会重新进入先前遇到的状态或耗尽所有可能的状态（自初始状态以来）之前就到达了标识为“终止”的状态。
或 4。最简单的程序将从初始状态开始，一次进入所有可能的状态，然后别无选择，只能 (3) 停止或 (4) 重新进入先前遇到的状态并永远循环。

对于（int i = 0；真的;我++）；//i将达到最大值，回滚到零，此时它将重新进入初始状态

所以，基本上，你的索引可以这样描述：

换言之，对于每个初始状态，程序要么达到终止状态，要么重新进入自初始状态以来已经遇到的状态，并无休止地循环。

因此，对于任何运行在 确定性数字硬件, ，这是 绝对有可能 （但经常 不实用）来确定其所有状态以及是否停止或永远循环。

除了强制任何程序的运行时间为 O(1) 操作之外，捕获状态的其他用途包括游戏机模拟器中的保存状态功能和计算机的休眠功能（尽管不是完美的状态恢复，因为必须使用一些系统内存）对于恢复状态的代码，某些内存可能永远不会被存储（例如GPU 内存））。

这证明了任何程序都可以用哈希表来表示。任何程序都可以用初始到最终的状态转换图来表示。所有程序都可以简化为一个具有大量内存占用的大函数！

其他提示

这不可能解决一般程序。暂停问题证明无法确定程序是否会停止。确定给定状态是否可能的问题可以归结为暂停问题，因此也无法解决。

我认为这种做法对任何事情都是完全棘手的。

作为一个搜索问题，它太大了。如果我们假设每个州可以导致10个结果（虽然我认为这个数字真的很低），那么只需要前面20步，我们现在必须跟踪2000亿个可能性。

请记住，循环中的每一步都算作分支点。因此，如果我们的代码如下所示：

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

然后可能的状态数是（some_function内的分支数）^ 100

虽然Josh是正确的，由于它的含糊不清，你无法回答这个问题最自由的版本，如果你对你的场景有一些限制，你可以回答它。您的计划状态与商业实体的状态之间存在很大差异。

例如，假设您有一个由DFA（状态机）定义的面向工作流的应用程序。然后，您实际上可以将该DFA中的给定点与某种ID相关联。

所以是的，它易于处理，但并非没有限制。

这是在功能级别完成的;这是一种名为 memoization 的技术。

研究kripke结构和模态逻辑。这是建模程序中采用的方法。我忘了使用这种方法的经典系统是什么。

许可以下： CC-BY-SA 和归因