计算理论初步：对角语言与通用图灵机

"形式语言与自动机：第十三讲 计算理论初步.pdf" 这篇文档主要介绍了计算理论的一些基本概念，特别是关注于形式语言与自动机的领域。在第十三讲中，作者首先提及了计算理论的初步知识，包括对角语言、通用语言以及问题与语言的关系。 对角语言是计算理论中的一个重要概念，它指的是那些不是递归可枚举的语言。这些语言不能被任何确定性或非确定性图灵机以确定的方式枚举出所有元素。通过对角化技术，可以构造出这样的语言，例如克莱尼-图灵对角线方法，用于证明某些语言无法被特定的图灵机识别。 接着，文档提到了递归语言和递归可枚举语言的补运算。递归语言是指存在一个确定性图灵机可以在有限步骤内判断其每个元素是否属于该语言的语言。递归可枚举语言则更广泛，允许存在非停机的枚举过程，但不保证能确定地拒绝不属于语言的输入。补运算则是指对于一个语言，其补集语言包含所有不在原语言中的元素。 通用语言是递归可枚举但不递归的语言，它们能够模拟所有其他递归可枚举的图灵机。通过图灵机的编码，我们可以将一个图灵机视为一个输入串，从而构建出一个通用图灵机，它可以模拟任何其他图灵机的行为。 文档还讨论了图灵机与输入串的二进制编码。为了便于讨论，作者做出了一些简化假设，如输入字母表仅包含0和1，有限状态集合，带符号和移动方向等。图灵机的编码方式是将所有的转移规则转化为0和1的序列，然后这些序列组合成机器的编码。同时，输入字符串也被编码为1前缀后的0和1序列。 此外，文档还涉及到了问题的归约，这是一种证明问题难度的方法，通过将一个问题转换为另一个已知难度的问题来判断原问题的复杂性。Post对应问题是一个典型的例子，它涉及到判断一个图灵机是否至少有一个接受路径。如果一个问题不能被确定性图灵机解决，那么它被称为不可判定的。 在计算理论中，P问题和NP问题是非常重要的分类。P问题是指能在多项式时间内解决的问题，而NP问题是指能在多项式时间内验证解正确性的非确定性问题。NP-完全问题是一类特别困难的问题，它们不仅是NP问题，而且所有NP问题都可以归约为它们。NP-难问题是指至少与最难的NP问题一样难的问题。 最后，文档提到了与图灵机相关的判定问题，这些问题探讨了是否存在一种图灵机能够在有限步内确定任意图灵机在任意输入上的行为。 这篇文档是计算理论的入门介绍，涵盖了对角语言、通用语言、图灵机编码、问题归约以及P、NP和图灵机判定问题等核心概念，对于理解和研究计算复杂性理论有着基础性的指导意义。