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