竹内関数

竹内関数（たけうちかんすう）とは三つの整数 x, y, z に対して、次のように再帰的に定義される関数である。

${\rm {Tak}}(x,y,z)={\begin{cases}y&{\mbox{ if }}x\leq y\\{\rm {Tak}}({\rm {Tak}}(x-1,y,z),{\rm {Tak}}(y-1,z,x),{\rm {Tak}}(z-1,x,y))&{\mbox{ otherwise. }}\\\end{cases}}$

定義からわかるように処理を次々にたらいまわしにしていくことから、たらいまわし関数、たらい関数(Tarai function)とも呼ばれる（後述のマッカーシー版との混同を避けるためこの名で呼ばれることのほうが多いが、こちらの定義のほうがオリジナルである）。電電公社研究員（当時）の竹内郁雄が1976年に考案した。与える数によって関数の再帰呼び出しの回数が非常に増え、計算量が大きくなるため、コンピュータの性能測定などに用いられる。

マッカーシー版

ジョン・マッカーシーは竹内関数を記憶違いで z を返すように変更し、これがTak関数として広まった。以下がその定義である。

${\rm {Tak}}(x,y,z)={\begin{cases}z&{\mbox{ if }}x\leq y\\{\rm {Tak}}({\rm {Tak}}(x-1,y,z),{\rm {Tak}}(y-1,z,x),{\rm {Tak}}(z-1,x,y))&{\mbox{ otherwise. }}\\\end{cases}}$

本質

竹内関数の出力は以下のものと同等である。

${\rm {Tak0}}(x,y,z)={\begin{cases}y&{\mbox{ if }}x\leq y\\z&{\mbox{ if }}x>y{\mbox{ and }}y\leq z\\x&{\mbox{ otherwise. }}\\\end{cases}}$

高速化

竹内関数を高速化するには関数の再帰呼び出しのコストを小さくする必要がある。これには次のような手法がある。

• メモ化

一度計算した値を覚えておき、次の呼び出しではその値を使う。

• 遅延評価

クロージャなどを利用してその場では関数を計算しない（ただし、クロージャ生成のコストがかかる）。原則として遅延評価する言語であるHaskellでは定義そのままで非常に速い。

関連項目

• アッカーマン関数

外部リンク

• TAK Function
• Wolfram MathWorld
• どう転んでもLisp - スライド10〜13に作者自身の解説がある
• 東京大学 竹内郁雄研究室