查看“︁可计算函数”︁的源代码

{{NoteTA
|G1 = IT
|G2 = Math
}}
在[[可计算性理论]]中，'''可计算函数'''（computable function）或'''图灵可计算函数'''是研究的基本对象。它们使我们直觉上的[[算法]]概念更加精确。使用可计算函数来讨论可计算性而不提及任何具体的[[计算模型]]，如图灵机或寄存器机。但是它们的定义必须提及某种特殊的计算模型。

在可计算函数的精确定义之前，数学家经常使用非正式术语'''可有效计算的'''。这个术语因此可以被认同为可计算函数。尽管这些函数被叫做有效的，它们可能极其困难。[[可行可计算性]]和[[计算复杂性]]研究可有效计算的函数。

依据[[邱奇-图灵论题]]，可计算函数精确的是使用给出无限数量的时间和存储空间的机器计算设备来计算的函数。等价的说，这个论题声称有[[算法]]的任何函数都是可计算的。

可以使用[[布盧姆公理]]来在可计算函数的集合上定义抽象[[计算复杂性理论]]。在计算复杂性理论中，确定一个可计算函数的复杂性的问题叫做[[功能性问题]]。

==定义==

计算函数是在[[自然数]]上的[[有限集合|有限]][[偏函数]]。每个可计算函数<math>f</math>接受固定数目个自然数作为参数；不同的函数接受不同数目的参数。因为函数是部分的，它们可以不定义在所有可能的输入选择上。如果定义了一个可计算函数，则它返回一个单一自然数作为输出（这个输出可以被解释为使用[[配对函数]]的一列数）。记号<math> f(x_1,\ldots,x_k) \downarrow </math>指示偏函数<math> f </math>被定义在参数<math>x_1,\ldots,x_k</math>上，而记号<math>f(x_1,\ldots,x_k) \downarrow = y</math>指示<math>f</math>被定义在参数<math>x_1,\ldots,x_k</math>上而返回的值是<math>y</math>。这些函数也叫做'''偏递归函数'''。在可计算理论中，函数的'''[[定义域]]'''是函数被定义在其上的所有输入的集合。

定义在所有参数上的函数叫做'''[[全函数]]'''。如果可计算函数是全函数，它叫做'''全可计算函数'''或'''全递归函数'''。

有很多等价方式定义可计算函数的类。为了具体，本文余下部分将假定可计算函数已经被定义可以被[[图灵机]]计算的那些偏函数。有很多计算的等价模型定义同一类可计算函数。这些[[计算模型]]包括
* [[图灵机]]
* [[递归函数|Mu-递归函数]]
* [[Lambda演算]]
* [[标记系统|Post机]]，也叫做标记系统
* [[寄存器机]]
等等。

==可计算集合和关系==

自然数的集合''A''被叫做'''可计算的'''（同义词：'''[[递归集合|递归的]]'''，'''可决定的'''），如果有可计算函数''f''使得对于每个自然数''n''，<math>f(n) \downarrow = 1</math>如果''n''在''A''中，并且<math>f(n) \downarrow = 0</math>如果''n''不在''A''中。

自然数的集合被叫做'''计算可枚举的'''（同义词：'''[[递归可枚举集合|递归可枚举的]]'''，'''半可判定的'''），如果有可计算函数''f''使得对于每个自然数''n''，''f(n)''是有定义的，当且仅当''n''在这个集合中。所以一个集合是计算可枚举的，当且仅当它是某个可计算函数的定义域。使用词'''可枚举的'''因为对于自然数的非空子集''B''下列是等价的：
* ''B''是可计算函数的定义域。
* ''B''是全可计算函数的值域。如果''B''是无限的则这个函数可以被假定为[[单射函数|单射的]]。
如果集合''B''是函数''f''的值域，则这个函数可以被看作''B''的枚举，因为列表''f(0)'', ''f(1)'', ...将包含''B''的所有元素。

因为在自然数上的每个[[有限关系]]都可以被识别为对应的自然数的有限序列的集合，'''可计算关系'''和'''计算可枚举关系'''的概念可以从它们的集合类似物来定义。

== 形式语言 ==
:''{{main|形式语言}}

在计算机科学的[[可计算性理论]]中，经常考虑[[形式语言]]。它包括任意集合的一个'''字母表'''，在字母表上的'''字'''是来自字母表的符号的有限序列；同一个符号可以出现多于一次。例如，二进制字符串精确的是在字母表<math>\{0,1\}</math>上的字。'''语言'''是在固定字母表上的所有字的搜集的子集。例如，精确的包含三个字母的所有二进制字符串的搜集是在二进制字母表上的一个语言。

形式语言的一个关键性质是对判定一个给定字是否在这个语言中的难度级别。必须开发某种编码系统来允许可计算函数来接受在语言中的任意字作为输入；这通常是要认真处置的例程。一个语言被称为是'''可计算的'''（同义词：'''[[递归语言|递归的]]'''、'''可判定的'''），如果存在一个可计算函数<math>f</math>使得对于在字母表上的每个字''w''，<math>f(w) \downarrow = 1</math>如果这个字在这个语言中，并且<math>f(w)\downarrow = 0</math>如果这个字不在这个语言中。所以一个语言在有一个过程能正确的判定任意的字是否在这个语言中的情况下是可计算的。

一个语言是'''计算可枚举的'''（同义词：'''[[递归可枚举语言|递归可枚举的]]'''，'''半可判定的'''），如果有可计算函数''f''使得<math>f(w)</math>是有定义的，当且仅当字''w''在这个语言中。术语'''可枚举'''同自然数的计算可枚举集合有同样的语源。

==例子==

* [[常数函数]]''f'' : '''N'''<sup>''k''</sup>→ '''N''', ''f''(''n''<sub>1</sub>,...''n''<sub>''k''</sub>) := ''n''。
* [[加法]]''f'' : '''N'''<sup>2</sup>→ '''N''', ''f''(''n''<sub>1</sub>,''n''<sub>''2''</sub>) := ''n''<sub>1</sub> + ''n''<sub>2</sub>。
* 给出一个数的[[素因数]]列表。
* 两个数的[[最大公约数]]。
* [[贝祖等式]]，线性的[[丢番图方程]]。

如果''f''和''g''是可计算的，则：''f + g'', ''f * g'', <math>f \circ g</math>如果
''f''是一元的，max(''f'',''g''), min(''f'',''g'')和更多的组合都是可计算的。

==相關條目==

* [[可計算數]]
* [[可定義數]]

== 引用 ==

*Enderton, H.B. Elements of recursion theory.  ''Handbook of Mathematical Logic'' (North-Holland 1977) pp. 527–566.

*Rogers, H.  ''Theory of recursive functions and effective computation'' (McGraw-Hill 1967).

*Turing, A. (1936), On Computable Numbers, With an Application to the Entscheidungsproblem. ''Proceedings of the London Mathematical Society'', Series 2, Volume 42 (1936). Reprinted in M. Davis (ed.), ''The Undecidable'', Raven Press, Hewlett, NY, 1965.

[[Category:递归论]]
[[Category:計算理論]]
[[Category:函数]]