Numbers which encode other numbers infinite times.

Question

Let $g(x,n)$ be a function which chops off the first n digits of the binary decimal expansion of x.

eg $g(0.1010111,2)=0.10111$

Is there a function $f(x)$ from the reals to the reals, such that for all positive integers n, and real numbers $x$, given only the value of $c$, where $c=g(f(x),n)$, there is an algorithm to find $x$?

Is there an algorithm, given both $n$ and $c$, to find $x$?

Answer 1

Yes.

First encode the binary representation of $x$ so it is a number in $[0,1)$, then create a infinite number of copies of this in another number in $[0,1)$.

To decode, find one of the untruncated copy and then decode back to the original real.

So for example, for the first step take the first bit to represent the sign and then use the even bits to hold the integer bits of $x$ in reverse (using $0$s when you run out) and the other odd bits to hold the fractional bits of $x$. Call this $y$.

For the second part, put the bits of $y$ at positions $p^1, p^2,p^3,\ldots$ for all primes $p$ and fill the non-prime-powers with $0$. Call this $z=f(x)$.

To decode $g(z,n)$, chose any particular prime $p>n$ and look at the bits $p^1, p^2,p^3,\ldots$. This gives you $y$. Then reverse the first step.

Answer 2

If I understand you right, you want to find an $f$ such that $$\forall x,y\in\mathbb R,n,m\in\mathbb N: g(f(x),n)=g(f(y),m)\Rightarrow x=y$$ And furthermore, given the value of $g(f(x),n)$ there should be an effective procedure for finding $x$. True?

I think it is somewhat easier to think in terms of bit sequences than real numbers here, so let's assume that $f$ takes $2^\omega$ (the set of infinite sequences of bits) to $2^\omega$ and $g$ just chops off the first $n$ bits in a sequence. This is equivalent to your formulation, if only we take a bit of care not to run into trouble with sequences that end in repeating $1$s.

Here is one possible construction for $f$.

1. Take the input bit sequence and put $22$ in front of it. This results in another infinite sequence of the alphabet $\{0,1,2\}$. Call this sequence $a_1, a_2, a_3, \ldots$.

2. Interlace infinitely many copies of the $(a_i)$ sequence, like this:$$\begin{array}{c} a_1 && a_2 && a_3 && a_4 && a_5 && a_6 \\ & a_1 &&&& a_2 &&&& a_3 \\ &&&a_1&&&&&&&&a_2 \\ &&&&&&& a_1 \\ \hline a_1 & a_1 & a_2 & a_1 & a_3 & a_2 & a_4 & a_1 & a_5 & a_3 & a_6 & a_2\end{array}$$ Each copy is spaced out by a factor of $2^i$ for some i. The general rule is that the element number $2^i(2j-1)$ of the interlaced sequence is $a_j$.

3. Translate the interlaced sequence to a self-synchronizing binary sequence by the rule that $0$ becomes 0, $1$ becomes 01 and $2$ becomes 011.

To find $x$ given $g(f(x),n)$, translate back to an $\{0,1,2\}$-sequence and look for the first two $2$-symbols whose mutual distance is a power of $2$. These two $2$s must be the beginning of one of the copies of $(a_i)$, and now that you know where it begins and what its spacing is, you can read off all of the $(a_i)$ and reconstruct $x$.

Since the output sequence contains infinitely many zeroes and infinitely many ones, we don't get into any problems with real $c$ values that have two different binary represntations.