Bounded-input bijections of infinite sequences

Question

Here is a puzzle I haven't managed to solve. I would like to know if this problem is already known, or has an easy solution.

It is possible to define a bijection $ 3^\mathbb{N} \cong 5^\mathbb{N} $ using the properties of bicartesian closed categories. Andrej Bauer posted an explanation of what this means on his blog as "Constructive gem: juggling exponentials".

This bijection has an interesting property: it is "bounded-input" meaning that each component of the output depends only on boundedly many components of the input. However, for $k,l\geq 2$ it seems that this construction can only show that $ k^\mathbb{N} $ and $ l^\mathbb{N} $ are isomorphic if $k$ and $l$ are both odd or both even. This leaves open the question:

Is there a bounded-input bijection from $ 2^\mathbb{N} $ to $ 3^\mathbb{N} $?

Here is a short note describing the problem in more detail: A conjecture concerning bounded-input bijections of infinite sequences.

Definitions:

A function $f : \prod_{i \in I} X_i \rightarrow \prod_{j\in J} Y_j $ is bounded-input if there exists an integer $k$ such that each component of the output of $f$ depends only on at most $k$ components of the input. More formally, $f$ is bounded-input if for each index $j \in J$ there are indices $i_1,\dotsb,i_k \in I$ and a function $f_m : X_{i_1}\times\dotsb\times X_{i_k} \rightarrow Y_j$ such that for all $x \in X$ the component $f(x)_j$ equals $f_j(x_{i_1},\dotsb,x_{i_k})$.

A bijection $f$ is a bounded-input bijection if it is a bounded-input function.

A bijection $f$ is a bounded-input isomorphism if it and its inverse are bounded-input functions. This is also interesting.

Answer 1

I am not a CS theory guy. But in ergodic theory this type of mapping is known as finitary isomorphisms. For example people considered if two Bernoulli sequences of the same entropy is finitarily isomorphic or not. For example (this is one-sided shift because it seems you are concerned with $P^{\mathbb{N}}$ rather than $P^{\mathbb{Z}}$):

A. Del Junco, “Finitary codes between one-sided Bernoulli shifts,” Ergodic Theory Dynamical Systems, vol. 1, pp. 285–301, 1981.

P.S. I intend to leave this as a comment but I cannot due to lack of reputation. Let me know if it is completely off-topic then I will delete it.

Answer 2

I think an isomorphism between $k^\mathbb{N}$ and $2^\mathbb{N}$ should be provided by any collection of exclusive and exhaustive binary prefixes of size $k$, for example for $k = 3$ we could us "0", "10", and "11". In more general, we can use "0", "10", "110", ..., "11...10", "11...11" where the second to last has $k - 2$ ones and the last has $k - 1$.

The exclusive and exhaustive nature allows us to define the inverse ($2^\mathbb{N} \to k^\mathbb{N}$) in the obvious fashion.

The boundedness in the forwards direction is easy since each input digits provides at least one output digit the $i$th binary digit is easily determined by no more than the first $i$ $k$-ary digits.

The boundedness in the backwards direction is a little uglier. With the prefix collection I gave above each $k$-ary digit "reads" from at most $k$ binary digits and so the $i$th $k$-ary digit is determined by no more than the first $k i$ binary digits.