竹内関数
再帰的に定義される、3個の引数 x, y, z をとる次のような関数である。
T a r a i ( x , y , z ) = { y if x ≤ y T a r a i ( T a r a i ( x − 1 , y , z ) , T a r a i ( y − 1 , z , x ) , T a r a i ( z − 1 , x , y ) ) otherwise. {\displaystyle {\rm {Tarai}}(x,y,z)={\begin{cases}y&{\mbox{ if }}x\leq y\\{\rm {Tarai}}({\rm {Tarai}}(x-1,y,z),{\rm {Tarai}}(y-1,z,x),{\rm {Tarai}}(z-1,x,y))&{\mbox{ otherwise. }}\\\end{cases}}}
特に変わる所は無いがLisp版も参照のこと。
ジョン・マッカーシーは竹内関数を記憶違いで z を返すように変更し、これがTak関数として広まった。以下がその定義である。
T a k ( x , y , z ) = { z if x ≤ y T a k ( T a k ( x − 1 , y , z ) , T a k ( y − 1 , z , x ) , T a k ( z − 1 , x , y ) ) otherwise. {\displaystyle {\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}}}
計算量はずっと少ない(たとえば tarai(12, 6, 0) では 12,604,860 回 tarai が呼ばれるのに対し、 tak(12, 6, 0) では tak は 63,608 回しか呼ばれない)。