图灵的秘密 - 书评

无敌北

　　这本书对我来说真的很难读懂。看到大段大段的各种稀奇古怪的数学符号我就发求。但是这并不妨碍我从另一个角度来重新了解了图灵、数学、计算机….去年的时候曾听过Jeff讲过的一个session:《世界及宇宙的终极答案》。我敢确定至少一半的内容都是来自这本书。
　　图灵在论文中描述了一个想象出来的机器，用来论证数理逻辑中的一个问题，论文题目叫:<论可计算数及其在判定性问题中的应用>（On Computable Numbers, with an Application to the Entscheidungsproblem）。这个想象出来的机器被后人成为图灵机。
　　
　　
　　图灵在论文中让图灵机使用二进制，仅是觉得方便论证。后来研制的计算机有的使用十进制，有的使用二进制，直到冯诺依曼发表了一片论文论述了计算机使用二进制的可行性与优势后，二进制逐渐成为标准。
　　
　　如果一个集合可以与自然数意义对应起来，那么我们可以说这个集合是可数的。
　　正整数和偶数个数那个多些？答案是一样多。因为他们都是可数的。
　　那么有理数和无理数那个多？答案是无理数。因为无理数是不可数的。
　　
　　无理数属于实数的一部分。所以实数也是不可数的。这可以用对角线法来证明。
　　这是一个反证法。
　　我们假设实数是可数的。那么将0和1之间所有的实数都按照从小到大的顺序列出来。然后我们取第一个数的第一位、第二个数的第二位、第三个数的第三位…..即取对角线的数组成一个新的数。然后对这个数的每一位都加1,如果该位的值是9再加1后变成0。我们看看这个数是不是在已经枚举出来的列表中。列表中的第一个不是它，因为它比第一个数的第一位大1，第二个数也不是它，因为它比第二个数的第二位大…….这样遍历了整个列表发现这个新的数并不在列表中，也就是说我们根本无法将0和1之间的所有实数列举出来，因为我们总可以通过这个方法来找到一个新的实数。
　　
　　实数是无穷的。我们可以这样理解，世界上有数不清的数字，我们恰好找到了一些，并给它们起了一些名字，如整数，实数，有理数，但还有更多的数我们并不知道它们的存在，就算发现一个也算是意外。
　　
　　
　　一个图灵机无法通过程序判断另一个图灵机在限定的时间内停机。停机问题说明了图灵机的局限性，这也被很多人作为程序无法没有bug的借口。你无法写一个程序，来判断一段程序中是否没有任何bug。
　　
　　我们可以预知未来吗？根据图灵机理论，如果我们可以用确定的不含糊的步骤来描述出宇宙的发展，那么我们就可以将其作为输入到图灵机，得到未来。问题是我们如果要构造这个输入，差不多等于构造了一个新宇宙。