可计算性与复杂性/简介

本书旨在作为理论计算机科学中可计算性和复杂性主题的指南，面向中级本科生。它假设读者对离散数学有一定的了解，并使用 Perl 作为所有示例程序的语言。

迄今为止，工作重点是形式语言，特别是乔姆斯基层次结构，以及与该层次结构相对应的机器。需要补充的主要领域是可归约性部分，以及时间和空间复杂性部分。在乔姆斯基层次结构之外添加更多语言类别也会改进形式语言部分，并且在正则语言和上下文无关语言部分添加关于泵浦引理的信息也会改进这些部分。