在计算理论中，丘奇-图灵论题是什么？

丘奇-图灵论题指出，每个可解的判定问题都可以转化为一个等价的图灵机问题。

它可以用以下两种方式解释：

  • 判定问题的丘奇-图灵论题。

  • 判定问题的扩展丘奇-图灵论题。

让我们来了解这两种方式。

判定问题的丘奇-图灵论题

如果且仅当存在一个对于所有输入字符串都停止并解决问题的图灵机时，才存在某种有效的程序来解决任何判定问题。

判定问题的扩展丘奇-图灵论题

如果且仅当存在一个精确接受 Q 中答案为“是”的元素的图灵机时，则称判定问题 Q 是部分可解的。

证明

丘奇-图灵论题的证明是一种在建立判定算法的存在性时经常采用的捷径。

对于任何判定问题，与其构建一个图灵机解决方案，不如让我们描述一个解决该问题的有效程序。

丘奇-图灵论题说明，一个判定问题 Q 有解当且仅当存在一个图灵机可以确定每个 q ϵ Q 的答案。如果不存在这样的图灵机，则称该问题是不可判定的。

更新于： 2021年6月12日

26K+ 浏览量

开启你的职业生涯

通过完成课程获得认证

开始学习
广告