日本語プログラミング言語Mindの小技 「リカーシブコール」たらい回し関数

Mindでもリカーシブコール

Mind でも他のプログラミング言語と同様に、リカーシブコール（再帰呼び出し）が使えます。
リカーシブコールとして有名（？）な、竹内 郁雄先生の「たらい回し関数」をMindでプログラミングし実行してみました。

実行時の注意

各プログラミング言語で実装・実行可能ですが、x,y,z の値によっては　呼び出し回数が膨大になります。
f(2,1,0)で9回、f(4,2,0)で53回、f(6,3,0)で673回、f(8,4,0)で12,605回、f(10,5,0) で343,073回、f(12,6,0)で12,604,861回、f(14,7,0)で588,802,013回
でした。

たらい回し関数の停止性とその値

「たらい回し関数」は、
たらい回し関数f(x,y,z)：x,y,z は整数 の定義
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のとき

たらい回し関数f(x,y,z)が　任意の整数x,y,zで停止し
ある簡単な関数g(x,y,z)があり。（g は再帰表現なしで記述できます）
f(x,y,z)＝g(x,y,z)である。
を証明するのは、結構たいへんです。
いくつか証明がありますが私の証明は、２重の数学的帰納法を使い、40行ぐらいです。
みなさんも　g(x,y,z)を見つけて（できれば証明の概略も）コメントに書き込んでください。

大昔、数学セミナーの「エレガントな解答を求む」で出題されましたが、証明は掲載されませんでした。
次回は、g(x,y,z)と停止性の証明を掲載したいと思います。

Mind プログラム

たらい回しとは
      ｘは  変数
      ｙは  変数
      ｚは  変数
      ｘと  ｙと  ｚに  入れ
      ｘが  ｙ  以下  
            ならば  ｙを  返し
　　　　　 　さもなければ
                  ［ｘ － １］と  ｙと  ｚを  たらい回し
　　　　　　　　　　［ｙ － １］と  ｚと  ｘを  たらい回し
　　　　　　　　　　［ｚ － １］と  ｘと  ｙを  たらい回し
　　　　　　　　　　たらい回しし  返す 
　　　　　　つぎに。
メインは 
     ixは　変数
     iyは　変数
     izは　変数
	起動引数個数が　3と　等しい
　　　　ならば
  		    起動引数(1)を 数値変換し　捨て　ixに　入れる
	 	    起動引数(2)を 数値変換し　捨て　iyに　入れる
 		    起動引数(3)を 数値変換し　捨て　izに　入れる
　　　　    「たらい回し開始します。」と　表示し　改行し　
		    ixと　iyと　izとを　たらい回し  数値表示する
　　　　    「です。」と　表示し　改行する
       さもなければ
　　　　　  「起動引数個数は３個です。」と　表示し　改行する
　　　　つぎに。

実行結果

c:\mind8\pmind\sample>taraimawashi 1 2 3
たらい回し開始します。
2です。
c:\mind8\pmind\sample>taraimawashi 15 10 6
たらい回し開始します。
15です。