计算机

计算机可以理解为提供计算能力的机器，那么计算机科学就是关于这台机器运行的科学。

尽管在有些人眼里计算机科学就是在人类自己设计里兜圈子，不能算科学。这样的说法我个人觉得有些偏激，一来科学的定义本来就含糊，是个非常大的词汇，在不同情况下有不同的语义是非常正常的；二来计算机世界好歹能够提供可验证的结果（即输出）。

谈到输出，我想补充的是除了1和0（true or false)我们还有第三种可能性即null  这也是很多语言和代码中经常范的错误——没有匹配好null的情况。

由于计算机的集成度很高，单从物理方向去脑补计算机科学是不现实的，我们不可能搞清楚所有的细节。从计算理论的角度去解释它会是一种非常有益的补充。

另外我们不能把计算能力仅视作一个独立的单位，由于信息共享的需要，网络也是需要掌握的；此外，还有作为计算结果持久化的存储。

要制造拥有计算能力的机器，最基本的要求是信息传递——即输出=输入。最容易识别的信号就是发生或者不发生（暂时先不考虑无的情况），无论是机械计算机还是电子电路计算机均是如此。

对于电路来说，高低压的跳动是一种最易获得的信息。通过“真假”判断我们可以构建出一系列所需要的逻辑，通过“读取”一端的电压而获取另一端的电压，这样的电路就提供了记忆功能。这还不够，因为我们不可能为每一个程序都重新制造一个新的电路，我们要实现电路的复用。

复用的基础有两点，一是计算机需要知道复用的电路是什么，二是知道什么时候复用。第一点通过“地址”来实现，第二点需要我们制造复用的触发信号。

这个过程，还需要我们设计一个存储器来存下这个地址，并且在计算机收到复用信号时去读取这个地址并执行该地址的指令。这样的存储器是一种特殊的寄存器即stack

到这一步，我们实际上已经在讨论程序了。只不过用的语言非常的低级，每一句话都是在跟处理器直接打交道，也非常容易出错。为了提高编程的效率，我们在指令之上做了一层抽象——解释器。

解释器提供了语言和语义的桥梁，使得我们可以用更加亲人的语言实现机器指令的语义。直接从这种思路出发而设计出的语言被称为冯诺依曼体系的语言，另外的“非冯”语言则是依据lambda calculus设计的，当然最终还是会解释成机器指令。

不同的语言设计以及解释器的设计并不会造成计算能力的差别。如何解释计算机的计算能力也是计算机科学的重要问题。

我们要找到计算能力的边界，最简单的方法是举出不可能的问题。

我们当然可以从机器的角度出发，一个个的去考察逻辑门，然后去发现这些逻辑组合触碰不到的地方。但这里的问题在于我们凭白增加了理解问题的复杂度，这是因为我们已经有了关于逻辑的知识，这并不是来源于计算机硬件的。我们可以直接从逻辑的角度出发去解释可计算性理论。

然而仅从逻辑的角度除非也并不轻松，最好是有完备的将逻辑进一步抽象的技术使得我们可以简洁地找到不可计算的问题。Church做了这个工作，因此我们可以利用其的lambda calculus来研究计算理论。

lambda calculus和电子电路是完全等价的，因为它们的母亲都是同一个——逻辑。lambda calculus中的递归实际上就是电子电路中的call和ret指令，有了递归我们就获得了定义函数的能力。

那么对于停机问题，我们就可以很方便的构造出一个判断自身是否停机以及一个无限循环的函数。从而引出了矛盾。

当然这只是计算理论诸多问题中的一个，还有很多问题需要继续探索。

物理学界有一个大一统问题深受大家的关注，计算机世界也有P=NP这样的“大一统”问题。

这个问题主要难在如何证明确定型计算机能够在多项式时间内解决所有非确定型计算机在多项式时间内解决的所有问题。

然而这样一个高深的问题可能并不算是一个好问题，首先非确定型计算机是我们幻想的机器；其次同样是多项式时间性能差别可以非常巨大，就算获得证明也不能提供特别的帮助。或许研究一个特定问题，而不是“所有”对于我们的会更有意义。