mathematics - Automatically a Knight, Knave, and Joker

Let M be a finite positive integer. It's exact value is not known.

Suppose we have three classes of automaton, all of which accept a bit stream as input, produce a bit stream as output (one bit per input bit), and have a non-observable state, S, that is an integer coordinate on an infinite bidirectional 1D line:

• knightbots start with S = M. Whenever a 1 bit is inputted, knights move 2 units to the right (i.e. S is incremented by 2). Whenever a 0 bit is inputted, knights move 1 unit to the left (i.e. S is decremented by 1).


• knavebots start with S = -M. Whenever a 1 bit is inputted, knaves move 1 unit to the right. Whenever a 0 bit is inputted, knaves move 2 units to the left.


• jokerbots start randomly at either S = M or S = -M. On cromulent days, jokers move 1 unit right on a 1 input and 1 unit left on a 0 input, but on non-cromulent days, jokers move 1 unit left on a 1 input and 1 unit right on a 0 input. You have no idea whether or not the current day is cromulent, and there's really no way to find out.

After each input, the automata output either a 1 if they have moved into the state S = 0, or a 0 otherwise.

Simple Problem (for "Correct Answer" Credit)

You are given an automaton that is either a knightbot, a knavebot, or a jokerbot, but you don't know which of the three. The automaton is guaranteed to be in its starting state. You can input bits to the automaton and observe its output, but otherwise you cannot observe its state or inner workings. Also note that you cannot "reset" the automaton.

Your task is to produce an algorithm that is mathematically guaranteed to properly classify the automaton as a knight, knave, or joker using an input sequence of finite length.

Your solution should include a (reasonably) detailed description of your algorithm, as well as a guaranteed (although not necessarily tight) upper bound on required input length as a function of M.

Challenge Problem (for 100 Bonus Rep!)

Instead of the aforementioned jokerbots, consider jesterbots:

• jesterbots start with S start randomly at either S = M or S = -M


• jesterbots have a secondary state, b, which assumes the value of the most-recently-inputted bit. The initial value of b is 0.


• jesterbots have a tertiary state, D, which takes on the values 1 or -1, and may be treated as a direction. The initial value of D is 1.


• on cromulent days, jesterbots move in the direction of D (i.e. increment S by D) iff an input bit matches b (the previous input bit), or else stand still and about face (multiply D by -1)


• on non-cromulent days, jesterbots move in the direction of D iff an input bit does not match b, or else stand still and about face


• after each input, the jesterbot outputs a 1 if it has moved into the state S = 0, or a 0 otherwise

Your task is identical to that for the simple problem, only substituting jester(bot) for joker(bot) in the task description.

I will award 100 bounty rep to the correct, defensible solution to this challenge problem that has the strictest upper input length bound (in terms of $\mathcal{O}\left( M\right)$), or to the earliest solution in the case of a tie.

Good luck automating. :)

Answer

I claim a bound linear in $M$.

First of all, the challenge is really to make the automaton hit 0. Once it hits 0, we can easily determine what type it is using a constant number of moves.

Let $A_1,A_2,...,A_n$ denote different types of automatons. For us, the $A_i$ consist of a knightbot, a knavebot, and then many different automatons for each initial setting of a jester/jokerbot.

We also assume that, given an automaton $A_i$, if we know what state it is in, then we can always move it one space to the right or one space to the left in constant time. This is clearly true for any automaton in the problem.

Now, suppose we have a finite upper bound $B$ on the distance from our automaton to the origin. Then the following series of moves is guaranteed to make the automaton hit 0 in $O(B)$ time:

• Pretend the automaton is $A_1$. Move it $B$ spaces to the right, one at a time. Then move it $2B$ spaces to the left. This takes time $O(B)$.



• If we hit 0 along the lines, great! Otherwise, our automaton is not $A_1$. Pretend the automaton is $A_2$. Then we have spent $O(B)$ moves so far, so there is a number $k=O(B)$ such that our automaton is at most $k$ steps from the origin. So, first calculate the internal state that $A_2$ would be in, given the entire sequence of inputs we have fed it so far. Then, based on this state, move the automaton $k$ steps to the right, one at a time, and then $2k$ steps left, one at a time.


• If we hit 0, great! Otherwise, pretend our automaton is $A_3$. You can see where this is going.... The important thing to note is that, since the number of automatons $n$ is a constant, the total number of steps spent to test all $n$ automatons is still $O(B)$. The constant factor may be large, but whatever, it's still $O(B)$.

Great. Unfortunately, we don't know an upper bound $B$ on the distance from our automaton to the origin. The fix is very simple. The above procedure runs in $O(B)$ moves, so there exists a constant $c$ such that the above procedure never moves any automaton $A_i$ by more than $cB$ steps.

Now, run the above procedure with $B=1,3c,(3c)^2,(3c)^3,(3c)^4,\dots$.

To see that this works, fix $M$. Pick $k$ so that $\frac 12(3c)^k\leq |M| \leq \frac 12(3c)^{k+1}$. Then after the first $k$ iterations of the procedure, by our choice of $c$, the automaton has moved at most $c(1+3c+(3c)^2+\cdots+(3c)^k)=c\frac{(3c)^{k+1}-1}{3c-1}\leq\frac 12(3c)^{k+1}$ spaces. So, it is at most $\frac 12(3c)^{k+1}+|M|\leq(3c)^{k+1}$ distance from the origin. Therefore, it will be found on the next iteration (because on the next iteration we use $B=(3c)^{k+1}$).

Furthermore, because each iteration takes linear time, the entire sequence of iterations takes at most $O(1)+O(3c)+O((3c)^2)+\cdots+O((3c)^{k+1})$ time. This sum is $O((3c)^k)$, and therefore $O(M)$.

Therefore, this procedure is guaranteed to hit 0 in $O(M)$ moves. As noted previously, as soon as we hit 0, we can easily determine which automaton we are dealing with using a constant number of moves. Therefore, this procedure guarantees a linear bound. QED