操作系统–前言01--计算

操作系统–前言01

可不可以计算一个人程序写得好不好？

"计算"可以涉及到计算机本源的有趣的知识,比如图灵机、冯诺依曼模型；再比如说 CPU 的构成、程序如何执行、缓存的分级、总线的作用等。

一级目录

二级目录

三级目录

芯片：计算能源

第一次工业革命出现了蒸汽机，能源是煤炭
第二次工业革命出现了发电机，能源是电
第三次科技革命，革命产物是计算机
第四次科技革命，就发生在当下，出现了人工智能，能源是数据。

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

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

芯片普及后,应用到我们生活中大大小小的物件,有了芯片，设备通电后才可以计算，有了计算，这些设备才能够实现更加复杂而精确的功能。

摩尔定律：计算能力的发展

第一个芯片:被称作集成电路， 1958 年由美国德州仪器公司的工程师杰克·基尔比发明
第一台通用计算机:ENIAC 则是在 1946 年诞生于美国陆军弹道研究实验室。

Intel 的创始人之一摩尔就观察到了这个现象，并提出了摩尔定律：当价格不变时，集成电路中可容纳的晶体管数目约每隔 18～24 个月就会增加一倍，性能也将提升一倍。

这一定律揭示了信息技术发展的速度，但到今天，摩尔定律失效了。因为随着芯片越来越小，在尺寸和散热等方面已经挑战了人类的极限，芯片中无法再放入更多的电子元件了。

展望未来，计算能力还有更多的增长点，不仅有可以无限提高计算能力的量子计算机，还有利用光学元件替代晶体元件的光电集成电路。

可计算理论：图灵机

生活在数字时代的我们，用着导航、玩着游戏，本能地知道很多问题是可以被计算的，生活在 20 世纪初的科学家们，需要在没有计算机和芯片的时代就想清楚这些问题，并不是一件容易的事情。

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

因为世界上存在着大量的这种“公说公有理，婆说婆有理”的问题，才让大家认识到计算不能解决所有问题，所以：计算机能力也是有边界的。哥德尔的不完备性定理，让大家看到了世界上还有大量不可计算的问题。

图灵机和可计算理论

哪些问题可以被计算，哪些不可以被计算

人工智能之父的阿兰·图灵提出了图灵机:它是一种不断执行指令的抽象计算机

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

比如一个马达的控制程序是可计算的，因为控制过程是可以被抽象成一条条指令的（即可以写程序实现）

不可计算问题

当图灵机遇到“素数是不是有无穷多个"？

如果素数是无穷的，那么我们的计算就是无穷无尽的，所以这样的问题不可计算。

停机问题

我们也无法实现用一个通用程序去判断另一个程序是否会停止。比如你用运行这段程序来检查一个程序是否会停止时，你会发现不能因为这个程序执行了 1 天，就判定它不会停止，也不能因为这个程序执行了 10 年，从而得出它不会停止的结论。这个问题放到图灵机领域，叫作停机问题，我们无法给出一个判断图灵机是否会停机的通用方法，因此停机问题是一个经典的不可计算问题

计算能力的边界在哪里？

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

问题的分类

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

可计算问题 < 不可计算问题

P 问题 vs NP 问题

有能力解决的问题，统称为多项式时间（ Polynomial time）问题。今天能解决的问题，都是多项式时间的问题，下面记为 P 类型的问题
问题如果不能在多项式时间内找到答案，我们记为 NP 问题。

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

今还有很多问题无法解决，它的数量远远大于我们可以解决的问题，科学家、工程师们也只能望洋兴叹了

人工智能

包括停机问题、包括 NP 问题在内的很多问题，虽然不能解决，但可以努力让计算机的解决方案超过人类的水平，这就是人工智能。

AlphaGo 战胜李世石就是利用了基于概率的不完全解法，这种解法已经可以超过部分人类职业选手了，也就是说计算机的解法已经超过了人类。

人类的强项在于理解和分析，人有两种思维，归纳和假设，这两种思维都是计算机无法计算的。机器用概率理解围棋，局部来说机器下得更好，但是人可以制造机器，因此，人的感悟更有意义，谈不上孰优孰劣。

可不可以计算一个人程序写得好不好？

这个问题可以这样来思考，如果把问题降级，变成：“可不可以计算一个人写的程序会不会停机？”

这个问题就如同停机问题，无法计算，因此这是一个不可计算的问题。

但是我们通过

设立规则，比如

检查缩进、
检查函数的复用情况、
检查类的命名情况

操作系统–前言01--计算