2
$\begingroup$

This is sort of inspired by the game “geo guesser” where you are placed on the surface of the earth and you have to recognise where you are on the planet. I have been considering something like this but rather then the earth it is an infinite binary string.

Consider a read head dropped at an arbitrary point on an infinite string. The read head can read the value at that offset in the string and it can advance. A string is geo guessable if there is an algorithm that terminates and gives the initial offset. So the string “01001100011100001111...” is geo guessable but “010101...” is not.

My question is in terms of O(read steps to find start offset) is there an optimal string/algorithm combo?

And if an optional solution exists what is that solution?

$\endgroup$
  • 1
    $\begingroup$ Could you give a precise formal definition of your problem? In particular, an algorithm takes an input and produces an output. What is the input in your case? $\endgroup$ – J.-E. Pin Feb 14 at 9:25
  • $\begingroup$ I am thinking of algorithm as a finite sequence of well defined steps. In this case the algorithm can get the value from the read head at the offset or advance the head in order to read the next value. However I’ll work on making this more formal. $\endgroup$ – Q the Platypus Feb 14 at 10:09
2
$\begingroup$

I'll try formalizing your problem: Given an infinite binary string $S = (s_i)$, and an offset $n$, let $f_S(n)$ be the number of steps a read head starting at position $n$ needs to take to uniquely determine $n$.

Claim: For any $S$, $f_S$ cannot be in $o(\log(n))$.

Proof: Assume this were the case. Then there is some large $n = 2^k$ and some $j < \frac{1}{3}\log_2(n) = \frac{1}{3}k$ such that $f_S(m) \leq j$ for all $m \leq n$. This means that if a read head is dropped at some position $m < n$, then it is possible to uniquely determine $m$ from the substring $s_{m-j}\ldots s_{m+j}$, so the mapping $m \mapsto s_{m-j}\ldots s_{m+j}$ is injective from integers $\{\frac{n}{2}, \ldots, n-1\}$ to strings of length $2j+1 < k-1$. Unfortunately, there are less than $2^{k-1} = \frac{n}{2}$ such strings, which makes such an injective mapping impossible.


Let $W = (w_1, w_2, \ldots)$ be the list of all finite binary strings not containing the substring $11$, ordered shortlex. Observe that $w_i$ has length $O(\log(i))$, because there are exponentially many such strings of any given length.

Now define $S = w_1\,0110\,w_2\,0110\,w_3\,0110\ldots$

Claim: For this choice of $S$, $f_S$ is in $O(\log(n))$.

Let's place a read head at position $n$. Move left until we find the first $11$ (or the beginning of the string), then move right until we find the next $11$. From what we read in between we can tell which $w_i$ we are at, and thus determine our exact position, though we just read only $O(|w_i|) = O(\log(i))$ symbols. Now by our construction of the string, we know that $i$ is in $O(n)$, thus $\log(i)$ is in $O(\log(n))$.

Altogether, we find that we only needed to read $O(\log(n))$ symbols to determine our starting position $n$ in $S$, so $f_S$ is in $O(\log(n))$, completing the proof.

$\endgroup$
  • $\begingroup$ Cool . I had come up with another solution using “111” as the as the separator then using an encoding of $ 1 \mapsto 01 $ $ 0 \mapsto 10$ to encode a binary counter. Which has the same O(log(n)) I would love something that felt more natural but I think this is the best. $\endgroup$ – Q the Platypus Feb 15 at 5:04

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.