原始递归函数

✍ dations ◷ 2025-06-27 20:12:58 #原始递归函数
在可计算性理论中,原始递归函数(英语:primitive recursive functions)对计算的完全的形式化而言是形成重要构造板块的一类函数。它们使用递归和复合作为中心运算来定义,并且是递归函数的严格的子集,它们完全是可计算函数。通过补充允许偏函数和介入无界查找运算可以定义出递归函数的更广泛的类。通常在数论中研究的很多函数,近似于实数值函数,比如加法、除法、阶乘、指数,找到第 n 个素数等等是原始递归的(Brainerd and Landweber, 1974)。实际上,很难设计不是原始递归的函数,尽管某些函数是已知的(比如阿克曼函数)。所以,通过研究它们,我们能发现有广泛影响的结论的那些性质。原始递归函数可以用总是停机的图灵机计算,而递归函数需要图灵完全系统。原始递归函数的集合在计算复杂性理论中叫做PR。原始递归函数接受自然数或自然数的元组作为参数并生成自然数。接受 n 个参数的函数叫做 n-元函数。基本原始递归函数用如下公理给出:更加复杂的递归函数可以通过应用下列公理给出的运算来获得:服从这些公理的函数是原始递归的,如果它是上述基本函数之一,或者它可以通过应用有限次数的运算获得自基本函数。投影函数可用来避免采用上述明显刻板的函数元数方式;通过使用各种投影函数的复合,有可能把一个函数的参数子集传递到另一个函数。例如,如果 g 和 h 是二元原始递归函数,则也是原始递归的。使用投影函数的一个形式定义为在某些设置中,自然的考虑接受混合了数值和真值{ t= true, f=false } 的参数,或生成真值作为输出的原始递归函数(参见 Kleene )。这可以通过把真值识别为任何固定方式的数值来完成。例如,通常把真值t 识别为 1 和真值 f 识别为 0。一旦作出这种识别,集合 A 的特征函数,它在文字上返回 1 或 0,可以被看作判定一个数是否在集合 A 中的谓词。把谓词识别为数值函数的这种方式将假定于本文余下部分。直觉上我们会把加法递归的定义为:为了使它适合于严格的原始递归定义,我们定义:(注意: 这里的 P13 是一个函数,它接受 3 个参数并返回第一个。)P11 是简单的恒等函数;包含它是上述原始递归运算定义的要求;它扮演了 f 的角色。S 和 P13 的复合,它是原始递归的,它扮演了 g 的角色。我们可以定义有限减法,就是说,截止到 0 的减法(因为我们还没有负数的概念呢)。首先我们必须定义"前驱" 函数,它担任后继函数的对立物。直觉上我们会把前驱定义为:为了使它适合正式的原始递归定义,我们写:现在我们以类似加法的方式定义减法。出于简单的缘故,切换了"标准"定义的参数次序来适合原始递归的要求,就是说, sub(a,b) 对应于 b-a。这可以轻易的使用适当的投影来矫正。很多类似的函数可以被证明是原始递归的;一些例子包括条件、指数、素数检验和数学归纳法,并且原始递归函数可以被扩展来运算在其他对象上比如整数和有理数。通过使用哥德尔数,原始递归函数可以被扩展到在其他对象比如整数和有理数上的运算上。如果以标准方式编码整数用哥德尔数,算术运算包括加法、减法、乘法都是原始递归的。类似的,如果以哥德尔数表示有理数,则域运算都是原始递归的。通过介入无界查找算子可定义更广泛的偏递归函数类。这个算子的使用可以导致偏函数,就是说,对每个参数有最多一个值,但是不同于全函数,不必须对参数有值的关系(参见定义域)。一个等价的定义声称偏递归函数是可以被图灵机就算的函数。全递归函数是对所有输入有定义的偏递归函数。所有原始递归函数都是全递归的,但不是所有全递归函数都是原始递归的。阿克曼函数 A(m,n)是周知的不是原始递归的全递归函数。原始递归函数有作为使用阿克曼函数的全递归函数的子集的一个特征。这个特征声称一个函数是原始递归的,当且仅当有一个自然数 m 使得这个函数可以被总在 A(m,n) 或更少步骤内停机的图灵机计算,这里的 n 是原始递归函数的参数的总数。原始递归函数意图紧密对应于我们直觉上可计算函数应该的样子。当然函数的初始集合在直觉上是可计算的(因为它们非常简单),而你能用来创建新原始递归函数的两个运算也是非常直接的。但是原始递归函数的集合不包含所有可能的可计算函数 — 这可以看作康拖尔对角论证法的变体。这个论证提供了一个不是原始递归的可计算函数。证明的梗概如下:原始递归函数集合可以被计算枚举。这个编号方案在函数定义上是唯一的,尽管在实际函数自身上不是唯一的(因为所有的函数都可以有无限数目的定义 — 考虑简单的由恒等函数构成)。这个编码在可计算性的形式模型,比如递归函数或图灵机下定义的意义上是可计算的,邱奇-图灵论题涉及的任何机器都可以。现在考虑一个矩阵,这里的行是在这个编号方案下的有一个参数的原始递归函数,而列是自然数。则每个元素 (i, j) 对应于计算于数 j 之上的第 i 个一元原始递归函数。我们可以写为 fi(j)。现在我们考虑函数 g(x) = S(fx(x))。g 位于这个矩阵的对角线上,并简单的对它找到的值加一。这个函数是可计算的(按上述定义),但是明显的没有计算它的原始递归函数存在,因为它与每个可能的原始递归函数都有至少一个值不同。所以,必然存在不是原始递归的可计算函数。这个论证可以应用于能用这种方式枚举的任何一类的可计算(全)函数上。所以,任何这种可计算(全)函数的明确列表都不可能是完全的,比如那些可以用总是停机的机器计算的函数。但是要注意,偏可计算函数集合(那些不需要对所有参数有定义的函数)可以被明确的枚举,例如通过枚举图灵机编码。可以明确展示的一个简单的 1-元可计算函数阿克曼函数,它是对任何自然数递归定义的,但不是原始递归的。

