主页

之前的讲述都不过是热身，到了这一章，计算理论才显现出真正的威力。

前一篇描述了正则语言的描述方法，但是他并不能描述所有语言，比如01等的情况。 本章介绍一种能力更强的描述数学语言的模型，称为上下文无关文法。它能够描述某些应用广泛的具有递归结构特征的语言。

指针问题的核心就是认识到：指针的地址和指针的内容是两码事。它们同时归属于一个对象，却有着完全不同内涵。只要深刻把握了这一点，小心考察每一个已使用指针。犯错的可能性就会大幅度降低。

本课程为理论计算机科学基础，比起计算机，更像是一门数学课。主要讨论什么是计算。

假定我们定义了计算，那么计算问题可以分成两类。一类是能算的，一类是不能算的。我们会学到一些判断方法。

对于能算的问题，也可以分成容易算的和难计算问题。比如RSA密码学就是利用了一个幂次模方程双向求解的难易度不同设计的。容易计算的问题，对其的计算称为有效计算。如何区别这两类问题，也是本课程的一部分。

1. 无穷多的素数

让我们列出一些常见的素数：

首先我们可以发现：

当然，更重要的事实是在最后的省略号。

我们有无穷多个素数吗？