图灵的停机问题及其对角线证法研究

Research on Turing's Halting Problem and Diagonal Method

停机问题是计算机科学领域的最经典问题之一,被认为是不可解的。证明停机问题不可解的方法主要包括对角线法和判定程序法,其中对角线是康托尔对角线法的延伸。通过对康托尔对角线法、图灵关于停机问题不可解的对角线证法以及判定程序证法的深入分析,揭示了判定程序证明的本质,指出了在不影响判定程序设计初衷(即拥有对所有其他程序是否停机的判定功能)的前提下,该证明否定不了这样的判定程序存在性。同时揭示了对角线证明方法的根本缺陷和谬误。

Halting problem is one of the most classical ones in computer science, which has been considered unreseluable. The methods of testifieation on the unresolvability of halting problem are composed of diagonal proof and that of program, in which the former is a stretch of canter＇ s diagonal method. By deep study on Cantor＇ s diagonal method, Turing＇ s unresolvable proofs of the halting problem, and both the program proof and the diagonal proof,the essence of the program proof is revealed. It is pointed out that without loss of its original function, the judge program may exist. In addition, the essential deficiency and fauh of the diagonal method, both Cantor＇ s and ＇Fating＇s,is revealed.