589(3): デフォルトの名無しさん [sage] 2018/06/18(月) 18:04:53.53 ID:xdRdwSco(1/4) AAS
>>578
とある関数呼び出しの定義内に表れる再帰的呼び出しの
停止性マトリクスが、大元の関数呼び出しの停止性マトリクスから辞書順で下降していくことから停止性を担保しようというのが停止性マトリクスの意味。

そして停止性マトリクスの記述に表れる n は issven や isodd の引数そのものだということに注意

iseven、isodd の停止性マトリクスがそれぞれ n、n+1 だと、

iseven n の停止性マトリクス→n
iseven n の定義に出てくる isodd (n-1) の停止性マトリクス→n-1+1=n
減っていないから停止性が担保されない(NG)。

説明にあるように <n, 0> と <n,1> ならば、
iseven n の停止性マトリクス→<n,0>
iseven n の定義に出てくる isodd (n-1) の停止性マトリクス→<n-1,1> (下降している！OK)
isodd も同様に
isodd n の停止性マトリクス→<n,1>
isodd n の定義に出てくる iseven (n) の停止性マトリクス→<n,1> (下降している！OK)

そして<n,0 <n,1> の代わりに n*2, n*2+1 を使っている(この代用が可能なことはわかるよね)。

596(1): デフォルトの名無しさん [sage] 2018/06/18(月) 19:23:14.64 ID:xdRdwSco(4/4) AAS
>>595
＞すまない。俺はバカなんだ。分からないんで教えて下さい。

辞書順を保ったまま <n, 0 <n,1> をそれぞれ 2*n, 2*n+1 で置き換えられる
3*nとか4nでもいいけど2つしかないから2nで十分

例

fun f
{n:nat} .<3*n>.
(n: int n) : bool =
if n = 0 then true else g (n-1)
and g
{n:nat} .<3*n+2>.
(n: int n) : bool = not (h (n))
and h
{n:nat} .<3*n+1>.
(n: int n) : bool = not (f (n))

605(1): デフォルトの名無しさん [sage] 2018/06/18(月) 22:18:33.96 ID:ejyTxCd5(1/3) AAS
>>604
いやここで堪えて理解しておくべき。
引数から算出できて、再帰で減るものを何か考えてそれを停止性マトリクスとする。

値そのものじゃなく大小関係だけが大事だから、
m が 0 と 1 のどちらかしかなければ
<n, m> の代わりに n*2+m で ok ってこと

例
<5,0> は <4,1> より大 ⇔ 5*2+0 は 4*2+1 より大