网站首页 情感咨询 情感美文 情感百科 情感生活 学习充电 旧版美文
| 标题 | 递归论 |
| 类别 | 哲学 |
| 释义 | 递归论 recursion theory 一门算法地处理数学中各类问题的学科。数理逻辑的分支之一。狭义地指研究递归函数类或能行可计算函数类及其对数学各学科应用的理论。这部分还包括判定理论、不可解问题及不可解度的研究。广义地指研究用递归来定义的一般过程。这部分不仅涉及数论函数，也涉及其他类型的数学结构，包括a - 递归，高类递归及递归定义等的研究。能行描述集论是递归论的主要应用之一，计算复杂性的研究是递归论的一个重要的实用方向。递归论的历史与数学基础探讨的历史密切相关。如斐波纳奇级数那样的“循环级数”，是递归函数的前驱。斯柯林(T. Skolem， 1887—1963)已提出可不必用无穷的总合去建基初等数论中的概念。希尔伯特提出的证明论，试图把数学的各个分支与其中的证明加以塑述，使得这些证明亦能作为数学探讨的对象。这种“元数学”的探讨，推进了不用实无穷的递归数论的发展。哥德尔在不完全性定理的证明中，第一个提出和使用了原始递归函数理论。后又有过多个等价的关于递归函数的定义。此外，厄布朗(J. Herbrand)、图灵、丘奇、克林、波斯特等人对递归论的建立也有重要贡献。递归论的基本内容是讨论“能行可计算”或“算法可计算”的函数类，研究“算法函数”的精确数学模型。对于算法这个概念，长期来都是一个直观的概念，人们也没有使其精确化的要求，直到1900年希尔伯特提出了著名的二十三个数学问题，其中第十个问题是：寻找一个算法，使得对任意给定的具整系数的多项式p(x1，…，xn)，能借助于这个算法在有限步内判定方程(丢番都方程)p(x1，…，xn)=0是否有整数解。以后由于人们始终未能找到这样的一个算法， 以致开始设想希尔伯特第十个问题的算法可能根本不存在。 但要作这一断定(即“递归不可解问题”)， 需要作出严密的证明， 同时也需要对算法这个概念作出一个精确的数学定义， 从而引出使算法这一直观概念精确化的要求。1930年以后，这一问题吸引了众多逻辑学家的注意，推动了递归论的进展。此后相继出现了刻划算法这个概念的多种等价形式。到1970年，由马基雅西维契(Ю . В . Матиясевич)在罗宾逊(Abraham Robinson， 1918—1974)等人研究基础上，最后证明了这一问题是递归不可解的。递归论产生后在许多方面得到了应用。最早的应用是在递归可枚举集不可解性的研究基础上，得出了数理逻辑和数学各分支的许多问题的递归不可解性。除希尔伯特第十问题外，还包括半群上的字问题，谓词演算的判定问题。由于算法的研究是计算机科学中重要的内容，而递归论又给出了算法的描述和处理方法，因此，递归论在计算机科学中也有广泛的应用。 |
| 随便看 |
|
依恋情感网情感百科知识大全收录了49620条情感类百科知识词条，覆盖心理学、哲学、美学等领域，基本涵盖了日常生活中常见问题的详细解释，是情感生活的有利工具。