Appearance
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.
- 解释计算机科学中不可判定问题的存在。