10.3969/j.issn.1673-629X.2016.12.014
图灵的停机问题及其对角线证法研究
停机问题是计算机科学领域的最经典问题之一,被认为是不可解的。证明停机问题不可解的方法主要包括对角线法和判定程序法,其中对角线是康托尔对角线法的延伸。通过对康托尔对角线法、图灵关于停机问题不可解的对角线证法以及判定程序证法的深入分析,揭示了判定程序证明的本质,指出了在不影响判定程序设计初衷(即拥有对所有其他程序是否停机的判定功能)的前提下,该证明否定不了这样的判定程序存在性。同时揭示了对角线证明方法的根本缺陷和谬误。
康托尔、对角线、停机问题、图灵、不可解问题
26
TP31(计算技术、计算机技术)
2014年湖北省自然科学基金项目2014CFC1121
2017-01-11(万方平台首次上网日期,不代表论文的发表时间)
共5页
64-68