<p>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.</p>

<p>Then $O(\log x + \log y)$ addition could be defined as $$\begin{align} &amp;add(x, y) = add'(\pi_1(x), \pi_1(y), \pi_2(x), \pi_2(y), 0) \\ &amp;add'(0, 0, 0, 0, 0) = 0 \\ &amp;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 &gt; 1$ and $0$ otherwise.</p>

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

CC BY-SA 3.0
2014-07-24T16:52:51.723Z
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 ?
Xoff
CC BY-SA 3.0
2014-07-24T17:58:25.380Z
@Xoff, the parallel of $\pi$ in real computers is writing two bytes one after another and projection $\pi_k$ is random memory access.
Karolis Juodelė
CC BY-SA 3.0
2014-07-24T18:09:22.803Z
Now that I think about it, this recursion isn't so primitive... Possibly, including the lengths of the numbers before first digit could help?
Karolis Juodelė
CC BY-SA 3.0
2014-07-24T18:43:37.880Z
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 !
Xoff
CC BY-SA 3.0
2014-07-24T16:33:22.173Z
2014-07-24T17:58:52.280Z
2014-07-24T17:58:52.280Z
Karolis Juodelė
<p>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) &amp;= g(\vec x), \\
f(zi,\vec x) &amp;= h_i(z,\vec x,f(z,\vec x)), &amp; i\in\{0,1\}
\end{align*}
$$
as soon as $g$ and $h_0,h_1$ are already in the class.</p>

<p>In the above setting, the usual numerical functions may be encoded either by considering only unary strings (<em>i.e.</em>, $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).</p>

<p>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", <em>Computational Complexity</em> 2(2):97-110. </p>

CC BY-SA 3.0
2014-07-25T12:18:51.310Z
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) ?
Xoff
CC BY-SA 3.0
2014-07-25T12:52:39.817Z
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).
Damiano Mazza
CC BY-SA 3.0
2014-07-25T10:56:02.250Z
2014-07-25T12:53:41.393Z
2014-07-25T12:53:41.393Z
Damiano Mazza
<p>Usually primitive recursive functions are define from Zero, Identity and Successor, projectors, composition and recursion. </p>

<p>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.</p>

<cc.complexity-theory><computability>
Primitive Recursive Definition : Binary numbers
Xoff
# Primitive Recursive Definition : Binary numbers

(Asked by: username_0 on 2014-07-24)

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.

**Tags:** cc.complexity-theory, computability

---

## 2 answers

### Answer by username_2 on 2014-07-25. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_0**: 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) ?  
> **username_2**: 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).  

---

### Answer by username_1 on 2014-07-24. Score: 1

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.

> **Comments:**
> **username_0**: 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 ?  
> **username_1**: @Xoff, the parallel of $\pi$ in real computers is writing two bytes one after another and projection $\pi_k$ is random memory access.  
> **username_1**: Now that I think about it, this recursion isn't so primitive... Possibly, including the lengths of the numbers before first digit could help?  
> **username_0**: 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 !  

---

