CODEWITHSUNDEEP
isabelletermination
user1868607
user1868607

Reputation: 2600

Proving termination of Takeuchi function in Isabelle

Here is my try at proving that 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) )"

there are several problems here. First I should return a triple in the function moore. Right now, the system is complaining with error:

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

Then, of course the termination proof does not succeed since I didn't apply the termination function above (the way to this should be similar to here).

How can I fix this?

Upvotes: 0

Views: 293

Answers (1)

Manuel Eberl
Manuel Eberl

Reputation: 8278

First of all, your moore function currently does not return a triple but a function taking two ints and returning an int. For a triple, you would have to write int × int × int. Also, tuples are constructed as (x, y, z), not as x y z like you did.

Also, there is no reason to use fun (let alone function) to define the moore function, since it is not recursive. definition works fine. For tk, on the other hand, you will need to use function since there is no obvious lexicographic termination measure.

Also, functions returning triple are usually a bit ugly to handle in Isabelle; it makes more sense to define three individual functions. Putting all this together, you can then define your functions like this:

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

You can then easily prove a partial correctness theorem for the tk function using the partial induction rule tk.pinduct:

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)

The tk_dom (x, y, z) assumption says that tk terminates on the values (x, y, z).

Now, if I read the paper you linked correctly, the template for the termination proof looks like this:

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

In the last four cases here, you will have to do the actual work of showing that the measure decreases. The <*mlex*> operator combines several measures into a single lexicographic measure. The relevant rules for showing that something is in contained in that measure are mlex_less and mlex_le.

Upvotes: 2

Related Questions