如果我对我的书《图灵注释：艾伦·图灵关于可计算性和图灵机的历史性论文导读》有一个希望，那就是帮助读者理解图灵的原始图灵机与大学课程和教科书中常见的图灵机之间的区别。
在图灵发表介绍其计算机器的论文二十年后，斯蒂芬·克莱恩（Stephen Kleene）在《元数学导论》（1952 年）和马丁·戴维斯（Martin Davis）在《可计算性和不可解性》（1958 年）中重新表述了图灵机。这些重新表述的机器（通常用于计算函数）在当前关于可计算性的文献中占主导地位。“停机问题”（马丁·戴维斯提出的术语）涉及一种通用算法的存在，该算法用于确定任意机器是否正确完成并停机，或者它是否出现故障并永远运行。
正如我之前提到的（2006-08-11、2007-11-26、2007-12-02、2008-05-12），将停机问题与图灵的原创工作联系起来是不正确的。图灵的图灵机应该永远运行。
图灵的论文描述了一些计算函数的机器，但这些只是特殊情况。最初的概念是一台计算无限位数的实数的机器。当然，这不是典型的计算机活动（除非你是那些让计算机计算π无限位数的人之一），但它肯定是一个算法工作的很好的例子。
图灵方法的优势在于某些理论结果几乎可以立即获得。一旦你看到图灵机（以及任何有限算法）如何用一个整数来描述，就会发现图灵机是可枚举的。由于实数不可枚举，因此绝大多数实数无法通过算法计算（如果您对可枚举性的概念不太了解，这是《图灵注释》第 2 章的重点）因此，数字计算机的功能本质上是有限的。
如果只能计算实数的子集，那么所有其他无法计算的实数是什么？绝大多数实数基本上是没有任何模式的随机数字串，您根本无法通过算法生成随机数字。
乔治·康托 (Georg Cantor) 以两种截然不同的方式证明了实数的不可枚举性（尽管两者都是归谬法证明），康托的第二个证明涉及著名的对角化过程。 （再次，请参阅《图灵注释》第 2 章以了解完整讨论）如果您可以列出实数，则可以根据此列表中数字的对角线得出一个新数字，但每个数字相差 1。这肯定是一个实数，但它不在列表中，结论是您真的无法列出实数。
如果将可计算数置于康托的对角线化过程中，您会得到什么？您正在定义一种算法来从所有其他可计算数字中计算对角线，因此对角线必须是可计算数字。但是，如果它是可计算数，则它不在列表中，这意味着可计算数是不可枚举的，而我们已经知道事实并非如此。
摆脱这个看似悖论的唯一可能方法是得出一个不可避免的结论，即您实际上无法构造可计算数的对角线。你无法构建它，因为你无法确定哪些图灵机可以计算数，哪些图灵机“堵塞”或陷入不良循环。此外，没有通用的过程来确定特定机器是否会打印特定数字。
原文：
Turing Machines That Run Forever
If I have one hope for my book, The Annotated Turing: A Guided Tour through Alan Turing's Historic Paper on Computability and the Turing Machine, it is to help readers understand the difference between Turing's original Turing Machine, and the Turing Machine as it's commonly encountered in college courses and textbooks.
Two decades after Turing's paper that introduced his computing machines, the Turing Machine was reformulated by Stephen Kleene in Introduction to Metamathematics (1952) and Martin Davis in Computability and Unsolvability (1958). These reformulated machines — which generally compute functions — dominate the current literature on computability. The "halting problem" (the term is Martin Davis's) involves the existence of a general algorithm to determine whether an arbitrary machine finishes properly and halts, or whether it goes bad and runs forever.
As I've mentioned before ( 2006-08-11, 2007-11-26, 2007-12-02, 2008-05-12), it is not correct to associate the halting problem with Turing's original work. Turing's Turing Machines are supposed to run forever.
Turing's paper describes some machines that compute functions, but these are only special cases. The original conception is a machine that computes the infinite digits of a real number. Of course, this is not typical computer activity (unless you're one of those people who set computers going calculating the infinite digits of π) but it's certainly a good example of an algorithm at work.
The advantage of Turing's approach is that certain theoretical results are available almost immediately. Once you see how a Turing Machine (and hence, any finite algorithm) can be described by a single integer, it becomes obvious that Turing Machines are enumerable. Since real numbers are not enumerable, it follows that the vast majority of real numbers cannot be computed algorithmically. (If you're hazy on the concept of enumerability, that's the focus of Chapter 2 of The Annotated Turing.) Digital computers are thus intrinsically limited in what they can do.
If only a subset of the real numbers can be computed, what are all those other real numbers that can't be computed? The vast majority of real numbers are basically strings of random digits without any pattern whatsoever. You simply can't generate random digits algorithmically.
Georg Cantor proved the non-enumerability of real numbers in two very different ways (although both were reductio ad absurdum proofs). The second of Cantor's proof involves the famous diagonalization process. (Again, see Chapter 2 of The Annotated Turing for a full discussion.) If you can list the real numbers, you can derive a new number based on the diagonal of the numbers in this list, but which differs by 1 in each digit. This must be a real number but it's not in the list. The conclusion is that you really can't list the reals.
If you subject the computable numbers to Cantor's diagonalization process, what do you get? You're defining an algorithm to compute the diagonal from all the other computable numbers, so the diagonal must be a computable number. However, if it is a computable number, then it's not in the list, which means that computable numbers are not enumerable, and we already know that's not so.
The only possible way out of this seeming paradox is the inescapable conclusion that you actually can't construct a diagonal of the computable numbers. You can't construct it because you can't determine which Turing Machines compute numbers, and which get "jammed up" or stuck in undesirable loops. It also follows that there is no general process to determine whether a particular machine ever prints a particular digit, or a particular pattern of digits.
This is yet another limitation of digital computers. To determine what a Turing Machine (or algorithm) ultimately does, you essentially need to trace through the steps — in effect, to simulate the machine.
The indeterminacy of Turing Machines is a combination of bad news and good news: It means we can't write a generalized "debugging" program that can analyze code and reveal all the bugs that hide inside. Extensive testing of software is still required, and even then we can't ever be fully confident that all the bugs have been eliminated.
But imagine if there did exist a finite algorithm that could determine the ultimate fate of Turing Machines. What would that imply about models of the human mind that are based on Turing Machines? Or cosmologies that visualize the universe as a giant Turing Machine? The nasty hobgoblin of determinism is not exactly eliminated by the indeterminacy of Turing Machines, but it's almost rendered impotent.
There is no algorithmic process to determine the future — whether it's the future of a computer program, a thought process of the human mind, or the universe as a whole.
转载本文请联系原作者获取授权，同时请注明本文来自柳渝科学网博客。
链接地址：https://wap.sciencenet.cn/blog-2322490-1460895.html?mobile=1
收藏
