通过以位为单位的长度确定程序的执行时间？

Question

这是我在阅读停机问题、collatz 猜想和 Kolmogorov 复杂度时突然想到的一个问题。我曾尝试搜索类似的内容，但我找不到特定的主题，可能是因为它的价值不大，也可能只是一个微不足道的问题。

为了简单起见，我举三个例子programs/functions。

function one(s):
  return s

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

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

所以我的问题是，如果有一种方法可以形式化程序的长度（比如用于描述它的位）以及程序使用的内部存储器，以确定 minimum/maximum 数字需要 time/steps 来决定程序是终止还是永远运行。

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

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

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

Answer 1

如果确定性图灵机两次进入完全相同的配置（我们可以通过跟踪目前看到的配置来检测），那么我们立即知道 TM 将永远循环。

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

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

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

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

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

通过以位为单位的长度确定程序的执行时间？

Determining a program's execution time by its length in bits?

time-complexity

collatz

code-complexity

halting-problem

computability