Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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.
