マッカーシー版
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/11/19 10:16 UTC 版)
ジョン・マッカーシーは竹内関数を記憶違いで 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 回しか呼ばれない)。
※この「マッカーシー版」の解説は、「竹内関数」の解説の一部です。
「マッカーシー版」を含む「竹内関数」の記事については、「竹内関数」の概要を参照ください。
- マッカーシー版のページへのリンク