可计算函数

✍ dations ◷ 2025-09-19 03:20:13 #可计算函数
在可计算性理论中,可计算函数(computable function)或图灵可计算函数是研究的基本对象。它们使我们直觉上的算法概念更加精确。使用可计算函数来讨论可计算性而不提及任何具体的计算模型,如图灵机或寄存器机。但是它们的定义必须提及某种特殊的计算模型。在可计算函数的精确定义之前,数学家经常使用非正式术语可有效计算的。这个术语因此可以被认同为可计算函数。尽管这些函数被叫做有效的,它们可能极其困难。可行可计算性和计算复杂性研究可有效计算的函数。依据邱奇-图灵论题,可计算函数精确的是使用给出无限数量的时间和存储空间的机器计算设备来计算的函数。等价的说,这个论题声称有算法的任何函数都是可计算的。可以使用Blum公理来在可计算函数的集合上定义抽象计算复杂性理论。在计算复杂性理论中,确定一个可计算函数的复杂性的问题叫做功能性问题。计算函数是在自然数上的有限偏函数。每个可计算函数 f {displaystyle f} 接受固定数目个自然数作为参数;不同的函数接受不同数目的参数。因为函数是部分的,它们可以不定义在所有可能的输入选择上。如果定义了一个可计算函数,则它返回一个单一自然数作为输出(这个输出可以被解释为使用配对函数的一列数)。记号 f ( x 1 , … , x k ) ↓ {displaystyle f(x_{1},ldots ,x_{k})downarrow } 指示偏函数 f {displaystyle f} 被定义在参数 x 1 , … , x k {displaystyle x_{1},ldots ,x_{k}} 上,而记号 f ( x 1 , … , x k ) ↓= y {displaystyle f(x_{1},ldots ,x_{k})downarrow =y} 指示 f {displaystyle f} 被定义在参数 x 1 , … , x k {displaystyle x_{1},ldots ,x_{k}} 上而返回的值是 y {displaystyle y} 。这些函数也叫做偏递归函数。在可计算理论中,函数的定义域是函数被定义在其上的所有输入的集合。定义在所有参数上的函数叫做全函数。如果可计算函数是全函数,它叫做全可计算函数或全递归函数。有很多等价方式定义可计算函数的类。为了具体,本文余下部分将假定可计算函数已经被定义可以被图灵机计算的那些偏函数。有很多计算的等价模型定义同一类可计算函数。这些计算模型包括等等。自然数的集合A被叫做可计算的(同义词:递归的,可决定的),如果有可计算函数f使得对于每个自然数n, f ( n ) ↓= 1 {displaystyle f(n)downarrow =1} 如果n在A中,并且 f ( n ) ↓= 0 {displaystyle f(n)downarrow =0} 如果n不在A中。自然数的集合被叫做计算可枚举的(同义词:递归可枚举的,半可判定的),如果有可计算函数f使得对于每个自然数n,f(n)是有定义的,当且仅当n在这个集合中。所以一个集合是计算可枚举的,当且仅当它是某个可计算函数的定义域。使用词可枚举的因为对于自然数的非空子集B下列是等价的:如果集合B是函数f的值域,则这个函数可以被看作B的枚举,因为列表f(0), f(1), ...将包含B的所有元素。因为在自然数上的每个有限关系都可以被识别为对应的自然数的有限序列的集合,可计算关系和计算可枚举关系的概念可以从它们的集合类似物来定义。在计算机科学的可计算性理论中,经常考虑形式语言。它包括任意集合的一个字母表,在字母表上的字是来自字母表的符号的有限序列;同一个符号可以出现多于一次。例如,二进制字符串精确的是在字母表 { 0 , 1 } {displaystyle {0,1}} 上的字。语言是在固定字母表上的所有字的搜集的子集。例如,精确的包含三个字母的所有二进制字符串的搜集是在二进制字母表上的一个语言。形式语言的一个关键性质是对判定一个给定字是否在这个语言中的难度级别。必须开发某种编码系统来允许可计算函数来接受在语言中的任意字作为输入;这通常是要认真处置的例程。一个语言被称为是可计算的(同义词:递归的、可判定的),如果存在一个可计算函数 f {displaystyle f} 使得对于在字母表上的每个字w, f ( w ) ↓= 1 {displaystyle f(w)downarrow =1} 如果这个字在这个语言中,并且 f ( w ) ↓= 0 {displaystyle f(w)downarrow =0} 如果这个字不在这个语言中。所以一个语言在有一个过程能正确的判定任意的字是否在这个语言中的情况下是可计算的。一个语言是计算可枚举的(同义词:递归可枚举的,半可判定的),如果有可计算函数f使得 f ( w ) {displaystyle f(w)} 是有定义的,当且仅当字w在这个语言中。术语可枚举同自然数的计算可枚举集合有同样的语源。如果f和g是可计算的,则:f + g, f * g, f ∘ g {displaystyle fcirc g} 如果 f是一元的,max(f,g), min(f,g)和更多的组合都是可计算的。

相关

  • 第一手文献一次文献,又称初级资料、首次资料、一级来源或称第一手资料,是文献学、图书馆学、地理学中指用来做为证据的引文资料, 写作者将其来源方式可以区分成:依据研究资料及方法的不同,
  • 鸦片类药物阿片类药物(Opioid)是具有吗啡作用的化学物质,主要用途是镇痛。阿片类药物通过存在于中枢神经系统和消化系统的阿片类受体(Opioid receptor)起作用。这些阿片类受体能引发有益的
  • 克隆失能株落失能(英语:Clonal anergy)是一个免疫学名词。描述的是周边淋巴球对于外来物质失去产生免疫反应的能力,而导致耐受性。失能的淋巴球株落将无法对于特定的抗原产生免疫反应,通
  • 死亡勃起死亡勃起是人类男性在被处决(尤其是处以绞刑)后,尸体的阴茎会出现勃起的现象。其原因主要是绞索对小脑施压, 已知与脊髓损伤也有关系。 死亡勃起发生后,阴茎会排出尿液或前列腺中
  • 死亡率死亡率是用来衡量一部分人口中,一定规模的人口大小、每单位时间的死亡数目(整体或归因于指定因素)。死亡率通常以每年每一千人为单位来表示;因此在死亡率为9.5的10万人口中,表示
  • 李斯特菌李斯特菌(学名:Listeria monocytogenes),又名单核细胞增生性李斯特菌、李氏菌,是一种兼性厌氧细菌,为李斯特菌症的病原体。它主要以食物为传染媒介,是最致命的食源性病原体之一,造成
  • CD4+ T细胞辅助T细胞(T helper cells, Th),又称为助手型T细胞,是一种T细胞(白细胞的一种),它的表面有抗原受体,可以辨识抗原提呈细胞的MHC-II类分子呈献的抗原片段。一旦受到抗原刺激,Th细胞就
  • VIIBbr /7固体、 液体、 气体7族元素(又称锰族元素)是指元素周期表上第7族(ⅦB 族)的元素,位于6族元素和8族元素之间。7族元素包含锰(Mn)、锝(Tc)、铼(Re)、
  • 增生性贫血增生性贫血即指血液中某种细胞增生过多引起其他细胞成分相对减少的贫血。包括三大类贫血:溶血性贫血、缺铁性贫血和巨幼细胞增生性贫血
  • 理论理论(英语:Theory),又称学说或学说理论,指人类对自然、社会现象,按照已有的实证知识、经验、事实、法则、认知以及经过验证的假说,经由一般化与演绎推理等等的方法,进行合乎逻辑的推