Доказательство прекращения функции Такеучи в Изабель

Question

Вот моя попытка доказать, что функция Takeuchi действительно завершается:

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) )"

Здесь есть несколько проблем. Сначала я должен вернуть тройку в функцию Мура. Прямо сейчас система жалуется с ошибкой:

Ошибка объединения типов: столкновение типов "int" и "_ ⇒ _"

Ошибка типа в приложении: несовместимый тип операнда

Оператор: op ≤ x:: (int ⇒ int ⇒ int) ⇒ bool Операнд: y:: int

Тогда, конечно, доказательство завершения не удастся, так как я не применил функцию завершения выше (путь к этому должен быть подобен здесь).

Как я могу это исправить?

Answer 1

Прежде всего, ваш moore функция в настоящее время не возвращает тройной, а функция, принимающая два intи возвращая int, Для тройки вам придется написать int × int × int, Кроме того, кортежи построены как (x, y, z)не как x y z как ты.

Также нет причин использовать fun (не говоря уже о function) определить moore функция, так как она не является рекурсивной. definition работает отлично. За tk, с другой стороны, вам нужно будет использовать function Поскольку нет очевидной лексикографической меры прекращения.

Кроме того, функции, возвращающие тройку, обычно немного уродливы в Изабель; более разумно определить три отдельные функции. Собрав все это вместе, вы можете определить свои функции следующим образом:

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 функция с использованием правила частичной индукции 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)

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,