计算机科学导论第十七章计算理论

计算理论是计算机科学的一个重要分支，它主要研究计算的本质、计算的界限、计算的复杂性等问题。计算理论的核心是图灵机模型，该模型可以模拟所有可计算问题的计算过程。

在计算理论中，有一个重要的概念叫做可计算性。一个问题能够被计算机解决，当且仅当它是可计算的。可计算性理论主要研究哪些问题是可计算的，哪些问题是不可计算的。

在计算理论中，还有一个重要的概念叫做复杂性。复杂性理论主要研究计算问题的难度，即问题的计算复杂度。其中，最著名的复杂性类别是P和NP。P类问题是指可以在多项式时间内解决的问题，而NP类问题是指可以在多项式时间内验证解的问题。目前，P和NP问题的关系仍然是计算理论中的一个重要研究方向。

总之，计算理论是计算机科学中的一个重要分支，它研究计算的本质、界限和复杂性等问题，对计算机科学的发展和应用有着重要的意义。