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

• 作者: 杜立智 符海东 陈和平
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 康托尔 对角线 停机问题 图灵 不可解问题
• 年，卷（期）: 2016,（12）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 64-68
• 页数: 5页
• 分类号: TP31
• 字数: 7351字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2016.12.014

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈和平	武汉科技大学计算机科学与技术学院	105	1251	17.0	31.0
2	符海东	武汉科技大学计算机科学与技术学院	35	199	7.0	12.0
3	杜立智	武汉科技大学计算机科学与技术学院	21	73	4.0	7.0