Modified Takeuchi function as non recursive function

63 Views Asked by At

The Takeuchi function is described as

$$ t(x,y,z) = \begin{cases} \text{if } x \leq y & y \\ \text{else} & t⁢(t⁢(x-1,y,z),t⁢(y-1,z,x),t⁢(z-1,x,y)) \\ \end{cases} $$

which also has a non-recursive definition:

$$ t(x,y,z) = \begin{cases} \text{if } x \leq y & y \\ \text{else if } y \leq z& z \\ \text{else } & x \\ \end{cases} $$

Now the problem: I am trying to work out the non-recursive definition of a modified version which is the following:

$$ t(x,y,z) = \begin{cases} \text{if } x \leq z & y \\ \text{else} & t⁢(t⁢(x-1,y,z),t⁢(y-1,z,x),t⁢(z-1,x,y)) \\ \end{cases} $$

My first approach was to order the input in lexicographical order (starting at $t(1,1,1))$ and trying to deduce a relationship which seemed to look like like this initially:

$$ t(x,y,z) = \begin{cases} \text{if } x \leq z & y \\ \text{else if } y > x & x \\ \text{else } & z \\ \end{cases} $$

but that does not work, a counterexample is t(20, 7, 18)=8. So the underlying relationship seems to be a bit more complex. I have also tried to formally infer the solution by differentiating the cases for the '>'-relation between the variables but I did not get far with that either.