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
    What's wrong with trying $1,2,\ldots,k$ and testing equality each time?2012-04-02
  • 0
    Given that the set of non-negative integers is infinite, my understanding is that there is no guarantee to complete in finite time.2012-04-02
  • 0
    It would find $\rm k$ after precisely $\rm k$ equality tests no?2012-04-02
  • 0
    It will, because the number your adversary has selected is finite. But true there is no upper bound on how long it will take.2012-04-02
  • 0
    Given a positive integer $n$, there is no algorithm that is guaranteed to find $k$ within $n$ steps, but simply testing the non-negative numbers for equality in order is guaranteed to find $k$ on the $(k+1)$-st test. In other words, the algorithm is guaranteed to succeed in finite time, but no *a priori* bound on the time is possible.2012-04-02
  • 1
    Imagine that your adversary just pretends to select an integer. Whatever sequence of tests you name, the adversary can always give you an answer satisfied by infinitely many non-negative integers. If you can only run a bounded number of tests, then after you give up the adversary can reveal a number as if it had been selected at the start.2012-04-02
  • 0
    Surely how long it takes for the alogorithm to settle on k depends upon how quickly its iterations are performed. Count quickly, get to k quickly!2013-07-30
  • 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