| 丘奇-图灵论题 Church-Turing thesis 断言不加定义的“直观可计算函数”概念与递归函数等精确概念等价的命题。递归论发展过程中，人们曾对“直观可计算”或“算法可计算”的函数作了多种形式的精确刻画，但是，由于能行可计算函数是一个直观的不严格的概念，因此，不能严格证明经精确刻画所得到的函数类恰好就是通常直观上的可计算函数类。所以在每种形式的刻画中都需要一个相应的假设命题：经本方法所精确刻画的可计算函数类恰好与直观上的可计算函数类等同。就丘奇的形式刻画来说，它可称为丘奇论题;就图灵的形式刻画来说，它可称为图灵论题;就马尔柯夫的刻画来说，它可称为马尔柯夫论题等等。现在通常把它们统称为丘奇-图灵论题。这个论题包含两方面的内容：(1)每个直观可计算的函数是经某种方式精确刻画的可计算函数。(2)每个经某种方式精确刻画的函数是直观可计算的。其中第二部分内容是可以使用归纳方法来证实的，至于第一部分的内容是不可能加以证明的，因此本质上说，丘奇-图灵论题指的是第一部分的内容。尽管由于丘奇-图灵论点本身不是一条定理，而只相当于经验科学中的一个假设，但提出这个论题是有充分根据的，因为：(1)迄今为止所提出的对直观可计算性的数学刻画，各自得到的可计算函数类都是全同的。(2)迄今人们认为直观可计算的或者在现有的大型计算机上可以计算的那些数论函数，都证明是图灵机可计算的，或都证明是一个递归(部分)函数，而还未发现一个反例。(3)迄今为止已经证明不是图灵机可计算的或不是(部分)递归的数论函数，在直观上看来确实相信是很难计算的。但也有人怀疑丘奇论题，其中最有影响的是匈牙利逻辑学家卡尔玛(L. Kalmar， 1905—1976)等。承认丘奇-图灵论题，能使许多判定问题获得否定的解答;也能用简便的方法去证明某个数论函数是图灵可计算的或递归的。 |