可计算性

可计算性关注是否存在按明确步骤进行的方法，而不是当前机器是否已经够快。对一个判定问题，方法需要处理允许范围内的每种输入，并在要求的情形下给出答案。展示一部分实例可以解决，不足以证明存在能够处理所有实例的一般程序。

参考：[1]

图灵机、λ演算和递归函数等模型把“按步骤计算”变成可以严格研究的对象。经典模型之间的等价性提供了有力依据，使研究不必依赖某一种物理机器。丘奇—图灵论题将这种形式能力与非形式的有效方法联系起来，但不能简单写成一个已经涵盖一切物理过程的数学定理。

参考：[2]

有些程序能在答案为是时找到证据并停止，但答案为否时可能一直寻找。这种识别能力不同于总能在有限时间内回答是或否的判定能力。区分两者，才能准确说明一个方法究竟解决了什么，避免把“不断试直到发现结果”当作对所有输入都完整有效的决策过程。

参考：[1]

可计算并不保证适合实际使用。一个算法可能耗费随输入快速增长的时间，或需要无法提供的内存；这些属于复杂度与实现问题。另一方面，不可计算性也不是暂时缺少更好硬件，而是在指定模型和问题范围内不存在所要求的一般方法。两种边界需要用不同理由说明。

参考：[2]