可计算性

定义

可计算性理论研究的核心问题是：哪些问题原则上能够由算法机械地求解，哪些则根本无法求解。一个函数若存在算法对任意输入都能在有限步内给出正确结果，则称其为可计算函数；对应的判定问题称为可判定问题。

原理

多个独立提出的计算模型，包括图灵机、递归函数和 lambda 演算，被证明在计算能力上完全等价，这一事实支撑了丘奇图灵论题：凡是直觉上可计算的，都能由图灵机计算。借助对角线方法和归约技术，理论家证明了存在确定无法由任何算法解决的问题。

意义

停机问题是第一个被证明不可判定的问题，它表明不存在通用算法能判断任意程序是否会终止。可计算性理论揭示了计算的根本极限，提醒人们某些任务无论硬件多么强大都无法自动完成。它不仅是理论计算机科学的奠基支柱，也深刻影响了数理逻辑与哲学对机械思维边界的认识。