(From Omer Tamuz)
Basic puzzle:
A prisoner escaped from prison, and, starting from some n on the positive integer line, jumps k steps to the right at each step. An adversary tries to catch him by landing a the same place as the prisoner at the same time. The adversary chooses one place at each time step, and all choices are possible. For example: 3,10,5,2,58,9,... But the adversary knows neither k nor n.
How can he or she catch the prisoner?
Extension:
What if the prisoner takes his basic calculator and uses some elementary function of time (using addition, substraction, multiplication, division, logarithms, exponentials, sine and cosine - rounded to the nearest integer) to compute where to go at time t?
Further extension:
What if the prisoner takes his laptop and writes a program that will, for each t, determine where he goes at time t?
In each of these cases there are a countable number of strategies (including starting positions) the prisoner could be following. So if the adversary goes to the place prescribed by strategy 1 at t=1, strategy 2 at t=2, and so on, they will catch the prisoner at t=(whichever strategy the prisoner is using).
ReplyDeleteAnonymous, I am very happy to see your comment. That's exactly what I wanted to read. You're almost right... but there is a catch!
ReplyDeleteWhat sort of catch - is it applicable to the original problem or just one (or both) of the extensions? For the second extension, there's the technical issue that you need to add in a layer of dovetailing so that the adversary only considers halting programs...
ReplyDeleteIs the problem that you can't compute the position of strategy s by time s?
ReplyDeleteWell, let's see. If the adversary does what is suggested -- go through programs one by one, say, in order of increasing length, and goes to the place prescribed by strategy 1 at t=1, strategy 2 at t=2, and so on, then let x(t) denote the place which the adversary will check at time t.
ReplyDeleteNow, imagine the prisoner emulates what the adversary does, but adds +1 in the end: then the prisoner goes to position x(t)+1 at time t and is never caught by the adversary.
Hmmmmmmm...
For 1, you just increment $n$ and $k$, and check $n+tk$ at that time step. Start at 0,0, then go up 0,1 1,0 1,1 2,0 2,1 2,2. You will catch the criminal somewhere around step $n*k$.
ReplyDeleteFor the second, this is complicated by having a third variable: which operation. However the fundamental strategy is the same. Iterate through the possible permutations of the prisoner.
The THIRD possibility is interesting. On the face of it, there are a countable number of (finite) programs. However, because of self-reference there is something ill-defined about the program "z=in step i, emulate the ith program". What happens when the program you emulate is z itself? This isn't quite uncountability, and isn't quite diagonalization, but has the flavor of both.
For any deterministic strategy on the part of the adversary, there's a strategy for the prisoner which computes where the adversary would go, and then goes somewhere else. Does this mean the adversary requires randomness?
ReplyDeleteIf the adversary takes a probability distribution with support on all the integers (e.g. a discretized Gaussian) and samples randomly from that distribution, then wherever the prisoner goes at each step there is nonzero probability that the adversary will be there too. So it seems as though the adversary should catch the prisoner with probability 1 - but I worry that it'd be possible for the prisoner to keep running ever further into the tails of the distribution in such a way that this didn't happen.
Two samples over an infinitely long space have a 0 probability of colliding, IIRC.
ReplyDelete"Now, imagine the prisoner emulates what the adversary does, but adds +1 in the end: then the prisoner goes to position x(t)+1 at time t and is never caught by the adversary."
ReplyDeleteEven stronger! Now it really does look like diagonalization.
Problem 3 reduces in an odd way to the halting problem. If the adversary runs every program (as an extension of the all (n,k) strategy) he'll eventually run a non-halting program and never catch the prisoner.
ReplyDeleteHowever, if the prisoner chooses an arbitrary program, it may itself be non-halting, and he'll sit in place until the guards come.
Thus we expect the prisoner to choose one of the provably halting programs. Which means the adversary can first check each program to ensure he can prove it halts before running it.
It is, of course, impossible to prove whether or not a program halts in general. But you can prove that some programs do halt, and skip anything you fail to prove (even though it may halt).
If the adversary and the prisoner both use the same technique for identifying a halting program, the adversary will eventually catch the prisoner. If the prisoner has a stronger technique for identifying halting programs, or risks using a random program that happens to halt on all his inputs and isn't in the adversary's 'good list', he's safe.
But Paul, can't you deal with halting programs by some kind of dovetailing mentioned in one comment: to execute programs on input t, first try one step of program 1, then one step of program 1 and program 2, then one step of programs 1, 2 and 3, etc., until some program terminates and gives you the position to be checked? (Of course you skip programs that you have checked before).
ReplyDeleteVery interesting. You'd have to diagonalize the execution in some way: if you've run n programs, then you run (n-i) steps of the ith program and see if it returns (otherwise you'd run 1 step of every program).
ReplyDeleteHowever, the complexity of each program now comes into play. Let's say the prisoner chooses a program that's O(t^t^t^t^t^t). I suspect (but haven't proven) that there's always a program after that that'll return first. If you run on a fixed t you'd eventually evaluate the program, but every time you finish a program, you need to increment to a new t (as the prisoner has moved on).
Now, if you execute the first O(t^t^t^t^t^t^t) steps of each program in turn, you'd successfully execute the proper program. But what if there's an additional exponent on the order?
I think more interesting than the complexity (although that's an interesting question: are there really complexities with an infinite number of faster algorithms) is the fact that the prisoner could be running the exact same program you are, and using the output differently. Thus I don't think there is a non-randomized way to win, and I'm not sure there's a randomized way.
ReplyDeleteA nice consequence of your counter-example is that it applies to any finite set of cooperating deterministic guards. The "calculator prisoner" would eventually be caught by a single guard, in the worst case it takes infinite guards to comb every integer simultaneously to find the "laptop prisoner".
ReplyDeleteOn the complexity question, there are clearly complexities with an infinite number of faster algorithms as there are infinite constant time algorithms.
I suppose the question about whether diagonalization would eventually evaluate every function on an incrementing argument is:
let f(i,n) be the floor of a strictly increasing function for every i (this lets us delay starting each i for arbitrary lengths of time, but does ensure we eventually approach f(i,inf)=inf.)
let i be an offset into all programs ordered first by length than lexicographically.
let g(i,t) be the steps needed for the ith program to return on integer input t.
then the question would be: for all f, does there exist an i, where i is a halting program and g(i,t) < f(i,n) iff Sum(j!=i){g(j,t) < f(j,t)} > t
Correction f(j,t) => f(j,n):
ReplyDeletethen the question would be: for all f, does there exist an i, where i is a halting program and g(i,t) < f(i,n) iff Sum(j!=i){g(j,t) < f(j,n)} > t
Is the adversary's strategy required to be computable? If not, comment 1 seems right.
ReplyDeleteyes. I should have specified it!
ReplyDeleteThis is an awesome puzzle!
ReplyDeleteFirstly, there's a minor question of information here. The prisoner presumably does not have knowledge of the adversary's strategy, so cannot just move to a different position each time. However, the same idea with a diagonalisation argument works (as many above have alluded to, but no one seems to have written down yet).
Let P_1, P_2, ... be the set of all programs. It doesn't matter whether you include all programs, only programs that halt, etc, as long as: (1) the prisoner and adversary share the same set of programs, and (2) for any program, there exists another program that never agrees with it (for example, the first program + 1). If the adversary has a winning strategy P*, then for all i, there must be some t(i) such that P*(t(i)) = P_i(t(i)). But there is a program P_k which is never equal to P*, hence by contradiction, this winning strategy cannot exist.
Of course, the adversary has plenty of strategies that almost always win, in the sense that for any prior distribution on the prisoner's program, the adversary can win with probability 1. Also, if the adversary and the prisoner have different sets of programs available to them, there may exist a winning strategy.
The apparent paradox raised by Claire's construction of running every program to find the ones that halt doesn't work because it will always miss some programs, due to the fact that the number of steps a program takes to run is not constant but depends on t. As Paul mentioned above, it's difficult to constructively prove that something is always missed, but the absence of a winning strategy is itself a non-constructive proof of this fact.
What if we restrict ourselves to programs which we know to halt? Why can't we simply let P*(t) = P_t(t), safe in the knowledge that we can always compute it? In that case, we have just elegantly proved that there does not exist an algorithm which can enumerate all programs that halt. And if we restricted to some enumerable subset, the program that enumerates and runs them cannot be a member of that subset.
A more intuitive resolution of this sort of paradox is to think about what we mean by a "program". In this context, a program is essentially a sequence of positive integers. However, not all sequences of positive integers are programs, because there are only countably many programs. There does exist a sequence which shares a common entry with every program, but this sequence cannot be a program, because we have assumed that for every program, there exists another program whose output always differs from it.