搜索

traduire vers

gecimao 发表于 2019-05-11 06:59 | 查看: | 回复:

  是一类从自然数自然数函数,它是在某种直觉意义上是可计算的。事实上,在可计算性理论中证明了递归函数精确的是图灵机可计算函数。函数有关于原始递归函数,并且它们的归纳定义(见下)建造在原始递归函数之上。但是,不是所有递归函数都是原始递归函数—最著名的这种函数是阿克曼函数。

  μ-递归函数(或偏μ-递归函数)是接受自然数的有限元组并并返回一个单一自然数的偏函数。它们是包括初始函数并闭合在复合、原始递归和μ算子下的最小的偏函数类。

  包括初始函数并闭合在复合和原始递归下的(就是说使用前五个函数定义的)最小的函数类是原始递归函数类。所有原始递归函数都是全函数。需要第六个或μ算子是因为不是所有全函数都可以只用五个原始递归函数来计算(比如阿克曼函数)。在这些实例中μ算子终止运算。它充当无界查找算子,无界但仍然(通过全函数定义)被某种方式(比如归纳证明)证明为最终生成一个数并终止运算。

  但是,如果无界μ算子自身是偏函数 -- 就是说存在某个数它不能为其返回一个数 -- 使用它的函数将也是偏函数 -- 对某些数没有定义。在这些实例中,因为它是无界的,μ算子将永远查找,永不通过生成一个数而终止运算。(某些算法可以采用可以生成指示“不可判定”的符号u并以此终止运算的u-算子(cf Kleene (1952) pp. 328ff))。换句话说:使用偏μ算子的偏μ-递归函数可能不是全函数。全μ-递归函数的集合是全函数的偏μ-递归函数的子集。

  成立,当且仅当对于参数的任何选择要么两个函数都有定义并且它们的值相等要么两个函数都是未定义的。

  在可计算性模型的等价中在对特定输入不终止的图灵机和对这个输入得到未定义结果的相应偏递归函数之间是平行/并列的。无界查找运算是不能通过原始递归的规则定义的,因为它们不提供无限循环(未定义值)的机制。

  数e被叫做函数f的索引或哥德尔数。这个结果的一个结论是任何μ-递归函数都可以使用把μ算子应用于(全)原始递归函数的一个单一实例来定义。

本文链接:http://miamiaccounting.net/diguidingli/289.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部