柯尼格引理
柯尼格引理（）为图论中的一个定理。 命题 给定具有无穷个顶点但每个顶点的度有限的连通图G，则对G的任意顶点都至少存在一条无穷的简单路径。 证明 对G的任意顶点v1，因G连通，故v1到G的任意顶点都存在简单路径。由于G存在无穷个顶点，故存在从v1出发的一个无穷的简单路径集。考虑这个无穷简单路径集。因v1的度有限，故该无穷集必然有一个无穷子集通过v1的某个相邻顶点v2。同理，考察通过v1、v2的该无穷简单路径子集，因v2的度有限，故这些无穷…
标签：#递归论
共 35 篇文章
邱奇数
邱奇编码是把数据和运算符嵌入到lambda演算内的一种方式，最常见的形式即邱奇数，它使用lambda符号表示自然数。方法得名于阿隆佐·邱奇，他首先以这种方法把数据编码到lambda演算中。 透過邱奇編碼，在其他符号系统中通常被认定为基本的项（比如整数、布尔值、有序对、列表和tagged unions）都會被映射到高阶函数。在無型別lambda演算，函數是唯一的原始型別。 邱奇編碼本身並非用來實踐原始型別，而是透過它來展現我們不須額外原始…
图灵机
图灵机（），又称确定型图灵机，是英国数学家艾倫·图灵于1936年提出的一种將人的計算行為抽象化的数理逻辑机，其更抽象的意义为一种计算模型，可以看作等价于任何有限逻辑，数学过程的强大可计算机器。 图灵的基本思想 图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作： 在纸上写上或擦除某个符号； 把注意力从纸的一处移动到另一处； 而在每个阶段，人要决定下一步的动作，依赖于（a）此人当前所关注的纸上某…
可判定性問題
可判定性問題（德語：Entscheidungsproblem，意為「決策問題」）是數學和計算機科學中的一個基本問題，由德國數學家大衛·希爾伯特和威廉·阿克曼於1928年提出。此問題為是否存在一個通用的方法，能在有限步驟內，判定一個數學命題的真假。 语言的可判定性 一个语言L，是一个集合，且其补集为\overline{L} 。 当L是图灵机可识别时，语言L则称为半可判定。 当语言L不是图灵机可识别，则为不可判定语言。 当且仅当L和\bar…
停机问题
停机问题（）是逻辑数学中可计算性理论的一个问题。通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：是否存在一个程序P，对于任意输入的程序w，能够判断w会在有限时间内结束或者死循环。 艾伦·图灵在1936年用對角論證法证明了，不存在解决停机问题的通用算法。这个证明的关键在于对计算机和程序的数学定义，这被称为图灵机。停机问题在图灵机上是不可判定问题。这是最早提出的决定性问题之一。 用数学…
不可判定问题
不可判定问题是可计算性理论和计算复杂性理论中定义的一类决定性问题，此类问题无法总是用单一算法得出正确的是/否的答案。停机问题是这类问题的一个代表：对于停机问题，没有算法能够正确判定任意程序是否会终止运行。 背景 决定性问题是一类根据从一个无限集合中选取的输入值，得出是或否的回答的问题。因此，根据传统定义，寻求答案为是的输入值之集合的问题，与决定性问题等价。 与哥德尔不完备定理的关系 不可判定问题举例 参考资料
原始递归函数
在可计算性理论中，原始递归函数（）对计算的完全的形式化而言是形成重要构造板块的一类函数。它们使用递归和复合作为中心运算来定义，并且是递归函数的严格的子集，它们完全是可计算函数。通过补充允许偏函数和介入无界查找运算可以定义出递归函数的更广泛的类。 通常在数论中研究的很多函数，近似于实数值函数，比如加法、除法、阶乘、指数，找到第 n 个素数等等是原始递归的（Brainerd and Landweber, 1974）。实际上，很难设计不是原始…
缓成长阶层
在可计算性理论、计算复杂性理论和证明理论中，缓成长阶层是缓成长函数gα: N → N的序数索引族（其中N是自然数集合, {0, 1, ... }）。缓成长阶层的增长率与急成长阶层形成鲜明对比。 定义 令 μ 为一个大的可数序数，以便将基本序列分配给每个小于 μ 的极限序数。函数gα: N → N的缓成长阶层（对于α g_0(n) = 0 g_{\alpha+1}(n) = g_\alpha(n) + 1 对于极限序数α， g_\alph…
邱奇-图灵论题
邱奇-图灵论题（，又称邱奇-图灵猜想，邱奇论题，邱奇猜想，图灵论题）是一个关于可计算性理论的假设。该假设论述了关于函数特性的，可有效计算的函数值（用更现代的表述来说——在算法上可计算的)。简单来说，邱奇-图灵论题认为“任何在算法上可计算的问题同样可由图灵机计算”。 20世纪上半叶，对可计算性进行公式化表示的尝试有： 美国数学家阿隆佐·邱奇创建了称为λ演算的方法来定义函数。 英国数学家阿兰·图灵创建了可对输入进行运算的理论机器模型，现在被…
柯氏复杂性
在算法信息论（计算机科学和数学的一个分支）中，一个对象比如一段文字的柯氏复杂性（亦作柯尔莫哥洛夫复杂性、描述复杂性、柯尔莫哥洛夫-复杂度、随机复杂度，或算法熵）是衡量描述这个对象所需要的信息量的一个尺度。柯氏复杂性是由安德雷·柯尔莫哥洛夫于1963年发现，所以用他的名字命名。 以下面的两个长度为64的字符串为例。 01010101010101010101010101010101010101010101010101010101010101…
递归 (计算机科学)
遞迴（）在電腦科學中是指一種通過重複將問題分解為同類的子問題而解決問題的方法。 遞迴式方法可以被用於解決很多的電腦科學問題，因此它是電腦科學中十分重要的一個概念。 絕大多數程式語言支援函式的自呼叫，在這些語言中函式可以通過呼叫自身來進行遞迴。計算理論可以證明遞迴的作用可以完全取代迴圈，因此有很多在函數程式語言（如Scheme）中用递归来取代循环的例子。 電腦科學家尼克勞斯·維爾特如此描述遞迴： 遞迴程式 java public void…
預言機
在计算复杂度理论与可计算性理论中，预言机（），又称谕示机，是一种抽象电脑，用来研究决定型问题。可以被视为具備在一次运算之內解答特定问题的黑盒子（又稱為预言者）的图灵机；該问题可以是任何复杂度类，甚至可以是不可判定问题，像是停机问题。 定義 一部預言機可以視為是與一個預言者（）相連接的圖靈機。所謂預言者的概念，是一個可以回答特定問題集合的一個實體，而且常常使用特定的自然數子集A來表示這個問題。我們可以很自然的發現，一部預言機可以執行很多對…
Λ演算
λ演算（英語：lambda calculus，λ-calculus）是一套從數學邏輯中發展出的形式系統，以變數綁定和替換的規則，來研究函式如何抽象化定義、函式如何被應用以及遞迴。它由數學家阿隆佐·邱奇在20世紀30年代首次發表。lambda演算作為一種廣泛用途的計算模型，可以清晰地定義什麼是一個可計算函式，而任何可計算函式都能以這種形式表達和求值，它能模擬單一磁帶图灵机的計算過程；儘管如此，lambda演算強調的是變換規則的運用，而非實…
Μ算子
μ算子（）或者极小化算子（），无界查找算子（）在可计算性理论中，被用來尋找给定性质下的最小自然数。 定义 R( y, x1 , . . ., xk ) 是固定的在自然数上的 k+1 元关系。低洼“μy”，在无界和有界形式下，都是从自然数 { 0, 1, 2, . . . } 到自然数的“数论函数”。但是，“μy”包含在谓词被满第三代 有界μ算子最早出现在 Kleene（1952年）书中的“第4章原始递归函数，§45 谓词，素因子表示”中…
互递归
互递归（mutual recursion），是数学与计算机科学中一种递归，指两个数学或计算机对象如函数或数据类型互相定义。互递归在函數程式語言或某些问题域中非常常见，如，其中数据类型是自然地互相递归定义的。 例子 数据类型 采取互递归定义的最重要的基本数据类型是树。这可以用于定义森林（树的列表）: f: [t[1], ..., t[k]] t: v f 森林f由一棵树的列表组成，同时一棵树t由一对：值v与森林f (子树)构成。这种定义是…
低基定理
低基定理是关于不可解度的定理。 定理 设 A\subseteq 2^\omega 为无穷长二进制串的集合，若自然数的语言中存在递归公式 \theta，使 X\in A 当且仅当 \forall n\,\theta(n,X\vert n)（注：X\vert n 是二进制串 X 的前 n 位）为真，则定义 A 为 \Pi^0_1 类。 若将无穷长二进制串的第 n 位理解成“n 是否属于该集合”，则 2^\omega 自然对应了自然数集合的子…
算数阶层
算术阶层是递归论或可计算性理论中的概念，将自然数的子集按照定义它们的公式的复杂度分类。 定义 按公式定义 设 \phi(x) 为自然数的语言中的公式，定义 \phi 为 \Delta_0 公式当且仅当 \phi 中的所有量词都是有界量词（即形如 \exists n 或 \forall n 的量词，其中 t 为该语言中的项）。 定义 \phi(x) 为 \Sigma^0_1 公式当且仅当 \phi(x):=\exists n\,\thet…
递归可枚举集合
递归可枚举集合（）是可计算性理论或更狭义的递归论中的一个概念。可数集合*'被称为是递归可枚举、计算可枚举的、半可判定的或可证明的，如果 存在一个算法，只有当输入是*'中的元素时，算法才会中止。 或者等价的说， 存在一个算法，可以将S中的成员枚举出来。也就是说该算法的输出就是 S 的成员列表: s1, s2, s3, ... 如果需要它可以永远运行下去。 包含所有可递归枚举集合的复杂性类是 RE。 共同的编程意义会暗示出如何转换一种算法到…
组合范畴语法
组合范畴语法（Combinatory categorial grammar，CCG），是在AB演算基础上进行扩展而产生的范畴语法。从语法理论视角看，CCG是一种词汇形式化的方法；从计算语言学视角看，CCG属于一类适度上下文相关文法；从逻辑语义学视角看，CCG在句法与语义的接口方面非常融洽。无论是CCG语言的、计算的，还是逻辑的特征，都使得 CCG非常适用于自然语言信息处理，对于计算语言学具有很好的理论和实际价值。 介绍 组合范畴语法CC…
波斯纳–罗宾逊定理
波斯納–羅賓遜定理（）是可计算性理论中关于不可解度的定理。 定理 设 B\subseteq\mathbb{N} 不可计算，则存在集合 G 令 G\oplus B\ge_T G^\prime。 证明 这一定理证明如下：令 \Phi_G\subseteq \omega\times\{0,1\}\times2^{，则 \Phi_G 可以看作是一个函数 2^\omega\to2^\omega，具体定义为 a\in\Phi_G(X) 当且仅当存在…