Finding a finite integer in infinite space

Question

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?

Answer 1

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.

Answer 2

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.