|
\end{cases}</math>
定義からわかるように処理を次々に[[たらい回し]]にしていくことから、'''たらいまわし関数'''<ref>{{citeCite book | 1=和書 |author=奥村晴彦 |authorlink=奥村晴彦 |title=C言語による最新アルゴリズム事典 |year=1991 |publisher=[[技術評論社]] | author=奥村晴彦 | authorlink=奥村晴彦 | year=1991 | page=185 | isbn=4-87408-414-1 |page=185}}</ref>、'''たらい関数''' (''Tarai function'') とも呼ばれる（後述のマッカーシー版との混同を避けるためこの名で呼ばれることのほうが多いが、こちらの定義のほうがオリジナルである。マッカーシー版を特にTak関数として区別する場合もある）。[[日本電信電話公社|電電公社]]研究員（当時）の[[竹内郁雄]]が、1974年の夏前の頃、後述するような特性のある関数をあれこれ考えていた、ある日の午前に思いついたものである<ref>[{{Cite web |url=http://cybozushiki.cybozu.co.jp/articles/m000434.html |title=ハッカーの遺言状──竹内郁雄の徒然苔第18回：問題児も悪くない |accessdate=2016-3-7 |author=竹内 郁雄 |authorlink=竹内郁雄 |website=サイボウズ式] |language=ja}}</ref>。竹内関数と命名したのは[[野崎昭弘]]である<ref>[[{{Cite book |author=野崎昭弘]]『 |authorlink=野崎昭弘 |title=計算機数学』（ |year=1984 |publisher=[[共立出版]]、1984年）}}</ref>。
特性として、他のよくベンチマークに使われる関数と比較して、たとえば[[フィボナッチ数]]を何の工夫もなく計算するいわゆるダム（dumb）フィボナッチと比較して、計算量を増やしても、たいして大きな数の計算が必要ない（ワード長の整数演算さえ実装していれば十分）、再帰がたいして深くならない（たいした量のスタックを使えなくても十分）、といったものがある。このためベンチマークとしては、その処理系の関数呼び出し（と戻り）の[[オーバーヘッド]]に集中して結果が出ること、メモリの少ないハードウェアや多倍長計算がまだ無い処理系などのような実験的な環境でも実装し測定できること、といった特徴がある。
== マッカーシー版 ==
[[ジョン・マッカーシー]]は竹内関数を記憶違いで<ref>[{{Cite web |url=http://jp.franz.com/base/seminar/2005-11-18/SeminarNov2005-Takeuchi.htm |title=どう転んでもLisp |accessdate=2007-10-4 スライド|author=竹内郁雄 |authorlink=竹内郁雄 |page=12] |archiveurl=https://web.archive.org/web/20061211233610/http://jp.franz.com/base/seminar/2005-11-18/SeminarNov2005-Takeuchi.files/v3_document.htm |archivedate=2006-12-11 |deadlinkdate=2021-11-19}}</ref> ''z'' を返すように変更し、これが'''Tak関数'''として広まった。以下がその定義である。
<math>{\rm Tak}(x, y, z) = \begin{cases}
: [[クロージャ]]などを利用して、関数呼び出しの計算より前に引数を計算すること（[[先行評価]]）をしない（ただし、クロージャ生成のコストがかかる）。原則として遅延評価する言語である[[Haskell]]では定義そのままで非常に速い。他にも[[Scala]]など遅延評価に対応した言語においては、簡単に、非常に高速に評価が終わるコードを作成できる。
マッカーシー版は、メモ化では同様に速い。しかし、マッカーシー版をHaskellなどでそのままの定義で遅延評価した場合は、高速にならない（遅延評価では計算量が減らない）、という違いがある。これは少し動作を追いかけて考えてみるとわかるが、本物では z の値をたらいまわしした挙句に結局使っていない（捨ててしまっている）ため、遅延評価ではその計算がごっそり行われなくなるからである。マッカーシー版では z を返しているため結局その値が必要になっている、という違いになっている。先行評価による tarai(n, 0, n+1) の計算全体において「さもなくば」の側が評価される回数をTakeuchi Numberと言う<ref>[http{{Cite web |url=https://mathworld.wolfram.com/TakeuchiNumber.html Weisstein, Eric W. "|title=Takeuchi Number." From|accessdate=2015年6月22日 MathWorld--A|last=Weisstein Wolfram|first=Eric Web ResourceW. http://|website=mathworld.wolfram.com/TakeuchiNumber.html] |language=en}}</ref>。
== 感覚化 ==
数値データ等を視覚や聴覚でとらえられるようにすることがあるが（視覚の場合[[可視化]]という）、竹内関数の引数の値に音階を割り振り、3個の引数で和音のような音にした試みがある<ref>http{{Cite web |url=https://daike.hatenahatenablog.ne.jpcom/aikeentry/20111112 |title=竹内関数で音楽生成 |accessdate=2011-11-15 |author=aike |website=aike’s blog |language=ja}}</ref>。
== 参照 ==
| 