The Concept of a Limit in Computer Science | 计算机科学中的极限概念

📚 The Concept of a Limit in Computer Science | 计算机科学中的极限概念

The concept of a limit, borrowed from mathematical analysis, is a powerful lens through which computer science examines resources, precision, and computability. In A-level computer science, understanding limits helps you reason about algorithm efficiency, numerical accuracy, recursion depth, and the fundamental boundaries of what a computer can compute.

“极限”这一概念源自数学分析，但它为计算机科学提供了一副强有力的透镜，用以审视资源、精度与可计算性。在 A-Level 计算机科学中，理解极限有助于你推理算法的效率、数值精度、递归深度，以及计算机在根本层面上能做什么、不能做什么。

1. What Does “Limit” Mean in Computing? | 计算中的“极限”指什么？

In mathematics, a limit describes the value that a function approaches as its input approaches some point. In computing, we adopt the same idea to study how a system behaves as its parameters grow or shrink without bound. For example, what happens to the running time of an algorithm as the size of its input tends to infinity? What happens to the error of a numerical method as we take more iterations?

在数学中，极限描述的是当输入趋近某一点时函数所趋近的值。在计算中，我们借用同样的思想来研究当参数无界增长或缩减时系统的行为。例如，当输入规模趋向无限大时，算法的运行时间会怎样变化？当我们进行更多次迭代时，数值方法的误差会怎样变化？

lim (n → ∞) f(n) = L meaning f(n) gets arbitrarily close to L

The central idea is that we do not need to reach the limit; we only care about behaviour near or beyond the limit. This abstraction lets computer scientists classify algorithms and systems into broad categories.

核心思想是我们不需要真正到达极限；我们只关心在极限附近或超越极限时的行为。这种抽象让计算机科学家能够将算法和系统划分为宽泛的类别。

2. Limits in Algorithmic Analysis | 算法分析中的极限

When analysing algorithms, we often ask: “How does the running time or memory usage scale as input size n increases?” The limit here is about asymptotic growth, i.e., the trend as n tends to infinity. For example, consider the simple loop:

在分析算法时，我们常问：“随着输入规模 n 增大，运行时间或内存使用如何扩展？”这里的极限关乎渐近增长，即当 n 趋向无穷时的发展趋势。例如，考虑一个简单的循环：

Constant time: T(n) = c, no matter how large n becomes.

常数时间：T(n) = c，无论 n 多大，运行时间不变。
Linear time: T(n) ≈ c × n. The limit of T(n)/n is a finite constant.

线性时间：T(n) ≈ c × n。T(n)/n 的极限是一个有限常数。
Quadratic time: T(n) ≈ c × n². The limit of T(n)/n² is finite.

平方时间：T(n) ≈ c × n²。T(n)/n² 的极限是有限的。

These limits tell us that for very large n, the dominant term (n, n², log n, etc.) determines the rate of growth. This is the foundation of Big O notation.

这些极限告诉我们，对于非常大的 n，主导项（n、n²、log n 等）决定了增长速度。这正是大 O 记号的基石。

3. Big O Notation as a Limit | 大 O 记号与极限

Formally, a function f(n) is O(g(n)) if there exist positive constants C and n₀ such that for all n ≥ n₀, f(n) ≤ C·g(n). This definition resembles the limit definition: the ratio f(n)/g(n) remains bounded as n → ∞.

形式上，若存在正常数 C 和 n₀，使得对所有 n ≥ n₀ 都有 f(n) ≤ C·g(n)，则称 f(n) 是 O(g(n))。这个定义类似于极限定义：当 n → ∞ 时，比值 f(n)/g(n) 保持在有界范围内。

f(n) = O(g(n)) ⇔ lim sup (n → ∞) f(n)/g(n) < ∞

In practice, we drop constants and lower-order terms. Thus O(2n + 5) simplifies to O(n). The limit concept allows us to focus on the dominant behaviour.

在实践中，我们忽略常数项和低阶项。因此 O(2n + 5) 简化为 O(n)。极限概念让我们专注于主导行为。

Algorithm class	Limit behaviour as n → ∞
O(1)	Time is constant
O(log n)	Time grows very slowly
O(n)	Time grows linearly
O(n²)	Time grows quadratically
O(2ⁿ)	Time grows exponentially

4. Limits in Floating-Point Precision | 浮点数精度中的极限

Computers store real numbers with finite precision, following the IEEE 754 standard. There is always a smallest representable difference between two numbers, called the machine epsilon (ε). For double precision, ε ≈ 2⁻⁵² ≈ 2.22×10⁻¹⁶. This is a hard limit on relative precision.

