哈尔滨工业大学李建中：计算复杂性初步——递归与不可判定性研究

本篇文档是哈尔滨工业大学李建中教授于2018年编写的关于计算复杂性初步的讲义，章节名为“不可判定性/不可计算性”。该章节主要探讨了以下几个核心概念： 1. **非递归可枚举语言**：这些语言由一组TM（图灵机）决定，但不是递归可枚举的，即不存在单个TM能一一列举出该语言的所有元素。递归可枚举语言是指可以通过一个必停机TM来识别的语言。 2. **不可判定的RE语言**：这些语言属于递归可枚举语言范畴，但由于某种数学上的复杂性，无法证明它们是否包含某个特定的输入字符串。这意味着没有通用的算法来确定一个给定的输入是否属于此类语言。 3. **归约（Reduction）**：这是一个在证明复杂性问题之间关系的关键技术，通过将一个较难的问题转换为另一个已知难度的问题来理解其难度。在不可判定性中，如果一个问题A可以归约到问题B，而B不可判定，那么A也被认为是不可判定的。 4. **关于TM的不可判定问题**：如著名的Halting Problem（停止问题），即无法确定任意给定的TM是否会无限运行下去。这是计算理论中的一个经典不可判定问题。 5. **POST对应问题**：Post correspondence problem（PCP）是另一个不可判定问题，涉及寻找一系列符号序列之间的对应规则，这在实践中是不可行的。 6. **其他不可判定问题**：除了上述，还有其他一些复杂性问题，如Undecidable Language Problem（不可判定语言问题）和Undecidable Decision Problem（不可判定决策问题），它们同样展示了计算能力的局限性。 在整个章节中，作者通过递归、部分递归和完全递归函数的概念，以及对{0,1}*（二进制字符串集合）与自然数映射的讨论，进一步阐述了这些概念的逻辑关系。同时，图灵机的编码被用来实例化这些理论，说明如何将机器模型转化为可操作的数字序列，从而便于分析其计算能力。 总结来说，这一章深入剖析了计算复杂性中的核心概念，展示了在计算机科学理论中，尽管我们有许多强大的工具，但仍有一些问题由于其内在的复杂性，我们无法用现有的技术手段解决。这不仅揭示了计算机科学的边界，也为我们理解和设计更高效的算法提供了指导。