丘奇-图灵论题

来自计算思维百科
跳转至: 导航搜索

丘奇-图灵论题是可计算性理论的基本论题,也称图灵论题。它规定了直观可计算函数的精确含义。丘奇论题说:λ可定义函数类与直观可计算函数类相同。图灵论题说:图灵机可计算函数类与直观可计算函数类相同。A.Turing证明了图灵机可计算函数类与λ可定义函数类相同。这表明图灵论题和丘奇论题讲的是一回事,因此将它们统称为丘奇-图灵论题。直观可计算函数不是一个精确的数学概念,因此,丘奇-图灵论题不能加以证明。