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.

  • $\begingroup$ 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$. $\endgroup$ – Emil Jeřábek Mar 16 at 18:54

Your Answer

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

Browse other questions tagged or ask your own question.