皇帝新脑-第16章

按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！



　　正如许多其他的数学观念，尤其是更美丽的、更基本的那些，可计算性的观念似乎自身具有某种柏拉图的实在性。在下面两章，我们应该探讨的正是数学概念的柏拉图实在性的这个神秘问题。

　　注　释1．我是采用当代通常的术语，它现在把零包括在“自然数”之中。

　　2．还有许多把一对、三个等等数编码成单独一个数的其他方法。虽然它们对于我们现在的目的不甚方便，数学家却熟知这些方法。例如，公式　便是用一个单独的自然数来代表一对自然数　。　12（（a　＋　b）　＋　3a　＋　b）　（a；　b）

　　2试试看！3．我在上面没花工夫去引进某种表示起始一个数（或指令等等）的序列的记号。这对于输入没有必要，由于当遭遇到第一个1时事情刚刚开始。然而，对于输出需要某些其他东西，这是由于人们预先为了达到第一个（也就是最左边的）1不知道要沿着输出磁带看多远。尽管在往左看时会遇到0的很长的串，这并不能保证在左边更远处不再有1。人们对此可采用不同的观点。其中一种总是用特殊记号（譬如，在收缩步骤中用6来编码）去启始整个输出。但是为了简单起见，我在自己的描述中将采用不同的观点，也就是总“知道”仪器实际上已遭遇到了多长的“磁带”（例如，人们可以想象，它留下了某种痕迹），在原则上不必去检查无限长的磁带，就能肯定整个输出已被查过。4．一种把两盘磁带的信息编码到单独一盘磁带上的方法是插入法。这样，这盘单独磁带上的奇数号码的记号可代表第一盘磁带的记号，而偶数号码的记号可代表第二盘磁带的记号。可用类似的方案来处理三盘或更多盘磁带。这一过程的“低效率”起因于如下事实，即阅读机必须沿着磁带不断地来回进退，并在上面留下记号以记住在该磁带偶数和奇数部分的什么地方。5．这一过程只是指作过记号的磁带可解释作自然数的方法而言。它并不改变我们特定的图灵机的编号譬如EUC或XN＋1。6．如果Tn/没有被正确地指定，则　U只要在n的二进位表示中到达多于四个1的第一串，就会像n的数已被终止那样进行下去。它就会把该表示式的余下部分当成m的磁带的部分来读，所以它会继续进行某种毫无意义的计算！如果需要的话，可采用扩展二进位记号来表示n，这种特征就能被清除。我决定不这样做，以免使这台可怜的普适机器U更加复杂！

　　7．我感谢大卫？德义奇根据以下我得到的u的二进位形式推导出十进位形式。我还感谢他检验u的这个二进位值实际上的确给出了一台普适图灵机！事实上u的二进位值为：

　　1000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l10011101010100100101011101010100110100010100010101101001000000001011101001101000100101010110100011010001010000011010100110100010101001011010000110100010100101011010010011101001010010010111010l100111010101001001010111010101001101000101000