3.18 Undecidable Problems 不可判定问题
There exist problems that computers cannot solve, and even when a computer can solve a problem, it may not be able to do so in a reasonable amount of time.
- 存在计算机无法解决的问题，即使计算机能够解决一个问题，它也可能无法在合理的时间内做到。
核心要点 Core Points
A decidable problem is a decision problem for which an algorithm can be written to produce a correct output for all inputs (e.g., "Is the number even?").
- 一个可判定问题是一个决策问题，可以为其编写算法为所有输入产生正确的输出（例如，"这个数字是偶数吗？"）。
An undecidable problem is one for which no algorithm can be constructed that is always capable of providing a correct yes-or-no answer.
- 一个不可判定问题是一个无法构造总是能够提供正确是或否答案的算法的问题。
An undecidable problem may have some instances that have an algorithmic solution, but there is no algorithmic solution that could solve all instances of the problem.
- 一个不可判定问题可能有一些具有算法解决方案的实例，但没有算法解决方案能够解决该问题的所有实例。
学生活动 Student Activities
- Explain the existence of undecidable problems in computer science.
- 解释计算机科学中不可判定问题的存在。
相关介绍 Related Resources
不可判定问题的定义
不可判定问题是不存在任何算法（无论运行时间多长、占用空间多大）能解决的判定问题 —— 即对于这类问题，不存在一个通用程序，能对所有输入实例都输出正确的「是 / 否」答案。
经典例子：图灵停机问题
- 问题描述：给定一个程序和输入，这个程序是否会在有限步后停机？
- 证明结果：图灵已证明，不存在任何算法能解决所有停机问题的实例，因此它是不可判定问题。
- 关键属性：不可判定问题的核心是「根本无法用算法解决」，无论算法效率如何。
补充说明：容易混淆的「NP 难问题」
需注意：「NP 难问题」（NP-hard）与「NP 问题」不同：
- 部分 NP 难问题是不可判定的（例如「停机问题」是 NP 难的，但它不可判定）。
- 但「NP 问题」的定义严格限定了「可验证」，因此必然是可判定的，与不可判定问题无交集。