1
$\begingroup$

Came across this interesting problem in one of my interviews. Suppose you have a circular turing tape, i.e. simply a circular array. You do not know the size i.e. the number of cells available in that circular array.

The array consists only of binary digits. Lets say you are currently at one of the cells. You can read and write on the current cell you are on. You can rotate the array towards the left or right, and you have a counter with you which tells you how far away are you from the original cell that you started off with. So if you go right by x units, the counter will read x units and -x if you go x units to the left. However, you cannot store the value of previous cells you encountered. You may have at max only one unit of external memory at your disposal. For example, if you are at +x, you could compare the value at that +x with the one value you have stored in the external memory. Given that currently all the cells have been randomly assigned either a 0 or a 1.

How would you identify the size of this circular array?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Can you simulate the following strategy? Set the initial cell to 0. For $n=1,2,\ldots$, go right $n$ cells, set the cell to 1, and go back to the origin. Check whether the value changed from 0 to 1. $\endgroup$ – Yuval Filmus Nov 2 '18 at 6:47
  • $\begingroup$ Another unbounded search. $\endgroup$ – Apass.Jack Nov 2 '18 at 7:36
  • $\begingroup$ Beware size one. $\endgroup$ – greybeard Nov 2 '18 at 9:34
  • $\begingroup$ Does one unit mean one bit or a constant number of bits? $\endgroup$ – DreamConspiracy Nov 2 '18 at 14:54
  • $\begingroup$ @DreamConspiracy one bit $\endgroup$ – qwerty_uiop Nov 2 '18 at 14:56
1
$\begingroup$

This answer was inspired by YuvalFilums's comment.

I will denote values in the cells with $t$ and $f$ and locations on the tape with $0, 1, 2, \dots$ to avoid confusion.

First, check that the length $\neq 1$. To do this, set the cell under the counter to $f$. Then, move right $1$ cell and set that cell to $t$, and return to $0$, checking if that is $t$. If so you have your answer, otherwise move to $2$ and set that to $f$, and return to $0$.

Second, check that the length $\neq 2$ similarly.

Then repeat the following procedure indefinitely:

  1. Move right until encountering an $f$. Set this to $t$.
  2. Move right one cell and set it to $f$.
  3. Return to $0$. If it is $t$, find the first $f$ after $1$, and move left one cell. This is your answer. Otherwise, repeat.
|cite|improve this answer
$\endgroup$

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.