计算机按照 IEEE 754 标准以有限精度存储实数。两个可表示数之间总存在一个最小的可区分差值，称为机器精度（ε）。对于双精度，ε ≈ 2⁻⁵² ≈ 2.22×10⁻¹⁶。这是相对精度的硬性极限。

fl(a ⊕ b) = (a + b)(1 + δ), |δ| ≤ ε

Every arithmetic operation introduces a relative error bounded by ε. When we take limits of iterative processes (e.g., summing a series), the accumulated error may prevent convergence to the true mathematical limit. Thus numerical methods must contend with the limit imposed by finite word length.

每次算术运算都会引入以 ε 为界的相对误差。当我们对迭代过程（如级数求和）取极限时，累积误差可能阻止收敛到真正的数学极限。因此数值方法必须应对有限字长所强加的极限。

5. Convergence of Numerical Methods | 数值方法的收敛性

A numerical method is said to converge if, as the step size tends to zero (or the iteration count tends to infinity), the approximate solution approaches the exact solution. For example, Newton’s method for solving f(x) = 0 produces a sequence x₀, x₁, x₂, … whose limit should be a root.

若当步长趋近于零（或迭代次数趋近于无穷）时，近似解趋近于精确解，则称该数值方法是收敛的。例如，求解 f(x) = 0 的牛顿法产生序列 x₀, x₁, x₂, …，其极限应为方程的根。

lim (n → ∞) xₙ = α where f(α) = 0

However, in a computer, we cannot take an infinite limit. We stop when the change |xₙ₊₁ − xₙ| is smaller than some tolerance. Therefore the “limit” is approximated within a margin of error. The rate of convergence (linear, quadratic, etc.) describes how quickly the sequence approaches the limit.

然而，在计算机中我们无法执行无限极限。我们会在 |xₙ₊₁ − xₙ| 小于某个容差时停止。因此“极限”是在一定误差范围内近似的。收敛速率（线性、二次等）描述了序列接近极限的速度。

6. Limit of Recursion Depth | 递归深度的极限

Recursion relies on the call stack, which has a finite size in any real computer. Each recursive call consumes stack memory. There is a limit to how many nested calls can exist before stack overflow occurs. This is a practical limit on the depth of recursion.

递归依赖于调用栈，而任何真实计算机中的调用栈大小是有限的。每次递归调用都会消耗栈内存。在发生栈溢出之前，嵌套调用能够存在的数量是有极限的。这是递归深度的实际极限。

For example, the Fibonacci function defined naively as fib(n) = fib(n−1) + fib(n−2) has a recursion depth of n, but its time complexity grows exponentially, limiting n even if the stack were infinite.

例如，朴素定义的斐波那契函数 fib(n) = fib(n−1) + fib(n−2) 的递归深度为 n，但其时间复杂度呈指数增长，即便栈是无限的，n 也会受到制约。

This illustrates a deeper limit: even a simple mathematical recurrence can exceed computational resources. In theory, a Turing machine has unlimited memory, but physical computers do not. Thus the theoretical limit of recursion is infinity, while the practical limit is finite.

这揭示了一个更深刻的极限：即便简单的数学递推也可能超出计算资源。理论上图灵机拥有无限内存，但物理计算机没有。因此递归的理论极限是无穷，而实际极限是有限的。

7. Limits of Finite State Machines | 有限状态机的极限

A finite state machine (FSM) has a finite number of states. Because of this, it can only recognise languages that do not require unbounded counting. For example, an FSM cannot recognise the language {aⁿbⁿ | n ≥ 1} because that requires counting the number of a’s and matching it to the number of b’s, which in general needs unbounded memory.

有限状态机（FSM）拥有有限数量的状态。因此，它只能识别不需要无界计数的语言。例如，FSM 无法识别语言 {aⁿbⁿ | n ≥ 1}，因为那需要计算 a 的个数并将其与 b 的个数匹配，这通常需要无界内存。

The limit of an FSM is that its memory is fixed by the number of states. No matter how many transitions we add, as long as the state set is finite, there exist strings long enough to create a repeated state, forcing the machine to lose count. This is a fundamental limitation of space.

FSM 的极限在于其内存由状态数固定。无论添加多少转移，只要状态集合是有限的，就存在足够长的字符串导致状态重复，迫使机器失去计数能力。这是空间上的根本限制。

8. Turing Machines and the Limits of Computation | 图灵机与计算的极限

A Turing machine extends the FSM with an unbounded tape, so it can handle any computation that a modern computer can, given enough time and memory. However, there are still problems that a Turing machine cannot solve, no matter how much time it is given. These are called undecidable problems.

图灵机用无界纸带扩展了 FSM，因此在时间和内存充足的情况下，它可以处理现代计算机所能处理的任何计算。但仍然存在图灵机无论如何都无法解决的问题，即不可判定问题。

