src/Doc/Tutorial/Advanced/WFrec.thy
changeset 69505 cc2d676d5395
parent 67406 23307fd33906
equal deleted inserted replaced
69504:bda7527ccf05 69505:cc2d676d5395
     3 text\<open>\noindent
     3 text\<open>\noindent
     4 So far, all recursive definitions were shown to terminate via measure
     4 So far, all recursive definitions were shown to terminate via measure
     5 functions. Sometimes this can be inconvenient or
     5 functions. Sometimes this can be inconvenient or
     6 impossible. Fortunately, \isacommand{recdef} supports much more
     6 impossible. Fortunately, \isacommand{recdef} supports much more
     7 general definitions. For example, termination of Ackermann's function
     7 general definitions. For example, termination of Ackermann's function
     8 can be shown by means of the \rmindex{lexicographic product} @{text"<*lex*>"}:
     8 can be shown by means of the \rmindex{lexicographic product} \<open><*lex*>\<close>:
     9 \<close>
     9 \<close>
    10 
    10 
    11 consts ack :: "nat\<times>nat \<Rightarrow> nat"
    11 consts ack :: "nat\<times>nat \<Rightarrow> nat"
    12 recdef ack "measure(\<lambda>m. m) <*lex*> measure(\<lambda>n. n)"
    12 recdef ack "measure(\<lambda>m. m) <*lex*> measure(\<lambda>n. n)"
    13   "ack(0,n)         = Suc n"
    13   "ack(0,n)         = Suc n"
   106 "g i = (if 10 \<le> i then 0 else i * g(Suc i))"
   106 "g i = (if 10 \<le> i then 0 else i * g(Suc i))"
   107 (*>*)
   107 (*>*)
   108 (hints recdef_wf: wf_greater)
   108 (hints recdef_wf: wf_greater)
   109 
   109 
   110 text\<open>\noindent
   110 text\<open>\noindent
   111 Alternatively, we could have given @{text "measure (\<lambda>k::nat. 10-k)"} for the
   111 Alternatively, we could have given \<open>measure (\<lambda>k::nat. 10-k)\<close> for the
   112 well-founded relation in our \isacommand{recdef}.  However, the arithmetic
   112 well-founded relation in our \isacommand{recdef}.  However, the arithmetic
   113 goal in the lemma above would have arisen instead in the \isacommand{recdef}
   113 goal in the lemma above would have arisen instead in the \isacommand{recdef}
   114 termination proof, where we have less control.  A tailor-made termination
   114 termination proof, where we have less control.  A tailor-made termination
   115 relation makes even more sense when it can be used in several function
   115 relation makes even more sense when it can be used in several function
   116 declarations.
   116 declarations.