Takeuchi function


The Takeuchi function is a triply recursive 3-parameter function originally defined by Ichiro Takeuchi in 1978 as t⁢(x,y,z)=y if x≤y and t⁢(x,y,z)=t⁢(t⁢(x-1,y,z),t⁢(y-1,z,x),t⁢(z-1,x,y)) otherwise. Later John McCarthy simplified the definition of the function as t⁢(x,y,z)=y if x≤y, t⁢(x,y,z)=z if y≤z and t⁢(x,y,z)=x in all other cases.

For example, t⁢(194,13,5)=194 since 194 is not less than 13, and 13 is not less than 5. The return value of the function “is on no practical significance,” but the function itself “is useful for benchmark testing of programming languages.” (Finch, 2003) The function T⁢(x,y,z) is the number of times t calls itself to obtain the return value. A properly optimized implementation of the function in a given programming language should not require more recursion than T indicates.

References

  • 1 Steven R. Finch Mathematical Constants New York: Cambridge University Press (2003): 321
Title Takeuchi function
Canonical name TakeuchiFunction
Date of creation 2013-03-22 17:33:07
Last modified on 2013-03-22 17:33:07
Owner PrimeFan (13766)
Last modified by PrimeFan (13766)
Numerical id 4
Author PrimeFan (13766)
Entry type Definition
Classification msc 05A16