邱奇-图灵论题 邱奇图灵论题英語ChurchTuring thesis又称邱奇图灵猜想邱奇论题邱奇猜想图灵论题是一个关于可计算性理论的假设该假设论述了关于函数特性的可有效计算的函数值用更现代的表述来说在算法上可计算的简单来说邱奇图灵论题认为任何在算法上可计算的问题同样可由图灵机计算 世纪上半叶对可计算性进行公式化表示的尝试有 美国数学家阿隆佐邱奇创建了称为λ演算的方法来定义函数 英国数学家阿兰图灵创建了可对输入进行运算的理论机器模型现在被称为通用图灵机 邱奇以及数学家斯蒂芬科尔克莱尼和逻辑学家J Barkley Rosser英语J Barkley Rosser一起定义了一类函数 这种函数的值可使用递归方法计算 这三个理论在直觉上似乎是等价的它们都定义了同一类函数因此计算机科学家和数学家们相信可计算性的精确定义已经出现邱奇图灵论题的非正式表述说如果某个算法是可行的那这个算法同样可以被图灵机以及另外两个理论所实现 虽然这三个理论被證明是等价的但是其中的前提假设能够有效计算是一个模糊的定义因此虽然这个假说已接近完全但仍然不能由公式证明