- 596 名前：デフォルトの名無しさん mailto:sage [2018/06/18(月) 18:04:53.53 ID:xdRdwSco.net]
- >>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 を使っている(この代用が可能なことはわかるよね)。
|
 |
