6
$\begingroup$

How can the class of tail recursive functions (TR) be compared to the classes of primitive recursive functions (PR) and recursive functions (R)?

The computation of a PR function always halts. This does not apply to TR functions. Given a tail recursive function $f$: $$f(x) = f(x)$$ The function $f$ obviously will result in an endless recursion and therefore $TR \not\subseteq PR $. Also a PR function has a finite time and space complexity, where a TR function can have a finite space and infinite time complexity. For this reason I assume: $$PR \subset TR \subset R $$

  • Is this assumption correct?
  • Is the Ackermann function $\in TR$?
  • Is there a well known function which is in $R$, but not in $TR$?
$\endgroup$
10
$\begingroup$

Every computable function can be expressed in continuation-passing-style, in which all calls are tail-calls.

The trick is to add a "continuation" parameter to every function. Instead of making a non-tail-call to a function, you make a tail call to that function with a modified continuation, describing what to do with the result. All instances where a value is directly returned (such as recursion base cases) are replaced by calling the continuation in tail-position with the result as an argument.

Transformation from the lambda calculus into CPS can be done mechanically. So, $TR=R$.


EDIT: addressing the comments about higher-order functions:

Tail-calls are almost always discussed in the context of higher order functions and the lambda calculus. So the problem is, what precisely is our definition of $TR$?

You can certainly add a wrapper around a CPS function to give it the type $\mathbb{N}^n \to \mathbb{N}$, by giving it an initial continuation of $\lambda k \ldotp k$. If higher-order functions are allowed internally, then the result that $TR=R$ still holds.

If higher order functions aren't allowed internally, what is our definition of $TR$? If we define it in the same way as $PR$, then it is going to only contain primitive recursive problems by definition (since it's just the restruction of $PR$ to tail-recursion). If we add $\mu$ for infinite search, I think we're just going to get $R$, since we can encode higher-order functions using integers. So, I'm not sure there's a meaningful question to be asked in the non-higher-order case.


EDIT 2:

As for the class of first-order functions that only allow tail recursion, with Constant, Successor, Projection and Composition functions, and extension by tail recursion:

h(x1 ... xn) = 
  if c(x1 ... xn) = 0 then
    h(g1(x1), ..., gn(xn))
  else
    f(x1, ..., xn)

where $c$, $g_i$ and $f$ are all tail-recursive functions, I think we can prove that it's Turing Complete, by solving Post's Correspondence Problem, which is undecidable but semi-decidable:

Assume that we've got nice functions for dealing with strings encoded as integers, with concatenation, etc.

Let $pcpInst(k, n)$ be a function which takes an integer $k$ and returns the $k$th string over the alphabet $\{1, \ldots, n \}$.

Let $c(k, x_1, \ldots, x_n) = $ be a function, where $k$ is an integer, and each $x_i$ is a pair containing two strings over a binary alphabet. Thus function does the following:

  • Computes $k_1 \cdots k_p = pcpInst(k,n)$, the $k$th possible PCP solution indices.
  • Constructs $s_1=\pi_1(x_{k_1}) \cdots \pi_1(x_{k_p}))$. This is the string we get by concatenating the first string of the arguments indexed by our $k_i$ sequence. We define $s_2$ with $pi_2$ similarly.
  • Return $0$ if $s_1 \neq s_2$, return $1$ otherwise.

Now, we'll define our function to solve the a PCP instance with $n$ strings:

  • $h(k, x_1, \ldots, x_n) = h(S(k), x_1, \ldots, x_n)$ if $c(k, x_1, \ldots, x_n) = 0 $
  • $h(k, x_1, \ldots, x_n) = 0$ otherwise

Now we define $h'(x_1, \ldots, x_n) = h(0, x_1, \ldots, x_n)$.

It is clear to see that $h'(x_1, \ldots, x_n)$ returns 0 if and only if there is a solution to the correspondence problem defined by pairs of strings $x_1, \ldots, x_n$. If there is a solution, we eventually iterate to it by increasing $k$, and return $0$ when our $c$ function returns 1. If there is no solution, we never return.

The trick here is ensuring that $c$ is itself tail-recursive. I am fairly confident that it is, but that proving so would be tedious. But since it is performing simple string manipulations and equality checks, I would be very surprised if it is not tail recursive.

$\endgroup$
  • $\begingroup$ Cool, that's unexpected. I guess the transformation is not computable? $\endgroup$ – Raphael Dec 11 '15 at 7:49
  • $\begingroup$ CPS is very interesting, but requires higher-order functions (space complexity isn't finite anymore). What does it mean if all functions $f \in TR$ have the type $f \colon \mathbb{N}^\mathbb{(N)} \to \mathbb{N}$ (like $PR$ and $\mu$-recursive functions)? Could you please extend your answer? $\endgroup$ – Peter Dec 11 '15 at 9:11
  • 2
    $\begingroup$ @Raphael I'm not sure what you mean. The transformation is computable, it just doesn't say anything about halting i.e. divergent programs are mapped to divergent programs. $\endgroup$ – jmite Dec 11 '15 at 18:44
  • $\begingroup$ @Peter I've edited my answer. I'm not sure there's a meaningful question to be asked in that case. What precisely is your definition of $TR$? $\endgroup$ – jmite Dec 11 '15 at 18:58
  • 1
    $\begingroup$ Thank you very much for taking the time to answer my questions! How do you define a growable list/string in $TR$? In a Turing machine you have a infinite tape and in $\mu$-recursive functions you can do infinite recursive calls. Tail recursive functions are basically as limited as simple loops. Although the input in PCP is finite, the actual length of the input is only known at runtime. So there must be some form of growable list. $\endgroup$ – Peter Dec 14 '15 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.