问题标签 [proof]

我们有 2 种语言（非正式地）在语义上是等价的，但在语法上是不同的。一个是xml，另一个是基于脚本的。我怎样才能正式证明这两种语言实际上是等价的。脚本方法只是编写相同程序的便捷方式，而用 xml 编写会很乏味。

谢谢科坦

我阅读 RWH 失败；没有人要退出，我订购了 Haskell: The Craft of Functional Programming。现在我对第 146 页上的这些功能证明感到好奇。具体来说，我正在尝试证明 8.5.1 sum (reverse xs) = sum xs。我可以做一些归纳证明，但后来我被卡住了..

炒作：

根据：

就职：

所以现在我只是想证明它Left sum ( reverse xs ++ [x] )等于Right x + sum xs，但这与我开始的地方并不太远sum ( reverse (x:xs) ) = sum (x:xs)。

我不太确定为什么需要证明这一点，使用reverse x:y:z = z:y:x(by defn) 的符号证明似乎完全合理，因为 + 是可交换的 (arth) then reverse 1+2+3 = 3+2+1，

最近，HP 实验室的 Vinay Deolalikar 发表了一篇论文，声称证明了P != NP。

有人能解释一下这个证明如何适用于我们不太喜欢数学的人吗？

从我读过的关于 cpython 的内容来看，它似乎确实引用计数 + 一些额外的东西来检测/释放指向彼此的对象。（如果我错了，请纠正我）。有人可以解释一下额外的东西吗？这也保证*没有循环泄漏吗？如果没有，是否有任何研究证明可以添加到引用计数以使其永不泄漏*的算法？这会只是经常运行非引用计数跟踪 gc 吗？

*折扣使用外部函数接口的模块的错误和问题

我知道关系 n = Big-O(1) 是错误的。但是如果我们使用涉及 Big-O 的归纳法，它可以被证明。但谬误是我们不能引入 Big-O。但我的问题是我们如何通过使用常数来反驳这种关系。

错误的证明就在这里，请使用常量给我证明它是错误的。我对常数感到困惑，我不知道证明中使用的每个关系是否具有不同的常数或相同的常数。请指教主题。

归纳假设：让它为真：n-1 = O(1) 现在我们证明 n = O(1)

错误地证明了.. 我想澄清 <= 和常量方面的谬误，即 Big-O 的基本定义。

我目前正在阅读一本算法的书，遇到了稳定匹配问题。我想到了一个我很好奇的问题，但这本书没有回答。在每个 SMP 中，是否总是有一对最喜欢另一对？就像在经典的婚姻例子中一样。是否总是有一对一女一男，并且彼此都在自己的偏好中排名靠前？

我将证明以下示例：

值得注意的是，多项式函数比指数函数增长得更快。我们试图找到满足条件的 k0 > 0

比

所以，k0 > 0，正且足够小，而c的值无关紧要……可以吗？

在我的算法分析课程中，我从算法推导出函数 f(n) = n^2 - n + 2。现在我需要证明或反驳f(n) ∈ O(n)。显然不是，所以我一直试图反驳这一点几个小时，但不知道该怎么做。

为了反驳它，我需要证明否定：

我试过前后工作，但似乎无处可去。我还试图证明，根据我的判断，f(n) ∈ O(n)：

...没有成功。我在做什么如此可怕的错误？

是否有可能通过归纳证明，对于所有长度为 n 的序列，任何 0 字符串的二进制补码总是会导致 0？

我正在尝试使用价值公式来做到这一点，即

值 = -a_n-1 x 2^(n-1) + summation{i=0 to n} (a_i x 2^i)，其中 n = 字符串中的位数

我试图通过归纳证明以下内容：

这是算法类的问题。我在想我可以做我通常对求和所做的事情，即假设它适用于某些 P(m)，然后增加 P(m+1) 的总和并通过在右侧添加额外的内容来向后工作左边的总和产生。

但是，这个问题是不同的，因为替换 H+1 会改变总和中的每个术语......所以我认为这种技术不会奏效。

这是一个家庭作业问题......所以我显然不期待一个完整的解决方案。但是，我不确定在哪里进行求和，所以我正在寻找其他方法进行归纳。