可计算函数 在可计算性理论中可计算函数computable function或图灵可计算函数是研究的基本对象它们使我们直觉上的算法概念更加精确使用可计算函数来讨论可计算性而不提及任何具体的计算模型如图灵机或寄存器机但是它们的定义必须提及某种特殊的计算模型 在可计算函数的精确定义之前数学家经常使用非正式术语可有效计算的这个术语因此可以被认同为可计算函数尽管这些函数被叫做有效的它们可能极其困难可行可计算性和计算复杂性研究可有效计算的函数 依据邱奇图灵论题可计算函数精确的是使用给出无限数量的时间和存储空间的机器计算设备来计算的函数等价的说这个论题声称有算法的任何函数都是可计算的 可以使用布盧姆公理来在可计算函数的集合上定义抽象计算复杂性理论在计算复杂性理论中确定一个可计算函数的复杂性的问题叫做功能性问题