【信息科学与工程学】计算机科学与自动化——第五十七篇 计算性与不可计算性01
编号 | 类型 | 领域 | 问题 | 问题的数学分析 | 关联知识 |
|---|---|---|---|---|---|
1 | 不可计算性 | 计算理论 | 停机问题：判断任意图灵机在给定输入上是否会终止 | 采用对角线法构造矛盾：假设存在通用停机判定器 H，则构造新图灵机 D 利用 H 判定自身并做相反操作，导致悖论，故不存在这样的算法。 | 图灵机、对角线论证、递归不可判定性、归约 |
2 | 不可计算性 | 组合数学 / 计算理论 | 波斯特对应问题（PCP）：给定一组多米诺骨牌，能否通过拼接使上下字符串相等 | 将停机问题归约到 PCP，证明 PCP 不可判定。具体构造编码图灵机计算过程的骨牌序列，使得存在匹配当且仅当图灵机停机。 | 归约、不可判定性、图灵机模拟 |
3 | < |