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