证明 Isabelle 中 Takeuchi 函数的终止

Question

这是我尝试证明 Takeuchi function does terminate:

function moore :: "(int ⇒ int ⇒ int) ⇒ (int ⇒ int ⇒ int)" where
"moore x y z = ((if (x ≤ y) then 0  else 1) (max(x,y,z) - min(x,y,z)) (x - min(x,y,z)))"


fun tk :: "int ⇒ int ⇒ int ⇒ int" where
"tk x y z = ( if x ≤ y then y else tk (tk (x-1) y z) (tk (y-1) z x) (tk (z-1) x y) )"

这里有几个问题。首先，我应该 return 摩尔函数中的一个三元组。现在，系统报错：

Type unification failed: Clash of types "int" and "_ ⇒ _"

Type error in application: incompatible operand type

Operator: op ≤ x :: (int ⇒ int ⇒ int) ⇒ bool Operand: y :: int

那么，终止证明当然没有成功，因为我没有应用上面的终止函数（方法应该类似于）。

我该如何解决这个问题？

Answer 1

首先，您的 moore 函数目前不是 return 三元组，而是一个包含两个 int 和 return 一个 int 的函数.对于三元组，您必须编写 int × int × int。此外，元组构造为 (x, y, z)，而不是像您那样构造为 x y z。

此外，没有理由使用 fun（更不用说 function）来定义 moore 函数，因为它不是递归的。 definition 工作正常。另一方面，对于 tk，您将需要使用 function，因为没有明显的字典序终止措施。

此外，函数 return 三元组在 Isabelle 中处理起来通常有点难看；定义三个单独的函数更有意义。将所有这些放在一起，您就可以像这样定义您的函数：

definition m1 where "m1 = (λ(x,y,z). if x ≤ y then 0 else 1)"
definition m2 where "m2 = (λ(x,y,z). nat (Max {x, y, z} - Min {x, y, z}))"
definition m3 where "m3 = (λ(x,y,z). nat (x - Min {x, y, z}))"

function tk :: "int ⇒ int ⇒ int ⇒ int" where
  "tk x y z = ( if x ≤ y then y else tk (tk (x-1) y z) (tk (y-1) z x) (tk (z-1) x y))"
  by auto

然后您可以使用部分归纳规则 tk.pinduct:

轻松证明 tk 函数的部分正确性定理

lemma tk_altdef:
  assumes "tk_dom (x, y, z)"
  shows   "tk x y z = (if x ≤ y then y else if y ≤ z then z else x)"
  using assms by (induction rule: tk.pinduct) (simp_all add: tk.psimps)

tk_dom (x, y, z) 假设表明 tk 终止于值 (x, y, z)。

现在，如果我正确阅读了您链接的论文，终止证明的模板如下所示：

termination proof (relation "m1 <*mlex*> m2 <*mlex*> m3 <*mlex*> {}", goal_cases)
  case 1
  show "wf (m1 <*mlex*> m2 <*mlex*> m3 <*mlex*> {})"
    by (auto intro: wf_mlex)
next
  case (2 x y z)
  thus ?case sorry
next
  case (3 x y z)
  thus ?case sorry
next
  case (4 x y z)
  thus ?case sorry
next
  case (5 x y z)
  thus ?case sorry
qed

在此处的最后四种情况下，您将必须进行实际工作以显示度量值下降。 <*mlex*> 运算符将多个度量组合成一个字典序度量。显示该度量中包含某些内容的相关规则是 mlex_less 和 mlex_le.

证明 Isabelle 中 Takeuchi 函数的终止

Proving termination of Takeuchi function in Isabelle

termination

isabelle