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