equal
deleted
inserted
replaced
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. |