波斯特对应问题
词条百科 0
目录
波斯特应对问题
波斯特对应问题是 Emil Post 于 1946 年提出的不可判定问题。因为它比停机问题和 Entscheidungs 问题更简单，所以经常用于不可判定性的证明。
问题的定义
设 A {displaystyle A} 是一个至少有两个符号的字母表。
那么判定问题就是判定这样的解是否存在。
问题实例
不可判定性证明草图
PCP 不可判定性的最常见证明描述了一个 PCP 实例，它可以模拟任意图灵机对特定输入的计算。
内容来源于网络，本内容不代表16map.com立场，内容投诉举报请联系16map.com客服。如若转载，请注明出处：https://16map.com/wiki/nmjemiylnizk