无限倒退
无限倒退（），是一种遵循递归原则而产生的无限递归所造成的恶性逻辑现象。无限倒退通常由一组无限的，受递归原则支配的实体或对象所组成的序列构成，在这样的序列中，每一个实体或对象均根据递归原则以前一位的实体为条件或因为前一位实体的存在而产生，并无限向后一位衍生，往复该过程。 举例而言，在中，一个信念之所以合理，是因为它基于另一个合理的信念。但是，这个其他信念本身也需要另一个合理的信念来使其合理，如此继续下去，便产生了一种无限倒退。根据无限倒退…
标签：#递归论
共 35 篇文章
可計算數
可計算數（），是数学名詞，是指可用有限次、會結束的算法計算到任意精確度的实数。可計算數也被稱為遞迴數、遞迴實數或可計算實數。 等效的定義可以用递归函数、图灵机及λ演算等演算法的形式表示法而得。可計算數形成實閉域，可以在許多數學應用上取代实数。 定義 如果一個實數a能被某個可計算函數 f:\mathbb{N}\to\mathbb{Z} 以下述方式來近似，那麼 a 就是一個可計算數：給定任何正整數n，函數值f(n)都滿足： :{f(n) -…
组合子逻辑
组合子逻辑是Moses Schönfinkel和哈斯凱爾·加里介入的一种符号系统，用来消除数理逻辑中对变量的需要。它最近在计算机科学中被用做计算的理论模型和设计函数式编程语言的基础。它所基于的组合子是只使用函数应用或早先定义的组合子来定义从它们的参数得出的结果的高阶函数。 数学中的组合子逻辑 组合子逻辑意图作为简单的元逻辑，它能澄清在逻辑符号中的量化变量的意义，并真正的消除对它们的需要。消除量化变量的另一种方式是蒯因的谓词函子。尽管多数…
決定性問題
在可計算性理論與計算複雜性理論中，決定性問題，亦稱判定問題，（）是一個在某些形式系統回答「是」或「否」的問題。 舉例來說，「判定給定的自然數是否為質數」是一個決定性問題。另一個具體的例子是：「給兩個數字 x 與 y，x 是否可以整除 y？」，此問題依據其 x 與 y 的值可回答是或否。以演算法形式給出的解決決定性問題的方法稱為決策程式（）。對決定性問題「給兩個數字 x 與 y，x 是否可以整除 y？」決策程式將確定 x 是否整除 y。一…
忙碌的海狸
在计算机科学中，忙碌的海狸（）是一个在给定参数后，寻找可能产生的最大输出的可终止程序。忙碌的海狸游戏包括设计一个可终止的，只输出0或1的图灵机，让其在一条纸带上尽可能多的输出1. 包含两个状态的忙碌的海狸游戏有下面两条规则： 该图灵机包括除终止态以外的两个状态 纸带初始值都是0 玩家需要设计出可能输出最多1的状态转换表格，同时也要确保图灵机是会终止的。 能赢得n个状态的忙碌的海狸游戏的图灵机，称为第n个忙碌的海狸，或者用BB-n表示(B…
递归定义
递归定义是数理逻辑和计算机科学用到的一种定义方式，使用被定义对象的自身来为其下定义（简单说就是自我复制的定义）。递归定义与归纳定义类似，但也有不同之处。递归定义中使用被定义对象自身来定义，而归纳定义是使用被定义对象的已经定义的部分来定义尚未定义的部分。不过，使用递归定义的函数或集合，它们的性质可以用数学归纳法，通过递归定义的内容来证明。 定义方式 大部分的递归定义都由三个部分构成：基本情况的定义，递归法则和递归结束的情况。如果定义的对象…
圖靈完備性
在可计算性理论，如果一系列操作数据的规则（如指令集、编程语言、细胞自动机）可以用来模拟任何图灵机，那么它便符合图灵完备（Turing-complete或computationally universal）。这意味着这个系统也可以识别其他数据处理规则集，图灵完备性被用作表达这种数据处理规则集的一种属性。如今，几乎所有编程语言都是具有图灵完备性的。这个词以引入图灵机概念的数学家艾伦·图灵命名。 还有一个相关概念是图灵等价如果P可以模拟Q并且…
急成长阶层
在可计算性理论、计算复杂性理论和证明理论中，急成长阶层（也称为扩展Grzegorczyk阶层或Schwichtenberg-Wainer阶层） 是一类定义域和值域为自然数集，以序数作为索引的函数，即急成长函数fα: N → N构成的集合（其中N是自然数集 {0, 1, ...}，并且索引 α 的范围可达某个大的可数序数）。例如：Wainer阶层，或Löb–Wainer阶层是所有具有索引 α0 的急成长函数。 急成长阶层提供了一种根据增长…
递归论
递归论或可计算性理论，是一个数理逻辑分支。它起源于可计算函数和图灵度的研究。它的领域增长为包括一般性的可计算性和可定义性的研究。在这些领域中，这门理论同证明论和能行描述集合论（effective descriptive set theory）有所重叠。 数理逻辑中的可计算性理论家经常研究相对可计算性、可归约性概念和程度结构的理论。相对于计算机科学家，他们研究次递归层次，可行的计算和公用于可计算性理论研究的形式语言。在这两个社区之间有着相…
递归函数
在数理逻辑和计算机科学中，递归函数或μ-递归函数是一类从自然数到自然数的函数。直觉上递归函数是"可计算的"。事实上在可计算性理论中已经证明了它确实是图灵机的可计算函数。递归函数与原始递归函数相关，而且递归函数的归纳定义（见下）建立在原始递归函数之上。但不是所有递归函数都是原始递归函数——其中最著名的是阿克曼函数。 其他等价的函数类是λ-递归函数和马尔可夫算法可计算的函数。 所有递归函数的集合叫做R。 定义 μ-递归函数（或偏μ-递归函数…
不可判定问题列表
這是一個不可判定问题列表。 逻辑問題 大衛·希爾伯特的可判定性。 二階Λ演算的类型推论和型別檢查。 抽象電腦（Abstract machine）問題 停机问题（決定圖靈機是否停機） 決定圖靈機是否Busy beaver（最長運行的圖靈機有相用的停机问题） 死亡率问题（mortality problem） 萊斯定理指出所有partial方程的非凡屬性，決定機器計算partial方程與其屬性是否未決定。 矩陣問題 矩陣的致命問題：表達，一個…
共递归
共递归在计算机科学重视一类操作，与递归在范畴论上对偶。因而递归是分析地工作，把数据分解为更小的数据直至达到基本情况。共递归是合成地工作，从基本情况构造出数据。共递归的数据是自己一点一点构造出来的。一个类似但不同的概念是生成式递归（generative recursion）。 共递归常与惰性求值配合，产生一个潜在无穷结构的有限子集。 例子 Corecursion can be understood by contrast with rec…
可计算函数
在可计算性理论中，可计算函数（computable function）或图灵可计算函数是研究的基本对象。它们使我们直觉上的算法概念更加精确。使用可计算函数来讨论可计算性而不提及任何具体的计算模型，如图灵机或寄存器机。但是它们的定义必须提及某种特殊的计算模型。 在可计算函数的精确定义之前，数学家经常使用非正式术语可有效计算的。这个术语因此可以被认同为可计算函数。尽管这些函数被叫做有效的，它们可能极其困难。可行可计算性和计算复杂性研究可有效…
跳跃逆转定理
跳跃逆转定理是递归论中关于不可解度的三个定理，定理给出满足特定条件的不可解度的“图灵逆跳跃”的存在性。 定理 弗里德堡定理 设 B\ge_T\mathbf{0}^\prime，则存在 A 使 A^\prime\equiv_T B。 肖恩菲尔德定理 设 B\ge_T\mathbf{0}^\prime 且可用具备 \mathbf{0}^\prime 的预言机递归枚举，则存在 A\le_T\mathbf{0}^\prime 使 A^\prim…
递归集合
在可计算性理论中，一个自然数的子集被称为递归的、可计算的或具可判定性，如果我们可以构造一个算法，使之能在有限时间内终止并判定一个给定元素是否属于这个集合。更一般的集合的类叫做递归可枚举集合。这些集合包括递归集合，对于这种集合，只需要存在一个算法，当某个元素位于这个集合中时，能够在有限时间内给出正确的判定结果，但是当元素不在这个集合中时，算法可能会永远运行下去（但不会给出错误答案）。 定义 自然数的子集 S 被称为递归的，如果存在一个全可…