丘奇-图灵论题

丘奇-图灵论题断言”图灵可计算的函数”和”可计算的函数”其实是同一回事——换句话说，图灵机这台极简的抽象机器已经囊括了任何算法系统所能拥有的全部计算能力，没有任何计算模型能算出图灵机算不出的东西。这个断言严格来说是一个无法被数学证明的猜想（因为”可计算”这个直观概念本身没有独立于图灵机之外的形式化定义），但几十年来收集到的大量支持证据，已经让它被计算机科学界广泛接受为事实。发散：这个论题的实际意义在于，它把图灵机的能力树立成了评判任何计算系统的统一标杆——只要能证明某个系统（一门程序设计语言、一台设计中的机器）能模拟图灵机，就可以确信它具备了”通用计算”的完整能力，这也是[[通用程序设计语言与 Bare Bones 揭示的语言核心]]之所以成立的理论基础：只要证明一门极简语言能模拟图灵机，丘奇-图灵论题就保证了它能表达任何可计算函数的算法。