递归论的算法演化-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

递归论的算法演化

2018-07-15 09:12:29 2110 1
递归论的算法演化
取消 提交回答
全部回答(1)
  • 祁同伟
    2019-07-17 22:55:00

    解决某一类问题的计算方法又称算法。算法是个古老的数学概念。16世纪R.笛卡尔创造的解析几何就是用代数来解决几何问题的一种典型的算法。但数学中有一些问题长期找不到解决的算法。人们怀疑根本不存在这种算法。为了证明这一点,必须对算法给出精确的定义。20世纪30年代K.哥德尔提出了算法的一种精确定义,S.C.克林据此定义了递归函数。与此同时,A.M.图灵用图灵机(一种理论计算机)来描述算法,并且证明图灵可计算的函数与递归函数等价。图灵机使人们普遍接受了关于算法的丘奇论题:递归函数是可计算函数的精确的数学描述。
    递归函数是用数理逻辑的方法定义在自然数集上的可计算函数。如果自然数的一个 n 元集的特征函数是递归函数,就称这个集合为递归集,一个递归函数的值域,称为递归可枚举集。递归集就是算法可判定的集合。递归集都是递归可枚举的,但是存在不是递归集的递归可枚举的集合。递归论的研究使人们把一些长期未解决的问题化为非递归的递归可枚举集,从而严格证明了不存在判定这些问题的算法。这些问题称为不可判定的。
    递归论进一步研究不可判定的,也就是非递归的递归可枚举集之间的复杂程度问题。1944年E.L.波斯特提出不可解度的概念。又给出了相对可计算性的构造方法。这就使人们开始对不可解度进行比较,并研究不可解度的代数结构。这方面出现了有穷损害优先方法、无穷损害优先方法等多种有力的研究手段,出现了许多有趣的研究成果。
    对可计算的递归集,也可以研究其计算的复杂性,考虑图灵机上计算的时间,空间,就得到计算时间的长短计算所占空间的多少这两个复杂性。计算复杂性的研究对计算机科学的发展有很大影响和作用。

    0 0
相关问答

1

回答

什么是非递归遍历算法

2018-07-19 17:59:48 995浏览量 回答数 1

1

回答

阶乘n的递归算法是什么?

2018-07-21 20:48:05 1281浏览量 回答数 1

1

回答

用递归算法求下列函数值

2018-07-21 10:02:58 1033浏览量 回答数 1

1

回答

迭代算法和递归算法的异同?

2018-07-18 16:55:35 1067浏览量 回答数 1

1

回答

求用C语言来表示对称二叉树递归算法

2018-07-22 17:48:48 1281浏览量 回答数 1

1

回答

c#用递归算法求n阶乘

2018-07-18 12:02:14 1246浏览量 回答数 1

3

回答

c语言递归算法

2018-07-17 15:36:57 1148浏览量 回答数 3

5

回答

递归算法有何特点

2018-07-18 18:19:32 1520浏览量 回答数 5

1

回答

二叉树遍历的递归算法是什么?

2018-07-18 10:27:42 1242浏览量 回答数 1

1

回答

n皇后问题,递归算法。

2018-07-17 15:33:40 2348浏览量 回答数 1
+关注
文章
问答
问答排行榜
最热
最新
相关电子书
更多
弱监督机器学习范式
立即下载
典型模型-卷积神经网络入门 从概念原理到应用实现
立即下载
大规模稀疏化模型技术介绍及实践
立即下载