Coq:证明不带非递归构造函数的归纳类型是不可驻留的 - 腾讯云开发者社区 - 腾讯云

开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

「SF-LC」10 IndPrinciples

Basic 每次我们使用 Inductive 来声明数据类型时，Coq 会自动为这个类型生成归纳原理。...为每一个 Inductive 定义的数据类型生成了归纳原理，包括那些非递归的 Coq generates induction principles for every datatype defined...尽管我们不需要使用归纳来证明非递归数据类型的性质 Although of course we don’t need induction to prove properties of non-recursive...，那么 P 对于 c x1 ... xn 成立” 每个具有类型 t 的参数的地方即发生了「递归」与「子结构」，归纳假设 = 「对子结构成立」....因此，其归纳定理 list_ind 是一个被 X 参数化多态的函数。

7163 0

用于数学的 10 个优秀编程语言

民意调查，数据挖掘者调查和学术文献数据库研究表明，近年来R的受欢迎程度大幅增加。 4. COQ / GALLINA Coq是一个交互式的定理证明工具。...它允许表达数学断言，机械地检查这些断言的证明，帮助找到形式化的证明，并从其正式规范的建设性证明中提取认证程序。 Coq工作在归纳结构微积分理论的基础上，归纳结构微积分是结构微积分的一个衍生物。...作为编程语言，Coq实现了一种依赖类型的函数式编程语言，作为逻辑系统，Coq实现了一个更高阶的类型理论。 Coq提供了一种名为Gallina的规范语言。...6.Haskell Haskell是一个标准化的，通用的纯函数式编程语言，具有非严格的语义和强大的静态类型。Haskell具有类型推断和惰性计算的类型系统。...IDRIS Idris是一种具有相关类型的通用纯函数编程语言。类型系统类似于Agda使用的类型系统。语言支持可与Coq媲美的交互式定理证明，包括策略，即使在定理证明之前，重点仍然放在通用编程上。

3.2K10 0

您找到你想要的搜索结果了吗？

是的

没有找到

用了一段时间Agda的感想

虽然都以有类型λ演算为理论基础（Agda是UTT，Coq是归纳构造演算），但是表现在证明上，两者就有很大的不同了。在Agda中，命题的证明就是给出一个类型的一个项。...Coq使用了不同的Tactics来辅助证明。在Coq中进行证明的过程更加类似于一般的数学证明。以下是证明皮尔士定律与排中律等价的Agda、Coq程序片段。...Agda的证明并没有用Function.Equality的_⇔_，因为我个人觉得那个东西非常复杂。证明过程中，Agda实际上是在辅助使用者获得某类型的项。...而针对这个目标，Agda提供了比如Case和Refine之类的工具来根据类型生成目标代码，这一点是十分方便的。但是缺点也显而易见，就是证明过程并不按照一般的证明顺序进行的，毕竟只是项的构造。...综上，如果是数学的证明，我大概会选择Coq。如果是用来实现论文里的Type System，我会更青睐于使用Agda。

1.4K1 0

原始递归函数及模拟运行的优化

于是，正好把《递归论》相关内容补一补。【原始递归函数】　　首先，我们明确，《递归论》里研究的都是自然数里的函数。　　所谓自然数，在这里的意思是指非负整数，我们可以用Peano五公理定义。　　...我们平常见到的绝大多数自然数下的函数都是原始递归函数。【原始递归函数的可计算性】　　原始递归函数的可计算性很容易证明。　　首先，本原函数是可计算的。　　...根据数学归纳法，　　　　$h$是可计算的。　　于是，我们根据复合规则和递归规则得到的总是可计算函数。从而所有的原始递归函数都是可计算的。【实现】　　我们就用Scheme来描述。　　...则定义如下： pre(0)=0 pre(n+1)=n 　　这也很像用一次递归规则就可以完成的事，只可惜，无法构造出不带参数的函数，所以需要一个技巧，先构造一个带两元的函数。...递归论里，我们一般用0、非0来代表假、真。　　实现逻辑非和实现之前的pre函数的手法类似，我们先用递归规则做一个二元函数，然后再用复合规则。

1.5K3 0

函数的定义和使用及代码复用和函数递归