The most famous example is the Halting Problem: determining whether an arbitrary program will terminate or run forever. Alan Turing proved in 1936 that no algorithm can decide this for all program-input pairs. This is the ultimate limit of practical computation.

最著名的例子是停机问题：判断任意程序是否会终止还是永远运行。阿兰·图灵在 1936 年证明，不存在算法能够对所有程序-输入对给出判定。这是实用计算的最终极限。

No computable function H(P, I) can decide whether program P halts on input I for all P and I.

9. The Halting Problem as a Limit | 停机问题：一种极限

The Halting Problem demonstrates that there is a “limit” to what computable functions can achieve. The set of all programs is countable, but the set of all possible behaviours is uncountably rich. We can define a function that is not computable by diagonalisation, in the same spirit as showing that the real numbers are uncountable.

停机问题表明可计算函数所能达到的目标存在“极限”。所有程序的集合是可数的，但所有可能行为的集合却无比丰富。我们通过对角线化可以定义一个不可计算的函数，这与证明实数不可数的思路一脉相承。

In terms of limits: suppose we try to approximate a decision by running the program for longer and longer. As time tends to infinity, we might hope to observe whether it halts. But if the program has not halted yet after 10¹⁰⁰ seconds, we still cannot conclude that it will never halt. The limit of this naive observation is indeterminate.

就极限而言：假设我们尝试通过让程序运行越来越久来逼近判定。当时间趋向无穷时，我们或许希望观察到它是否停机。但如果在 10¹⁰⁰ 秒后仍未停机，我们仍不能断定它永远不会停机。这种朴素观察的极限是悬而未决的。

10. Undecidability and Uncomputable Limits | 不可判定与不可计算的极限

Beyond the Halting Problem, many other problems are undecidable, such as the Entscheidungsproblem, the Post correspondence problem, and whether a given context-free grammar is ambiguous. Each represents a limit that separates the computable from the uncomputable.

除停机问题外，许多其他问题也是不可判定的，例如判定问题、波斯特对应问题，以及给定上下文无关文法是否具有歧义性。每一个都代表着可计算与不可计算之间的分界线。

The existence of such limits is not merely theoretical. In software engineering, static analysis tools often attempt to automatically verify properties of programs (like “no buffer overflow” or “no infinite loop”). Because of undecidability, these tools cannot be both sound and complete; they must make approximations. Thus developers accept a limit on what can be automated.

此类极限的存在不仅仅是理论上的。在软件工程中，静态分析工具常尝试自动验证程序的性质（如“无缓冲区溢出”或“无死循环”）。由于不可判定性，这些工具无法同时做到可靠且完备；它们必须进行近似。因此开发者接受自动化所能达到的极限。

11. Practical Implications of Computational Limits | 计算极限的实践意义

Understanding limits helps computer scientists make design trade-offs. For example, because algorithm efficiency has a lower bound for certain problems (e.g., comparison-based sorting requires Ω(n log n) comparisons in the worst case), we know that no clever algorithm can beat that limit; we only optimise constants.

理解极限有助于计算机科学家做出设计权衡。例如，因为某些问题存在算法效率下界（如基于比较的排序在最坏情况下需要 Ω(n log n) 次比较），我们知道没有任何聪明的算法能突破该极限；我们只能优化常数。

Precision limits guide how we design numerical algorithms to reduce error accumulation.

精度极限 指导我们设计数值算法以减少误差累积。
Memory limits influence choices between iterative and recursive solutions.

内存极限 影响我们在迭代与递归之间的选择。
Undecidability limits shape what we can expect from automated program verification.

不可判定性极限 决定了我们对程序自动验证可抱有的期望。

12. Conclusion: Embracing Limits | 结论：拥抱极限

The concept of a limit translates from mathematics into computer science at many levels: from the complexity of algorithms to the precision of numbers, from the depth of recursion to the boundaries of decidability. Recognising these limits allows us to build more robust systems and to avoid impossible requirements.

极限概念从数学渗透到计算机科学的许多层面：从算法的复杂度到数值的精度，从递归的深度到可判定性的边界。识别这些极限让我们能够构建更稳健的系统，并避免提出不可能实现的需求。

As an A-level student, you should be able to explain how limits underpin Big O notation, machine epsilon, stack depth, and the Halting problem. These ideas unify the theoretical and practical sides of computing.

作为 A-Level 学生，你应该能够解释极限如何支撑大 O 记号、机器精度、栈深度和停机问题。这些思想将计算的理论与实践方面统一起来。

Published by TutorHao | Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

The Concept of a Limit in Computer Science | 计算机科学中的极限概念