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?