停机问题的不可解性及基于归约法的相关问题不可解性证明

• 作者: 周旻 周理凤 黄水源
• 来源期刊: 计算机与现代化
• 学科: 工学
• 关键词: 可计算性 不可数性 停机问题 归约法 不可解性证明
• 年，卷（期）: 2006,（5）
• 页码范围: 18-20,24
• 页数: 4页
• 分类号: TP301
• 字数: 3627字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-2475.2006.05.006

摘要

可计算性理论是当今计算机科学中研究的热点和难点问题之一.本文先介绍了不可数性和停机问题等重要概念,用反证法证明了停机问题是不可解的,并使用归约法对计算机中的相关问题的不可解性进行了证明.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄水源	南昌大学计算中心	26	128	7.0	10.0
2	周理凤	南昌大学计算中心	4	8	2.0	2.0
3	周旻	南昌大学计算中心	1	1	1.0	1.0