函数的定义与使用函数的定义函数是一段代码的表示函数是一段具有特定功能的、可重用的语句组函数是一种功能的抽象，一般函数表达特定功能两个作用：降低编程难度和代码复用 def (<...组合数据类型，如果局部变量未真实创建，则是全局变量 lambda函数 lambda函数返回函数名作为结果 lambda函数是一种匿名函数，即没有名字的函数使用lambda保留字定义，函数名是返回结果...定义的普通函数代码复用与函数递归代码复用与模块化设计代码复用把代码当成资源进行抽象代码资源化：程序代码是一种用来表达计算的"资源" 代码抽象化：使用函数等方法对代码赋予更高级别的定义代码复用...类似数学归纳法数学归纳法证明当n取第一个值n0时命题成立假设当nk时命题成立，证明当n=nk+1时命题也成立递归是数学归纳法思维的编程体现函数递归的调用过程 **函数 + 分支语句递归本身是一个函数...函数递归的实现：函数 + 分支结构

871 0

函数式编程的优与劣

这个特性带来的弊端就是学习如何使用它们开发软件很困难。对于我们这些用强类型语言的开发者，尤其困难。递归和模式匹配函数式编程语言特性是运行期优化递归。...使用尾调用优化，运行期提供高效的回调环境，使每个回调用相同的栈帧(stack frame)。再加上参数模式匹配，你可以像写归纳法证明(高中数学的归纳法)那样写表达式函数。你有一个基础步骤和归纳步骤。...基础步骤结束递归，归纳步骤重复递归。通过这种方式，你可以定义函数处理列表或集合。函数的每个变量在每次调用中绑定，这使得变量绑定更易于管理。下面是个伪代码例子： ?...第二个步骤是归纳步骤——如果列表有头元素和尾元素，然后我们把尾元素通过递归调用looper()方法求和。...你在Ruby或JavaScript中只需要把基础步骤放在归纳步骤前面就行。常量赋值这点在函数式语言中很难实现。毕竟用不可变的值表示可变的状态非常困难。你又该怎么办呢？

7281 0

函数式编程的优与劣

这个特性带来的弊端就是学习如何使用它们开发软件很困难。对于我们这些用强类型语言的开发者，尤其困难。递归和模式匹配函数式编程语言特性是运行期优化递归。...使用尾调用优化，运行期提供高效的回调环境，使每个回调用相同的栈帧(stack frame)。再加上参数模式匹配，你可以像写归纳法证明(高中数学的归纳法)那样写表达式函数。你有一个基础步骤和归纳步骤。...基础步骤结束递归，归纳步骤重复递归。通过这种方式，你可以定义函数处理列表或集合。函数的每个变量在每次调用中绑定，这使得变量绑定更易于管理。下面是个伪代码例子： ?...第二个步骤是归纳步骤——如果列表有头元素和尾元素，然后我们把尾元素通过递归调用looper()方法求和。...你在Ruby或JavaScript中只需要把基础步骤放在归纳步骤前面就行。常量赋值这点在函数式语言中很难实现。毕竟用不可变的值表示可变的状态非常困难。你又该怎么办呢？

6482 0

NLP入门之形式语言与自动机学习(一)

今后用R+ 表示R的传递闭包,用R* 表示R的自反传递闭包。定义1.1.6 映射是关系的一个特殊类型 , 也称函数。...f的值域是B的子集,记为Rf。函数的几种特殊类型是 : (1) 对于f:A→B。如果f的值域Rf =B,即B的每一个元素都是A中一个或多个元素的像点,则称f是满射的。...因此,在使用数学归纳法证明某个关于非负整数n的命题P(n) 时,只需要证明(1)、(2) 两点即可。第(1)步称为归纳基础, 第(2)步称为归纳步骤。...比如说用归纳法证明下递归: 归纳法证明递归定义集合性质的步骤如下。...(1) 基础:证明该集合中的最基本元素具有性质P; 而且使得该集合非空; (2) 归纳: 证明如果该集合的元素x1 ,x2 ,x3 , …,具有性质P, 则使用某种运算、函数或组合方法对这些元素进行处理后所得的元素也具有性质

2.1K6 1

NLP入门之形式语言与自动机学习(一)

今后用R+ 表示R的传递闭包,用R* 表示R的自反传递闭包。定义1.1.6 映射是关系的一个特殊类型 , 也称函数。...f的值域是B的子集,记为Rf。函数的几种特殊类型是 : (1) 对于f:A→B。如果f的值域Rf =B,即B的每一个元素都是A中一个或多个元素的像点,则称f是满射的。...因此,在使用数学归纳法证明某个关于非负整数n的命题P(n) 时,只需要证明(1)、(2) 两点即可。第(1)步称为归纳基础, 第(2)步称为归纳步骤。...比如说用归纳法证明下递归: 归纳法证明递归定义集合性质的步骤如下。...(1) 基础:证明该集合中的最基本元素具有性质P; 而且使得该集合非空; (2) 归纳: 证明如果该集合的元素x1 ,x2 ,x3 , …,具有性质P, 则使用某种运算、函数或组合方法对这些元素进行处理后所得的元素也具有性质

2.1K13 0

USING INDUCTION TO DESIGN 使用归纳法设计算法【全文翻译】

（事实上我们称这种方法为归纳而不是递归，从而淡化递归实现的概念）在很多情况下，迭代也很容易，甚至尽管在算法设计中我们心里想的是使用归纳法（递归），但迭代却更有效率。...下面给出一个非递归的算法实现。...结论：我们刚才使用的是一种常见技术方法的一个具体实例，该方法被称为动态规划，它的本质是建立一个巨大的表，在表中填入已知的之前的解答。该表是用迭代的方法进行构造的。...最大的反例在证明数学定理中一种有特色并且强大的技巧是假设定理的反面成立然后找到一个矛盾。通常这是用一种完成非建设性的方式实现的，这对于我们的类比不是很有用。...普通的归纳法通过从一个基本情况(n=1)开始然后不断推广从而覆盖所有的自然数。假设我们想要逆推。我们假设它对n成立想要证明它对n-1也成立。我们称这种类型的证明为逆向归纳。但是，什么是最基本的情况呢？

4542 0

数学证明和计算机程序等同的深层链接

整数类型的数字 7 可以写为“7:整数”。你可以有一个函数，该函数获取类型 A 的对象并吐出 B 类型的对象，或者将一对类型 A 和类型 B 的对象组合成一个名为“A × B”的新类型。...当一个函数“栖居”在一个类型时——也就是说，当你能够成功地定义一个函数是该类型的对象时——你有效地表明相应的命题是正确的。...因此，接受类型 A 的输入并给出类型 B 的输出（表示为 A → B）的函数必须对应于一个蕴含：“如果 A，那么 B。”例如，假设“如果下雨，那么地面是湿的。”...在类型论中，这个命题将由“下雨 → 地面是湿的”的函数建模。外观不同的公式实际上在数学上是相同的。...这些是有助于构建形式证明的软件工具，例如Coq和Lean。在Coq中，证明的每一步本质上都是一个程序，证明的有效性通过类型检查算法进行检查。

1401 0

数据结构 | 每日一练（92）

试证明：若借助栈由输入序列 1,2,…,n 得到输出序列为 P 1 ,P 2 ,…,P n （它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着 i<j<k,使 P j <P k <P...（2）能否得到输出顺序为 154623 的序列。 3. （1）什么是递归程序？（2）递归程序的优、缺点是什么？（3）递归程序在执行时，应借助于什么来完成？...（2）递归程序的优点是程序结构简单、清晰，易证明其正确性。缺点是执行中占内存空间较多，运行效率低。（3）递归程序执行中需借助栈这种数据结构来实现。...（4）递归程序的入口语句和出口语句一般用条件判断语句来实现。递归程序由基本项和归纳项组成。...基本项是递归程序出口，即不再递归即可求出结果的部分；归纳项是将原来问题化成简单的且与原来形式一样的问题，即向着“基本项”发展，最终“到达”基本项。

87131 29

资源 | 谷歌与MIT联袂巨著：《计算机科学的数学》开放下载

而这些统计学概念和模型却又正好是机器学习的方法基础。...下面让我们一起来看看该书的章节目录： I 数学分析（Proofs）简介（Introduction） 0.1 参考文献（References） 1 什么是证明？（What is a Proof?）...（References） 4 数学上的数据类型（Mathematical Data Types） 4.1 集合（Sets） 4.2 序列（Sequences） 4.3 函数（Functions） 4.4...字符串（Strings of Matched Brackets） 7.3 非负整数递归函数（Recursive Functions on Nonnegative Integers） 7.4 算术表达式...使用母函数进行计数（Counting with Generating Functions） 16.3 部分分式（Partial Fractions） 16.4 求解线性递归（Solving Linear

1.4K7 0

理性的光辉，“哥德尔不完备定理”到底说了些什么？

可是，当哥德尔的证明也构造出了类似悖论的命题之后，人们宁可接受这个命题是不可证明的，也没有试图通过修补公理体系来解决这个问题。...且哥德尔所构造的命题是一条算术命题，恰恰是这个算术命题在PM中是不可证的。...定理二的证明思路：这个定理的证明相对容易，哥德尔构造了三个简单的原始递归函数α（x）、β（x，y）和γ（x，y），分别对应着“逻辑非”、“逻辑或”和“逻辑与”，如果R和S是两个原始递归的PM公式，那么它们必然对应着两个原始递归的函数...最后再强调一下，哥德尔构造出来的是一个算术命题（也可以说是一个数论命题或者一个函数关系式），只不过它对应的含义是“自身不可证”，从这个含义出发，我们确定了它不可证明，并不是说这个算术命题表面上的意思是自己不可证明...我们前面说过，哥德尔不完备定理是通过构造出一个不可证的算术命题来证明的。可是，作为已经修炼到第五重神功的我们，清楚的知道，哥德尔构造的这个算术命题我们几乎不可能直接的表达出来，因为太复杂、做不到。

2K3 0

递归算法时间复杂度分析

---- 2、代入法代入法实质上就是数学归纳法，因此求递推式分为两步：猜测解的形式；用数学归纳法求出解中的常数，并证明解是正确的。 ...遗憾的是并不存在通用的方法来猜测递归式的正确解，需要凭借经验，偶尔还需要创造力。即使猜出了递归式解的渐近界，也有可能在数学归纳证明时莫名其妙的失败。...定理4.1(主定理) 令a≥1和b>1是常数，f(n)f(n)是一个函数，T(n)T(n)是定义在非负整数上的递归式： T(n)=aT(n/b)+f(n)T(n)=aT(n/b)+f(n) 其中我们将...最后给出主定理应用的几个练习题：具体举例分析：【代入法】代入法首先要对这个问题的时间复杂度做出预测，然后将预测带入原来的递归方程，如果没有出现矛盾，则是可能的解，最后用数学归纳法证明。　　...接下来，我们要求解该方程的对应非齐次方程组的通解，这里我们针对该方程的特殊形式，不加证明地给出如下的通解形式：　　则和线性代数中的解一样，原方程的解等于齐次方程组的通解+特解，即：　　最后由初始条件确定

1.8K2 0

编码技巧

递归控制如何证明递归函数正确执行？...数学归纳法中的数学/自然语言程序语言递归书写方法严格定义递归函数作用，包括参数，返回值，Side-effct 先一般，后特殊每次调用必须缩小问题规模每次问题规模缩小程度必须为1 链表创建...循环控制递归 --> 非递归一般化的方法仍需要使用栈代码复杂，不根本解决问题 Node CreateLinkedList(List values) 循环不变式（loop invariant...）是一句断言定义各变量所满足的条件 Var a, b； While(){ } 循环书写方法定义循环不变式，并在循环体每次结束后保持循环不变式先一般，后特殊每次必须向前推进循环不变式中涉及的变量值...--复杂，面试一般不出算法题深度优先遍历广度优先遍历拓扑排序最短路径/最小生成树数学归纳法 -- 用在编码上用于证明断言对所有自然数成立证明对于N=1成立证明N>1时：如果对于N-1成立

4034 1

2020-07-02

递归控制如何证明递归函数正确执行？...数学归纳法中的数学/自然语言程序语言递归书写方法严格定义递归函数作用，包括参数，返回值，Side-effct 先一般，后特殊每次调用必须缩小问题规模每次问题规模缩小程度必须为1 链表创建...循环控制递归 --> 非递归一般化的方法仍需要使用栈代码复杂，不根本解决问题 Node CreateLinkedList(List values) 循环不变式（loop invariant...）是一句断言定义各变量所满足的条件 Var a, b； While(){ } 循环书写方法定义循环不变式，并在循环体每次结束后保持循环不变式先一般，后特殊每次必须向前推进循环不变式中涉及的变量值...--复杂，面试一般不出算法题深度优先遍历广度优先遍历拓扑排序最短路径/最小生成树数学归纳法 -- 用在编码上用于证明断言对所有自然数成立证明对于N=1成立证明N>1时：如果对于N-1成立

2192 0

顶会最佳论文覆灭科学家们30多年期待：复杂度远超预期

克雷西发自凹非寺量子位 | 公众号 QbitAI 三十多年来，在线算法一直被科学家寄予厚望，但一篇论文的诞生让它走下了神坛。...复杂度远超预期注：本节中的对数符号log，如无特别说明，底数为2 递归构建图度量空间为了探究k-server问题的复杂度，作者构建了一个递归定义的图度量空间（本质上也是k-server问题）。...之后，作者证明了在这个特殊构造的度量空间和请求序列上,任何确定性在线算法的预期消耗最低也要达到Ω(log²)。而具体的证明，则采用了数学归纳法。...数学归纳法数学归纳法虽然名字里有个归纳，实质上却是一种严谨的演绎推理。它首先验证结论针对序列中的第一项是否成立，然后假设对第k项也成立，接着，只要能证明对第k+1项也成立，结论就可以得到证明。...当k足够大时，log²k显然大于logk，因此在这样的k-server问题中，实现O(logk)级别的低消耗是不可能的。

1161 0

5.5 广义表的递归算法

01 广义表 1、递归函数结构清晰、程序易读，且容易证明正确性，因此是程序设计的有力工具。 2、有时递归函数的执行效率很低，因此使用递归应该扬长避短。在程序设计中，不应该一味追求递归。...3、如果一个问题的求解过程有明显的递推规律，我们也很容易写出它的递推过程，则不必要使用递归。 4、以广义表为例，如何利用分治法进行递归算法设计。...通常可以先写出问题求解的递归定义，和第二数学归纳法类似，递归定义由基本项和归纳项两部分组成。 5、递归定义的基本项描述了一个或几个递归过程的终结状态。...6、广义表的深度定义为广义表中括弧的重数，是广义表的一种量度。 7、任何一个非空广义表均可分解成表头和表尾，反之，一对确定的表头和表尾可唯一确定一个广义表。...如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！

59330 29

【计算理论】图灵机 ( 图灵机引入 | 公理化 | 希尔伯特纲领 | 哥德尔不完备定理 | 原始递归函数 )

可判定性 : 存在一个算法 , 可以帮助我们判定任何一个命题是真命题还是假命题 ; 四、哥德尔不完备定理 ---- 哥德尔否证明了上述希尔伯特纲领不可能实现 , 提出了哥德尔不完备定理 , 否定上述命题需要对算法提出严格的数学定义...; 整个数学不可能有一个完美牢固的基础 ; 哥德尔不完备定理指出推理的方法有很大的局限性 , 不是万能的 ; 中学算法很多都可以通过推理证明计算实现 ; 五、哥德尔原始递归函数 ----...原始递归函数是由哥德尔提出的 , 该函数定义在自然数集上 , 如下 : \rm \begin{cases} \rm h (0, y) = f(y) \\\\ \rm h(x + 1 , y) =...g(x, h(x,y) , y) \\ \end{cases} \rm f , g 这两个函数是已知的 , 根据这两个已知函数 , 定义一个新的函数 \rm h , \rm h 是二元函数 ,...0 , 定义该分量值 , 使用递归方法定义 , 根据 \rm h 在 \rm x , y 上的值 , 定义 \rm h 的第一个分量是 \rm x + 1 时的值 , 类似于数学归纳法思想

7560 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