可计算函数
维基百科，自由的百科全书
在可计算性理论中，可计算函数（computable function）或图灵可计算函数是研究的基本对象。它们使我们直觉上的算法概念更加精确，并且依据邱奇-图灵论题它们严格的是使用机器计算设备可计算的函数。函数的可计算性的概念可以相对化为任意自然数的集合 A，或等价的从自然数到自然数的任何函数 f，通过使用带有 A 或 f 的 oracle 扩展的图灵机。这种函数也可以分别叫做 A-可计算的 或 f-可计算的。在可计算函数的精确定义之前，数学家经常使用非正式术语可有效计算的。
使用可计算函数来讨论可计算性而不提及任何具体的计算模型，如图灵机或寄存器机。可以使用 Blum 公理来在可计算函数的集合上定义抽象计算复杂性理论。
依据邱奇-图灵论题，可计算函数的类等价于递归函数、lambda 演算或马尔可夫算法定义的函数类。
它们也可以被定义为能用图灵机、Post 系统或寄存器机运算的那些算法。
在计算复杂性理论中，确定一个可计算函数的复杂性的问题叫做功能性问题。
目录 |
[编辑] 定义
被称为可计算的，如果 f 的像是递归可枚举集合。带有一个参数的偏可计算函数的集合通常表示为 
，或 
如果参数的数目在上下文中是明确的。
被称为可计算的，如果 f 的像是递归集合。带有一个参数的全可计算函数的集合通常表示为 
或 
。
可计算函数 f 被称为可计算谓词，如果它是布尔值函数，就是
[编辑] 注解
有时出于清晰的原因，我们把可计算函数写为
我们轻易的使用配对函数编码 g 为新函数
[编辑] 例子
- 常函数 f : Nk→ N, f(n1,...nk) := n
- 加法 f : N2→ N, f(n1,n2) := n1 + n2
[编辑] 性质
- 给定两个函数 f 和 g，则 f+g、fg 和 f
g 是可计算函数。
- 可计算函数是算术可定义的。
- 布尔值函数 f 是可计算谓词，当且仅当语言
是递归语言。
