这次课我们讨论一个
很重要但又容易被忽视的问题：计算机为什么能够进行计算？
好像这个问题看上去非常非常的基础，但是很多同学好像
不怎么去考虑这个问题。计算机为什么能算数？
它是一个电路，是一个机器。它有智能吗？为什么它能够进行计算？
那我们今天来讨论一下，关于这个问题的讨论呢我想应该分成以下几步
首先我们来看，既然是算数，那么数在计算机中是如何表示的
如果一个数不能很好的被计算机接受并且存储下来，那么它就无法进行计算
第二步，在逻辑上，对于数
计算机是如何进行计算的？是按照四则运算的法则进行计算吗？
还是怎样，有什么其他的方式，这是第二个
第三个，在物理上，这个计算是如何实现的
我想我们想探讨这三个问题，那我们先来看第一个问题：数在计算机中是如何来表示的？
其实关于这个问题的讨论我们已经在图灵机的那部分已经涉及到了
在图灵机的章节里头我举过一个例子
我们用空白和数字1填满存储袋
当时我们算了一个加法叫4+3最后结果是7，7个1
来表示的，那这也是一种表示方式
而且这种表示方式非常非常的简便，可以说真的是简便到家了
那么这种方式，可不可以采纳呢？在计算机里？当然是可以的
从理论上讲。但是它有一个问题。我算的是4+3=7，这个还好办，我移动4次或者移动3次
我就可以把4或3读入进来，但是如果我算的是
1999+2001，这个移动的次数可能就非常多了
也就是说，随着数量的增大，图灵机为了读取这个数字
所要移动和读取的次数就非常非常的多
这显然是不合理的 也是不实际的。那么有的同学说了，
造成你这个问题的原因非常简单 采用了太少的符号来表示数了
那如果我用十进制来表示，那这个问题就简单得多了。比方说1999+2001
用十进制表示的话，我最多只需读取8位我就可以把数读取进来了
随着字母表中符号的个数的增加，符号的表达能力也越来越强，所以你需要读取的字符数也会越来越少
但是又出现了另外一个问题
比方说仅有1和空格的图灵机里
为了表达某一个状态和某个输入字符之间的条件关系，我只需要一个或者两个
顶多两个语句我就可以覆盖所有的情况
但是如果在十进制的程序里，我就要给每一个字符增加一个状态描述
当前状态Q1，逢0的时候怎样，逢1的时候怎样，逢2的时候怎样
一下子增大了，程序语句的增加直接意味着
每次图灵机在确定程序语句的时候，它的搜索空间也变大了
搜索次数也上去了，这个代价也非常非常昂贵，所以由此可知
字母表中的符号越多，读入的移动次数就会越少，但是程序量就会越多
符号越少，程序量会减少，但是读入的移动次数就会越来越多
太多也不行，太少也不行，那怎么办呢，经过计算，有人提出
说最优的数量可能是欧拉常数，2.71828
这个数取整以后是3，与具有2个状态的电子元器件相比
想制造具有3个状态的电子元器件
从工艺上讲更困难，所以人们希望能使用2个状态在字母表上来表达状态
直接的一个结论就是我们要采用二进制
在这我们对比十进制来专门说一下二进制，十进制我们大家都很习惯了
它的计数符号有10个，0、1、2、3、4、5、6、7、8、9，它的基数是10也就是说逢10进1
那么二进制也一样，二进制的计数符号只有2个，0和1
它的基数是2，也就是说，对于任何一个二进制数，跟上面的式子相同
我们怎样去计算这个二进制数的大小呢？
比方说对于10110这个数，0乘以2的0次幂 1乘以2的1次幂
1乘以2的2次幂，0乘以2的3次幂，最后1乘以2的4次幂
这样加起来，就把这样的一个二进制数转换成了十进制数
在这我们也提一下十六进制，十六进制计数符号
有十六个，从0到F
超过10之后，因为没有相应的阿拉伯数字来表示，我们就用字母A\B\C\D\E\F
分别代表10、11、12、13、14、15
这是十六进制数，那么基数是16，也就是说当我们把一个
十六进制的数，比方说ABCD转换成十进制数的话那怎么算呢？
D乘以16的0次幂，C乘以16的1次幂
B乘以16的2次幂，最后A乘以16的3次幂，通过这种方式
我们就把十六进制的数对应的十进制数计算出来了
那当我有一个十进制的数，因为我们平常用十进制的数还是最多的
怎么把它转换成二进制数呢？在这我们给出一个最通用的办法，就是除二取余
比方说对于一个十进制数123, 我要求它的二进制数，这个计算过程是这样的
123除2得61，余1
把余数写在这里，结果写在这里，商写在这里
61再除以2，商写在这里，余数写在这里
30除以2得15余0，15除以2得7余1 7除以2得3余1
3除以2得1余1，在这我要特别提示大家一定要把商除到0
才可以算计算完毕，所以说1再除以2得0余1
我们见到0以后，这个计算就可以完毕了
我们就得到了这样一个序列 这个序列从下往上反着把它写出来
就是123所对应的二进制数，从下往上去写的话就是1111011
也就是说对应的二进制数就是1111011
在这我特别想提示大家的就是一定要除到0
我把这一点称作一定要触底反弹
不触底不要反弹，我们有些同学炒股票可能就知道了
一定要触底再反弹，除到0，这样便于大家记忆
除了二进制之外，我们还有一种进制
也是常用的，叫做八进制，连同刚才我们所介绍过的十六进制
八进制就是逢八进一，从二进制到八进制 有一种非常简便的转换方法
比方说对一个二进制数1111011，就是刚才我们算的这个二进制数
我们想把它转换成一个八进制的数，注意这个表示，当你想表示一个数是二进制数的话
你可以这样来表示，在这个数的末尾加一个小括号然后写一个2
如果你想表示某个数是八进制的数的话，在这个数的末尾加一个小括号
右下角，然后写一个8 怎么从这个二进制的数得到八进制的数呢？
有一个非常简便的方法 就是从这个数的最右端开始向左，每三位截取一段
把这个截取下来的数字转换成相应的八进制数
就OK了，比方说011对应着3，我就把3写在这里
再数3位，111，对应的八进制数是7
把7写在这，再数三位，数不了三位了，只有一位了，一位把它写在这
那么就是173，这就是对应的八进制数
同理，我们可以把一个二进制数转换成一个十六进制数
转换成十六进制数的话我们不能数3位了，我们就要数4位 1011，所对应的
十六进制数应该是11
所以我们在这写B，剩下的111，三位
对应的是7，所以说我们最后答案写出来是7B，十六进制对应的数
说到这呢，我们已经解决的问题，我们归结一下
已解的问题是说：数的表示，在计算机里头
我们知道了我们是倾向于二进制数，这样表示比较便捷，而且比较符合我们现在的工艺水平
那未来的计算机可能不采用这种技术方法，我们在下一节课会讨论
待解的问题，接下来，已经解决的问题是说我们会采用二进制
接下来的问题就是，如果我们采用二进制数来表示数
那么对二进制的数应该怎么去计算？
是不是也用十进制数所用的那种四则运算法则去计算呢？还是有什么其他的办法
Ge Li 李戈, Ph.D.Associate Professor
