# Bijectively parametrize non-negative integers by binary sequences

Given $$n\in \mathbb{Z}_{\geq 0}$$ denote by $$B_n$$ the set of binary sequences of length $$n$$. Denote $$B=\bigcup_{n\geq 0} B_n$$.

Let $$P, Q:\mathbb{Z}_{\geq 0}\to\mathbb{Z}_{\geq 0}$$ be two computable functions. We have a map $$f_{P, Q}:B\to \mathbb{Z}_{\geq 0}$$ given by applying $$P$$ and $$Q$$ to $$0$$ in the order specified by the sequence.

Are there $$P$$ and $$Q$$ such that $$f_{P, Q}$$ is bijective? In particular $$P$$ and $$Q$$ cannot have fixed points.

• A simple example is given by dyadic numerals ($P(n)=2n+1$, $Q(n)=2n+2$), but in fact, every computable bijection $f\colon B\to\mathbb Z_{\ge0}$ can be written as $f=f_{P,Q}$ for suitable computable $P,Q$. – Emil Jeřábek Mar 16 at 18:54