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

意思是说我们启动了一个程序，结果只有很多可能的结果，比如说8.

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

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

可以将它想象成一棵树，其中没有孩子的节点是最终结果，并且节点与其父节点或者子节点之间的每个分支都是一个"状态"，每个键的键位不同。因此，虽然只有8个叶子或者该过程的最终结果，但可能会有许多"状态"，这取决于逻辑在孩子们快要耗尽之前从树上掉下来的深度。

也许是用于模拟，但是会占用大量内存。

解决方案

这是在功能级别上完成的。这是一种称为记忆的技术。

这对于一般程序是不可能解决的。停止问题证明了无法确定程序是否将停止。确定给定状态是否可能的问题可以减少到停止问题，因此也不能解决。

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

作为搜索问题，它太大了。如果我们假设每个州都可以带来10个结果(尽管我认为这个数字确实很低)，那么仅向前看20个步骤，我们现在就必须跟踪2000亿种可能性。

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

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

那么可能的状态数是(some_function内部的分支数)^ 100

研究克里普克结构和模态逻辑。这是建模程序中采用的一种方法。我忘记了使用这种方法的经典系统。

尽管乔希(Josh)因其模棱两可而无法回答这个问题的最宽松版本是正确的，但如果我们对方案有一些限制，则可以回答。程序状态和业务实体的状态之间存在很大差异。

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

是的，这很容易处理，但并非没有限制。

瑞安，答案肯定是。

与第一个答案相反，停顿问题没有任何证明。实际上，瑞安(Ryan)，建议是要证明错误的暂停问题不适用于真正的数字计算机，并且我之前已使用此示例作为证明。

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

散列所需的确切内存量为：

(2)*(程序状态大小)*(初始状态数)

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

对于操作系统，"程序状态大小"为2 ^(所有系统设备上的总内存量)。显然，如此大的通用程序将需要不切实际的内存量来进行哈希处理，并且由于系统是自引用的/不可简化的(也就是说，下一个用户输入取决于先前的系统输出)，因此无论如何都不会有用。

解释：

这非常有用，因为如果我们索引每个可能的初始状态并将其与终止状态相关联，则可以有效地使ANY PROGRAM的运行时间为零！零表示我是指非常快的O(1)运行时间-查找终止状态(如果终止)所花费的时间。

从所有可能的状态中的每一个开始运行程序，将提供一种显示周期的状态图。停止问题因此得以解决，因为给定任何可能的初始状态，只有三种可能性(实际上是四种崩塌为三种)：

• 程序将在耗尽所有可能的状态之前重新输入先前遇到的状态(自初始状态起)，因此逻辑上将永远循环。
• 程序有机会重新进入先前遇到的状态或者耗尽所有可能的状态(自初始状态起)之前，已到达被标识为"终止"的状态。
• 或者4.最简单的程序将从初始状态开始，将完全进入所有可能的状态一次，然后别无选择，只能(3)停止或者(4)重新进入先前遇到的状态并永远循环。为(int i = 0; true; i ++); // i会达到最大值，并回滚到零，这时它将重新进入初始状态

因此，基本上，索引可以这样描述：

• 对于每个初始状态，恰好有一个或者零个终止状态。

换句话说，对于每个初始状态，程序或者达到终止状态，或者
重新进入自初始状态以来已经遇到的状态，并不断循环。

因此，对于在确定性数字硬件上运行的任何程序，绝对有可能(但通常不切实际)确定其所有状态以及它是否永远停止或者循环。

• 实用性仅取决于我们具有多少个有效的初始状态(可以通过输入约束来大幅度减少)，以及花时间运行程序以终止每个状态并将结果存储在哈希表中是否可行桌子。

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

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