操作系统基础 计算是什么

第三次科技革命的能源是一种数字能量，本质是计算

计算能量

电能供给给芯片，芯片中的一种电子元件晶振（也就是石英晶体）通电后产生震荡，震荡会产生频率稳定的脉冲信号。通常这是一种高频的脉冲信号，每秒可达百万次。然后，通过谐振效应发放这个信号，形成方波。再通过电子元件调整这种脉冲的频率，把脉冲信号转换为需要的频率，这就形成了驱动芯片工作的时钟信号。这种信号的频率，也称作芯片的时钟频率。最后，时钟信号驱动着芯片工作，就像人体的脉搏一样，每一次脉冲到来，都让芯片的状态发生一次变化，用这种方法，最终存储器中的指令被一行行执行。指令被执行，其实就是数据被计算，这就是计算能量

公理化体系和不完备性定理

最早在 19 世纪初，德国著名数学家希尔伯特提出：这个世界可以建立一套完善的公理体系，由少数几个公理出发，推导出所有的定理和推论。这样就可以逐渐通过这种方法将世界上的万事万物都统一到一个体系中

当然，这只是一个非常美好的设想，如果万事万物都可以用形式化（简单理解就是程序化规范化）的手段统一到一套体系中，也就意味着计算能力将被无限扩展，只要给定足够的时间和空间，计算机就可以完成任何工作

但在不久后，美籍数学家哥德尔就提出了哥德尔不完备性定理，内容是：即便在完善的公理体系中仍然可以找到不能被证明也不能被证伪的命题

计算机能力也是有边界的。哥德尔的不完备性定理，让大家看到了世界上还有大量不可计算的问题

图灵机和可计算理论

哪些问题可以被计算，哪些不可以被计算，这就是可计算性理论，该理论是计算机科学的理论基础之一

图灵发现如果一个问题是可计算的，那么它的解决方案就必须可以被具化成一条条的指令，也就是可以使用图灵机处理。因此，不能使用图灵机处理的问题，都是不可计算的问题

不可计算问题

但当图灵机遇到 “素数是不是有无穷多个?” 这样的问题时，事情就变得复杂了。虽然，可以通过有限的步骤计算出下一个素数。比如可以每次尝试一个更大的数字，然后通过一系列计算过程判断该数字是不是素数，直到找到一个更大的素数。古希腊数学家埃拉托斯特尼就发明了筛选出给定范围内所有素数的方法

利用埃拉托斯特尼筛法找到的素数越来越多。但是，还是不能回答 “素数是不是有无穷多个” 这样的问题。因为要回答这样的问题，会不停地寻找下一个素数。如果素数是无穷的，那么计算就是无穷无尽的，所以这样的问题不可计算

停机问题

运行这段程序来检查一个程序是否会停止时，会发现不能因为这个程序执行了 1 天，就判定它不会停止，也不能因为这个程序执行了 10 年，从而得出它不会停止的结论

这个问题放到图灵机领域，叫作停机问题，无法给出一个判断图灵机是否会停机的通用方法，因此停机问题是一个经典的不可计算问题

计算能力的边界在哪里

世界上想解决的事情都称作问题，解决问题往往需要消耗芯片的计算能力，这通常称作时间开销，另外解决问题还需要消耗内存，称作空间开销

问题的分类

世界上有一类问题，无论消耗多少时间和空间也无法解决，这类问题就包括 “停机问题”，称作不可计算问题，无法用计算机精确地解决这类问题

世界上不可计算问题多，还是可计算问题多，也是一个不可计算问题，但直觉一定是不可计算问题更多

在可计算的问题中，有困难问题，也有简单问题，通常用复杂度来衡量，比如：

• “求数组第 10 个元素”，计算这种问题，时间开销、空间开销都不会随着问题规模增长，记为 O(1)；
• “求数组中的最大值”，计算这种问题，时间开销会随着数组规模线性增大，记作 O(N)，N 是问题的规模；
• “求一个n*n矩阵的和”，如果n是规模，那么时间开销会随着问题规模的平方增长，称作 O(N2)；
• 也有更加复杂的数学模型，比如说O(N3)、O(N4)、O(N100)等

P & NP 问题

有能力解决的问题，统称为多项式时间（ Polynomial time）问题。今天能解决的问题，都是多项式时间的问题，下面记为 P 类型的问题

还有一类问题复杂度本身也是指数形式的问题，比如 O(2N)的问题。这类型的问题随着规模 N 上升，时间开销的增长速度和人类计算能力增长速度持平甚至更快。因此虽然这类问题可以计算，但是当 N 较大时，因为计算能力不足，最终结果依然无法被解决

由此可见，不是所有可以计算的问题都可以被解决，问题如果不能在多项式时间内找到答案，记为 NP 问题

有一部分 NP 问题可以被转化为 P 问题，比如斐波那契数列求第 N 项，可以用缓存、动态规划等方式转化为 O(N) 的问题。但还有更多的 NP 问题，比如一个集合，找出和为零的子集，就没能找到一个合适的转换方法