1

这是我在阅读停止问题、科拉茨猜想和科尔莫哥洛夫复杂性时突然想到的一个问题。我试图搜索类似的东西，但我无法找到一个特定的主题，可能是因为它没有太大的价值，或者它可能只是一个微不足道的问题。

为简单起见，我将给出三个程序/功能示例。

function one(s):
  return s

function two(s):
  while (True):
    print s

function three(s):
  for i from 0 to 10^10:
    print(s)

所以我的问题是，如果有一种方法可以形式化程序的长度（如用于描述它的位）以及程序使用的内部存储器，以确定决定所需的最小/最大时间/步数程序是终止还是永远运行。

例如，在第一个函数中，程序不会改变其内部存储器并在一些时间步后停止。
在第二个示例中，程序永远运行，但程序也不会改变其内部存储器。例如，如果我们考虑与程序 2 具有相同长度且不改变其状态的所有程序，我们是否不能确定步数的上限，如果超过该上限，我们可以得出结论，该程序永远不会终止？（如果不是为什么？）
在最后一个例子中，程序改变了它的状态（变量 i）。因此，在每一步，上限都可能发生变化。

[简而言之] Kolmogorov 复杂性提出了一种查找对象（例如一段文本）的（描述性）复杂性的方法。我想知道，给定描述程序使用的内存空间的正式方式（在运行时计算），我们是否可以计算最大步数，如果超过，我们可以知道该程序是否会终止或永远奔跑。

最后，我想向我推荐任何我认为有用的资源，并帮助我弄清楚我到底在寻找什么。
谢谢你。（对不起我的英语，不是我的母语。我希望我很清楚）

4

1 回答 1

0

如果确定性图灵机两次进入完全相同的配置（我们可以检测到 b 保留到目前为止看到的配置痕迹），那么我们立即知道 TM 将永远循环。

如果它事先知道确定性图灵机不可能使用超过某个固定不变数量的输入磁带，那么 TM 必须明确停止或最终进入它已经访问过的某些配置。假设 TM 最多可以使用 k 个磁带单元，磁带字母表是 T，状态集是 Q。那么有 (|T|+1)^k * |Q| 独特的配置（长度为 k 的（T 联合空白）的字符串数乘以状态数）并且根据鸽巢原理，我们知道采取了这么多步骤的 TM 必须输入它之前已经进入过的一些配置。

一：因为我们知道这个函数不使用内部存储器，所以我们知道它要么永远停止，要么永远循环。

二：因为我们知道这个函数不使用内部存储器，所以我们知道它要么停止，要么永远循环。

三：因为我们知道这个函数只使用固定数量的内部存储器（比如 34 位），所以我们可以在不到 2^34 次循环迭代中判断 TM 对于任何给定的输入 s 是否会停止，这是有保证的。

现在，知道TM 将使用多少磁带，或者程序将使用多少内存，并不是 TM 可以解决的问题。但是如果你有一个预言机（比如一个能够做证明的人）告诉你一个正确的固定内存上限，那么停止问题是可以解决的。

于 2020-02-12T14:45:02.300 回答