竹内関数の停止性を示します。
AI が得意な方は、AIに証明させてみるのもおもしろいかも知れません。
タイポや論理ミスがあるかも知れません。お気づきの点や疑問点があればコメントお待ちしています。
竹内関数
f(x,y,z)= y: x≦yのとき
= f(f(x-1,y,z),f(y-1,z,x),f(z-1,x,y)):x＞yのとき
x,y,z は整数
竹内関数と等価な関数
g(x,y,z)= y: x≦yのとき
= z: x＞yかつy≦zのとき
= x: x＞yかつy＞zのとき
任意の整数x,y,zについて f(x,y,z) は停止し,f(x,y,z)＝g(x,y,z)である。
少し書き換えると、任意の実数x,y,zで成り立つことが示せます。次回はそれを載せます。
証明
d(x,y,z)=x-y+|y-z| とおいて、d(x,y,z)に関する数学的帰納法で証明する。
（Base Step)
d(x,y,z)≦0のとき,x≦y
よってf,gの定義より f(x,y,z)=y=g(x,y,z)
（Inductive Step)
（仮定A)ある0以上の整数kについて d(x,y,z)≦kならばf(x,y,z)=y=g(x,y,z)と仮定する。
d(x,y,z)=k+1なる任意のx,y,zをとる。
x≦yのとき 定義より f(x,y,z)=y=g(x,y,z)
x＞yのとき
定義より f(x,y,z)=f(f(x-1,y,z),f(y-1,z,x),f(z-1,x,y))
右辺の各項を順に評価する。
(1)d(x-1,y,z)=k,よって(仮定A)よりf(x-1,y,z)=g(x-1,y,z)
(2)-a y-1≦zのとき f(y-1,z,x)=z=g(y-1,z,x)
(2)-b y-1＞zのとき
d(x,y,z)=x-z=k+1である。
また、このとき、任意の自然数nについて f(z+n,z,x)=x…(ア）を示す。
(証明）nに関する数学的帰納法
(Base Step) n=1のとき
f(z+1,z,x)=f(f(z,z,x),f(z-1,x,z+1),f(x-1,z+1,z))
・f(z,z,x)=z
・z-1≦xなのでf(z-1,x,z+1)=x
・d(x-1,z+1,z)=x-z-1=kなので(仮定A)よりf(x-1,z+1,z)=g(x-1,z+1,z)
∴f(z+1,z,x)=f(z,x,g(x-1,z+1,z))=x
(Inductive Step) （仮定B)f(z+n,z,x)=xと仮定する。
f(z+n+1,z,x)=f(f(z+n,z,x),f(z-1,x,z+n+1),f(x-1,z+n+1,z))
・(仮定B)より,f(z+n,z,x)=x
・z-1≦xなので、f(z-1,x,z+n+1)=x
・d(x-1,z+n+1,z)=x-z-1=kなので(仮定A)よりf(x-1,z+n+1,z)=g(x-1,z+n+1,z)
∴ f(z+n+1,z,x)=f(x,x,g(x-1,z+n+1,z))=x
数学的帰納法により、任意の自然数nについて f(z+n,z,x)=x //
y-1=z+n(nは自然数）とおけるので
f(y-1,z,x)=f(z+n,z,x)
(ア）より=x=g(y-1,z,x)
(3)d(z-1,x,y)=z-1-x+|x-y|=z-1-x+x-y (∵x＞y)
=z-y-1=|z-y|-1≦k
よって(仮定A)より f(z-1,x,y)=g(z-1,x,y)
(1)(2)(3)より
f(x,y,z)=f(g(x-1,y,z),g(y-1,z,x),g(z-1,x,y))
(a)y≦zのとき
g(x-1,y,z)=y or z (≦z)
g(y-1,z,x)=z
∴f(x,y,z)=f( y or z,z,g(z-1,x,y))=z=g(x,y,z)
(b)y=z+1のとき
g(x-1,y,z)=x-1
g(y-1,z,x)=z
g(z-1,x,y)=x
∴f(x,y,z)=f(x-1,z,x)
x-1≧y＞zであるからx-1=z+n(nは自然数)とおけて
=f(z+n,z,x)
(ア）より=x=g(x,y,z)
(c)y＞z+1のとき
g(x-1,y,z)=x-1
g(y-1,z,x)=x
∴f(x,y,z)=f(x-1,x,g(z-1,x,y))=x=g(x,y,z)
(a)(b)(c)いずれの場合も,f(x,y,z)=g(x,y,z)がいえた。
以上から、数学的帰納法によりd(x,y,z)が任意の整数のときについて
f(x,y,z)=g(x,y,z)である。