たらいまわし関数 - kururu

d.y.d. 14:45 06/05/01
たらいまわし関数の停止性 - yoriyukiの日記

うーん、普通に証明できそうなんですが。何か私が変な勘違いをしているんでしょうか？計算理論はちゃんと知らないので…。関数型言語とか何も知らないし。
気になって証明を書いてみたので、ツッコミがありましたらよろしくお願いします。超限帰納法ではなく、普通の数学的帰納法です。

(証明開始)
示したいのは、

f(x, y, z)= if x<=y then y else f(f(x-1, y, z), f(y-1, z, x), f(z-1, x, y))

で定義されるfが全ての整数x, y, zに対して停止し、値としては

f(x, y, z)= if x<=y then y else if y<=z then z else x

となること。

まず最初にx, y, zが全て自然数だと仮定してよいことを観察(k.inabaさんのところ参照)。
というわけで、全ての自然数の組x, y, zに対して上記の式が成り立つことを、n=max(x, y, z)についての帰納法で示す。

まずnが0のときは、f(0, 0, 0)=0なので問題なし。
全ての自然数の組x, y, zでmax(x, y, z)<=nを満たすものについて上記の式が成り立つことを仮定する。このときに、max(x, y, z)=n+1を満たすような組について成り立つことを示す。

Case 1. y=n+1
x<=n+1=yなので、f(x, n+1, z)=n+1

Case 2. y<=n かつ z=n+1
このケースに関しては、yを固定してxに対する帰納法で示す。
もし、x<=yならば、f(x, y, n+1)=yなので成り立つ。
x=y+1ならば、
$\begin{eqnarray}f(y+1, y, n+1)&=&f(f(y, y, n+1), f(y, n+1, y+1), f(n, y+1, y))\\&=&f(y, n+1, f(n, y+1, y))=n+1\end{eqnarray}$
となるので成り立つ。
f(n, y+1, y)は帰納法の仮定またはCase 1.で処理されていることに注意。

y+1Case 3. y<=n かつ z<=n かつ x=n+1

$\begin{eqnarray}f(n+1, y, z)&=&f(f(n, y, z), f(y-1, z, n+1), f(z-1, n+1, y))\\&=&f(f(n, y, z), f(y-1, z, n+1), n+1)\end{eqnarray}$
Case 2. により

f(f(n, y, z), f(y-1, z, n+1), n+1)=if f(n, y, z)<=f(y-1, z, n+1) then f(y-1, z, n+1)
else n+1

なお、yが0の場合にはy-1が-1になってf(y-1, z, n+1)が帰納法の仮定からはみ出すが、y-1<0<=zなのでf(y-1, z, n+1)=zとなるので問題ない。

Subcase 3.1. y-1>z
明らかにf(y-1, z, n+1)=n+1>f(n, y, z)。
よってf(n+1, y, z)=n+1

Subcase 3.2. y-1=z
f(y-1, z, n+1)=z。帰納法の仮定よりf(n, y, z)=y or n。
もしz=nならば、y=z+1=n+1となり仮定に反する。よって、zSubcase 3.3. y<=z
f(y-1, z, n+1)=z。帰納法の仮定よりf(n, y, z)=y or z
どちらにしても、f(n, y, z)<=f(y-1, z, n+1)。よってf(n, y, z)=z。
(証明終了)

ちょっと簡略化する工夫はしましたが、基本的にはf(x, y, n+1)とf(n+1, y, z)を真面目に計算して場合分けしているだけです。