我读过一些关于大哦计算和停机问题的文章。显然，所有算法都不可能说它们是否会停止，例如：
while(System.in.readline()){
}
但是，这样的程序有什么大不了的呢？我认为它没有定义，出于同样的原因，也无法说它是否会停止。你不知道。
所以......有一些可能的算法，你不能说它是否会停止。但是，如果你不能说，那么该算法的大问题是未定义的。
现在到我的观点，计算一个软件的大哦。为什么你不能写一个程序来做到这一点？因为它要么是一个函数，要么是未定义的。
另外，我没有说任何关于编程语言的事情。纯函数式编程语言呢？可以在那里计算吗？
好的，让我们来谈谈图灵机（可以使用随机访问模型进行类似的讨论，但为了简单起见，我采用了这个）。
TM 时间复杂度的上限说明了 TM 进行的转换次数根据输入大小而增长的速率顺序。具体来说，如果我们说一个 TM 在输入大小 n 的最坏情况下执行一个 O(f(n)) 的算法，我们就是说存在一个 n0 和 c 使得对于 n > n0，T(n) <= cf(n)。到目前为止，一切都很好。
现在，图灵机的问题是它们可能无法停止，也就是说，它们可以永远执行某些输入。显然，如果对于某些 n* > n0，一个 TM 采取了无数步，则没有 f(n) 满足上一段中列出的条件（n0, c 有限）；也就是说，对于任何 f，T(N) != O(f(n))。好的; 如果我们能够肯定地说，对于长度至少为 n0 的所有输入，TM 将停止，对于某些 n0，我们是免费的。麻烦的是，这相当于解决了停机问题。
所以我们得出这样的结论：如果一个 TM 在输入 n > n0 上永远停止，那么我们就不能定义复杂度的上限；此外，通过算法确定 TM 是否会在所有大于固定的有限 n0 的输入上停止是一个无法解决的问题。
无法回答问题“ 'while(System.in.readline()){}' 程序将要停止吗？ ”的原因是没有指定输入，所以在这种特殊情况下，问题是缺少信息而不是不确定性。
停止问题是关于不可能构建一个通用算法，当同时提供一个程序和一个输入时，它总是可以判断带有该输入的程序是完成运行还是永远继续运行。
在停机问题中，程序和输入都可以任意大，但它们的目的是有限的。
此外，没有“程序+输入”的特定实例本身是不可确定的：给定一个特定实例，（原则上）总是可以构造一个算法来分析该实例和/或实例类，并计算正确答案。
然而，如果一个问题是不可判定的，那么无论算法被扩展多少次以正确分析额外的实例或实例类，这个过程永远不会结束：总是有可能提出算法不会的新实例除非进一步扩展，否则能够回答。
我会说“ while(System.in.readline()){} ”的大 O 是 O(n)，其中 n 是输入的大小（该程序可以看作是例如行计数程序的骨架）。
在这种情况下定义了大 O，因为对于每个有限大小的输入，程序都会停止。
所以要问的问题可能是：“程序是否会在它可能提供的每个可能的有限输入上停止？ ”
如果该问题可以简化为停止问题或任何其他不可判定的问题，那么它是不可判定的。
事实证明，它可以减少，正如这里澄清的那样： https ://cs.stackexchange.com/questions/41243/halting-problem-reduction-to-halting-for-all-inputs
不可判定性是问题的一个属性，它独立于用于构建在同一台机器上运行的程序的编程语言。例如，您可能认为任何用函数式编程语言编写的程序都可以编译成机器代码，但是同样的机器代码可以由用汇编编写的等效程序生成，所以从图灵机的角度来看，函数式编程语言不再是比汇编语言强大。
此外，不确定性不会阻止算法能够为无数（理论上无限）数量的程序计算大 O，因此为此目的构建算法的任何努力都不一定是毫无意义的。