在计算机科学中，可计算性理论（Computability theory）作为计算理论的一个分支，研究在不同的计算模型下哪些算法问题能够被解决。相对应的，计算理论的另一块主要内容，计算复杂性理论考虑一个问题怎样才能被有效的解决。可计算理论的研究对象有三个 ： ( 1) 判定问题； ( 2) 可计算函数；( 3) 计算复杂性。
可计算性理论，亦称算法理论或能行性理论，计算机科学的理论基础之一。是研究计算的一般性质的数学理论。可计算性理论通过建立计算的数学模型[2] ，精确区分哪些是可计算的，哪些是不可计算的。计算的过程是执行算法的过程。可计算性理论的重要课题之一，是将算法这一直观概念精确化。算法概念精确化的途径很多，其中之一是通过定义抽象计算机，把算法看作抽象计算机的程序。通常把那些存在算法计算其值的函数叫做可计算函数。因此，可计算函数的精确定义为：能够在抽象计算机上编出程序计算其值的函数。这样就可以讨论哪些函数是可计算的，哪些函数是不可计算的。
内容全部来源于网络收集，如有侵权，请联系网站删除！