标签: proof

我写了一小部分Haskell来弄清楚GHC如何证明对于自然数,你只能将偶数的一半:

{-# LANGUAGE DataKinds, GADTs, KindSignatures, TypeFamilies #-}
module Nat where

data Nat = Z | S Nat

data Parity = Even | Odd

type family Flip (x :: Parity) :: Parity where
  Flip Even = Odd
  Flip Odd  = Even

data ParNat :: Parity -> * where
  PZ :: ParNat Even
  PS :: (x ~ Flip y, y ~ Flip x) => ParNat x -> ParNat (Flip x)

halve :: ParNat Even -> Nat
halve PZ     = Z
halve …

我看到了这个问题,并对抽取引理是什么感到好奇(维基百科没有多大帮助).

我理解这基本上是一个理论证明,必须是真实的,以便语言在某个类中,但除此之外,我并没有真正得到它.

有人试图以非数学家/ comp sci博士学位理解的方式在相当精细的层面上解释它吗？

众所周知,应用函子在组合下是封闭的,但是monad不是.但是,我一直难以找到一个具体的反例,表明monad并不总是构成.

这个答案给出[String -> a]了一个非monad的例子.在玩了一下之后,我直觉地相信它,但是这个答案只是说"加入无法实现"而没有给出任何理由.我想要更正式的东西.当然有很多类型的函数[String -> [String -> a]] -> [String -> a]; 必须表明任何这样的功能必然不符合monad法则.

任何例子(附带证据)都可以; 我不一定特别想要证明上述例子.

最近在惠普实验室的Vinay Deolalikar周围发表了一篇论文,声称已证明P!= NP.

有人可以解释一下这个证明对我们这个数学上不那么倾向的人有用吗？

为什么计算机程序不能像数学陈述那样被证明？一个数学证明是建立在其他证明之上的,这些证据是从更多的证据和公理中建立起来的 - 我们认为这些真理是真实的.

计算机程序似乎没有这样的结构.如果您编写计算机程序,那么您如何能够获取以前经过验证的作品并使用它们来展示您的计划的真实性？你不能存在.此外,编程的公理是什么？这个领域的原子真理？

我对上面的内容没有很好的答案.但似乎软件无法被证明,因为它是艺术,而不是科学.你如何证明毕加索？

总(功能)语言是可以显示所有内容终止的语言.显然,有很多地方我不想要这个 - 抛出异常有时很方便,Web服务器不应该终止等等.但有时候,我希望进行本地整体检查以启用某些优化.例如,如果我有一个可证明的全部功能

commutativity :: forall (n :: Nat) (m :: Nat). n + m :~: m + n
commutativity = ...

然后,由于:~:只有一个居民(Refl),GHC可以优化

gcastWith (commutativity @n @m) someExpression
  ==>
someExpression

我的可交换性证明从O(n)运行时成本到免费.那么,现在我的问题:

为Haskell制作总体检查器有哪些微妙的困难？

显然,这样的检查是保守的,所以每当GHC不确定某些东西是完全的(或者是懒得检查)时,它可能会认为它不是......在我看来,拼凑一个不是 - 可能并不太难如此智能的检查器仍然非常有用(至少它应该是直截了当地消除我所有的算术证明).然而,我似乎无法找到任何努力在GHC中构建这样的东西,所以显然我错过了一些非常大的限制.来吧,粉碎我的梦想.:)

相关但不是最近的:2005年尼尔米切尔解散Haskell.

如何通过Haskell 为自然演绎证明树(如此处所示)创建LaTeX源,例如使用HaTeX？我想模仿LaTeX,.sty比如bussproofs.sty或proof.sty.

我从气泡排序算法的数据结构书中得到了这个公式.

我知道我们是(n-1)*(n次),但为什么除以2？

任何人都可以向我解释这个或给出详细的证据.

谢谢

我可能会说我对Code Contracts非常熟悉:我已经阅读并理解了大部分用户手册,并且已经使用了很长一段时间了,但我仍然有疑问.当我搜索SO代码"未经证实的代码合同"时,有很多点击,都在问为什么他们的具体陈述无法被静态证明.虽然我可以做同样的事情并发布我的具体情况(这是顺便说一句:

)

我更愿意理解为什么任何代码合同条件可以或不可以证明.有时我对它能证明的东西印象深刻,有时我......嗯......礼貌地说:绝对没有留下深刻的印象.如果我想了解这一点,我想知道静态检查器使用的机制.我相信我会从经验中学习,但我会在Contract.Assume所有地方喷洒语句以使警告消失,我觉得这不是Code Contracts的意思.谷歌搜索没有帮助我,所以我想问你们你们的经历:你们看到了什么(不明显的)模式？是什么让你看到光明？

有谁知道以下任何例子？

1. 关于证明助理(例如Coq)中正则表达式(可能通过反向引用扩展)的证据开发.
2. 关于正则表达式的依赖类型语言(例如Agda)中的程序.