4
$\begingroup$

Usually primitive recursive functions are define from Zero, Identity and Successor, projectors, composition and recursion.

But you obtain algorithms that works with unary numbers. For example, the addition $x+y$ has complexity $O(y)$, whereas usually, it has complexity $O(|x|+|y|)$. Is there a canonical definition of recursive functions that consider integers as binary string ? Any references are welcomed.

|cite|improve this question
$\endgroup$
4
$\begingroup$

The concept of primitive recursion function easily generalizes to any inductive data structure. For example, you can define the primitive recursive functions on binary strings as the smallest class of functions containing $\epsilon$ (the constant "empty string"), $S_0,S_1$ (append $0$ or $1$), projections and closed under composition and the scheme allowing to define a function $f$ by $$ \begin{align*} f(\epsilon,\vec x) &= g(\vec x), \\ f(zi,\vec x) &= h_i(z,\vec x,f(z,\vec x)), & i\in\{0,1\} \end{align*} $$ as soon as $g$ and $h_0,h_1$ are already in the class.

In the above setting, the usual numerical functions may be encoded either by considering only unary strings (i.e., $n$ is represented by $1^n$), in which case you can mimick the usual primitive recursive functions, or, more interestingly, by representing integers in binary. In that case, the successor function is not part of the basic functions but must be defined (and this is not immediate).

As you point out, traditional recursion theory considers primitive recursion on unary strings (or tally integers) because in that setting complexity is not a main concern. On the other hand, whenever complexity classes are defined in terms of recursive functions, primitive recursion on binary strings (or binary integers) is routinely used. See for example the seminal paper by Bellantoni and Cook "A New Recursion-Theoretic Characterization of the Polytime Functions", Computational Complexity 2(2):97-110.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks ! Your recursion operator consider binary strings as queue (FIFO). Wouldn't be more natural to have a recursion operator that consider binary strings as stacks (FILO) ? $\endgroup$ – Xoff Jul 25 '14 at 12:18
  • $\begingroup$ Yes, you can do that as well, there is no difference in terms of expressiveness. The formulation I gave is often used because it has a more straightforward meaning in terms of binary integers: the basic functions $S_i$ are just the functions $n\mapsto 2n+i$ and the choice of which of $h_0,h_1$ to use when unfolding a primitive recursion is given by whether the argument leading the recursion is divsible or not by $2$ (all this of course ignoring the non-uniqueness of the representation). $\endgroup$ – Damiano Mazza Jul 25 '14 at 12:52
1
$\begingroup$

If pairing function $\pi : \mathbb{N}^2 \to \mathbb{N}$ and projection functions $\pi_1, \pi_2 : \mathbb{N} \to \mathbb{N}$, such that $\pi(0, 0) = 0$ were $O(1)$ then numbers can easily be represented by lists of digits, $\pi_1$ being the first, $\pi_1 \circ \pi_2$ - the second and $\pi_1 \circ \pi_2^n$ - the $n$'th digit.

Then $O(\log x + \log y)$ addition could be defined as $$\begin{align} &add(x, y) = add'(\pi_1(x), \pi_1(y), \pi_2(x), \pi_2(y), 0) \\ &add'(0, 0, 0, 0, 0) = 0 \\ &add'(a, b, x, y, c) = \pi(\oplus(a, b, c), ~ add'(\pi_1(x), \pi_1(y), \pi_2(x), \pi_2(y), ~carry(a, b, c))) \end{align}$$ Here $\oplus$ is addition modulus $2$ and $carry$ is $1$ if $a+b+c > 1$ and $0$ otherwise.

I'm not sure about canonical definitions, but I think this is quite natural.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ That's a nice suggestion, but unfortunately, in real computers, projection is not a O(1) operation. Or perhaps we could extend definitions from $\mathbb N$ to $\mathbb N^*$ with some kind of typing mechanism ? $\endgroup$ – Xoff Jul 24 '14 at 16:52
  • $\begingroup$ @Xoff, the parallel of $\pi$ in real computers is writing two bytes one after another and projection $\pi_k$ is random memory access. $\endgroup$ – Karolis Juodelė Jul 24 '14 at 17:58
  • $\begingroup$ Now that I think about it, this recursion isn't so primitive... Possibly, including the lengths of the numbers before first digit could help? $\endgroup$ – Karolis Juodelė Jul 24 '14 at 18:09
  • $\begingroup$ As $\pi$ is a bijection it should at least read is argument which means it must at least take a linear time (using input size). So I don't think it should be made atomic in a natural definition of primitive recursive functions. But I may be wrong ! $\endgroup$ – Xoff Jul 24 '14 at 18: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.