人脑可计算的就是计算机可计算的

英国科学家图灵的著名假设．命题中的计算机指的是理想计算机．图灵曾经设想：人和计算机在两个互相看不到的屋子里通过某种方式互相交流，如果人无法确定坐在对面与之通话的是人还是计算机，则说明这样的计算机和人脑在计算能力上是等价的．比这个命题更为广泛和精确的陈述是图灵——丘奇假设：直观上的能行可计算函数与形式定义的递归函数类等概念等价．这个假设源自本世纪三十年代以后的一系列发现，人们提出的一系列形式计算模型如递归函数、图灵机可计算函数、λ—演算等等被证明在计算能力上是等价的．于是人们认为这也刻划了直观上的能行可计算性，也就是人脑的计算能力．从图灵——丘奇假设出发，人们可以对许多判定问题作出回答．如图灵机的停机问题就是不可判定的．再有对一阶谓词演算中的公式，其是否为真也是不可判定的．这些结果只是这个假设所有的巨大应用的一部分，这也巳说明了假设的重要意义。