1
$\begingroup$

An adversary selects an integer k from the set of non-negative integers.

Does any algorithm exist that, using only tests for equality or inequality (<, =, >), is guaranteed to find k in finite time?

  • 0
    @TomHewitt Not really...think of it as a computer. Your computer runs slowly, but then you get a software patch and it runs quicker again. The patch (might be) just finding a better way of doing the same job. Maybe a better example is of summing the numbers up to $n$. I could do this by simply summing them $1+2+\ldots$. But this takes a while. Or, I could compute $n\cdot(n+1)/2$. This is much quicker! The second, different algorithm gives the same result, but quicker!2013-07-30

3 Answers 3

3

At step $n$ test the non-negative integer $n-1$ for equality; you are guaranteed to find $k$ on step $k+1$, so the algorithm is guaranteed to terminate after a finite number of steps, though the possible stopping times are unbounded. What is not possible is to put a fixed limit on the search time beforehand: no matter what algorithm you use, for any $n$ there will be values of $k$ that cannot be found within $n$ steps.

  • 1
    @Eric: Suppose that you pick $k=10^{100}$; my algorithm will find it on step $10^{100}+1$. That’s a **very** long time, **but it’s still finite**. For any **specific** $k$ the amount of time needed is finite, though if $k$ is large, the amount of time needed will also be large. You keep ignoring the fact that in any given play of the game, $k$ is a **fixed** non-negative integer. It’s not floating around in the non-negative integers. It’s a single definite number, and if I count long enough, I **will** hit it.2012-04-03
3

As pointed out in the comments and in Brian's answer, checking $0,\ldots,k$ for equality will give you the answer in $k+1$ steps. You can improve on this by testing $2,2^2,\ldots,2^{\lceil\log k\rceil}$ for the inequality $\leq$ and then testing $2^{\lceil \log k\rceil-1}+2,\ldots,2^{\lceil \log k\rceil-1}+2^{\lceil \log k\rceil-1}$ with $\leq$, on and on as much as necessary. However, as Brian points out no algorithm can guarantee that for any $k$ it will give you the answer in a certain number of steps. To make this explicit, suppose you had an algorithm guaranteed to work in $n$ steps. For any test there are at most two results, so the algorithm has at most $2^n$ possible outputs. Your opponent then needs only choose a number greater than any of these $2^n$ outputs to defeat it.

  • 0
    The point is that the adversary *can't* move the target after he made his choice. Here's the situation: he chose $k$. You test $1$, the answer is no. You test $2$, so on and so forth. Eventually you test $k$ and the answer will be yes. He can't move the target once he made his choice. It is fixed for however long it takes you to find it.2012-04-03
1

Let's think about this from the perspective of the adversary. If we know that the player is going to try every non-negative integer in order, what number can we pick so that it takes her an infinite amount of time to guess it?

Clearly we can't pick $0$, she'll guess that right away! Picking 1 buys us a little time, but not much. 2, 3 and 4 will also be guessed quickly. Each higher number we consider takes a bit longer, but still isn't infinite. By induction, we're forced to concede that there is no number for us to pick that will take an infinite amount of time to guess. The reason for this is that even though there are an infinite number of integers, all of them are finite.

  • 0
    That is a helpful way to think about it.2014-07-16