相关

  • 周产期死亡周产期死亡(PNM, Perinatal mortality)是指胎儿或是新生儿的死亡,是计算周产期死亡率的基础。周产期死亡率的标准定义较多样,特别是涉及到是否须把早期胎儿和晚期新生儿死亡纳入
  • 视网膜病变糖尿病视网膜病变(英语:Diabetic retinopathy)是糖尿病的并发症。长期的高血糖环境会损伤视网膜血管的内皮,引起一系列的眼底病变,如微血管瘤、硬性渗出、棉絮斑、新生血管、玻璃
  • 抗利尿激素1jk4, 1jk6, 1npo, 2bn2· signal transducer activity · receptor binding · neuropeptide hormone activity · neurohypophyseal hormone activity · V1A vasopre
  • 呕血呕血(hematemesis)是指患者呕吐出血液的症状,血液的来源为上消化道(即屈氏韧带以上的消化道,包括食管、胃、十二指肠或胰胆等的出血,胃空肠吻合术后的空肠出血也属于上消化道)。呕
  • 伊利阿斯·马格努斯·弗里斯埃利亚斯·芒努斯·弗里斯(瑞典语:Elias Magnus Fries,1794年8月15日-1878年2月8日),瑞典生物学家。他在六十多年的科研生涯中,搜集了欧洲各地大量的真菌标本,对其进行了科学、系统
  • ISO国际标准化组织(英语:International Organization for Standardization,简称:ISO)成立于1947年2月23日,制定全世界工商业国际标准的国际标准建立机构。ISO总部设于瑞士日内瓦,成员
  • 宫底高度宫底高度(Fundal height)也称为耻骨联合-宫底高度(symphysial fundal height,也称为SFH),也称为宫顶高度或宫高,是妊娠中量测子宫大小的方式,可以在怀孕中评估胎儿成长及其发育情形
  • 陶尔米纳陶尔米纳(Taormina),在意大利西西里岛的墨西拿省内、位于墨西拿和卡塔尼亚之间,人口约九千九百余。公元前400年陶尔米纳曾是希腊的殖民地。公元前212年又归罗马帝国管辖。陶尔米
  • 韧带韧带(ligament、拉丁语 ligamenta,单数 ligamentum)是可弯曲,纤维样的弹性结缔组织。韧带连接骨与骨,为明显的纤维组织,或附于骨的表面或与关节囊的外层融合,以加强关节的稳固性,以
  • 女性生殖器官女性生殖系统是由人类女性的生殖器官组成的系统。可分成内生殖器官和外生殖器官,分别指生殖系统在体内不可见的部分和体外可见的部分。人类女性的生殖系统在出生时尚未发育成