Consider the following game: Alice chooses a real function number $x\in [0,1]$; Bob has to guess the number by asking Alice any number of queries of the form "is $x > a$?" [where Bob can choose the $a$]. Obviously Bob cannot always win by asking a finite number of queries, since any finite number of such queries only reveals an interval of positive size in which $x$ can be found.
There are similar problems that cannot be solved by a finite number of queries, but the proof might be more complicated. For example, here, Stromquist has proved that it is impossible to find an envy-free cake-division using a finite number of "mark" and "eval" queries. This result can be stated as follows. Suppose Alice chooses three nonatomic measures $v_1,v_2,v_3$ on $[0,1]$. Bob has to find two numbers $x,y\in [0,1]$ such that, after possibly renumbering the measures, the following holds:
- $v_1(0,x)\geq v_1(x,y)$ and $v_1(0,x)\geq v_1(y,1)$ ;
- $v_2(x,y)\geq v_1(0,x)$ and $v_2(x,y)\geq v_2(y,1)$ ;
- $v_3(y,1)\geq v_3(x,y)$ and $v_3(y,1)\geq v_3(0,x)$ .
Bob cannot do this using a finite number of queries of the form "what is $v_i(0,a)$?" and "what is a $b$ such that $v_i(0,b)=a$?".
My question is: is there a known complexity class of problems that cannot be solved using a finite number of queries (for some precise definition of queries)? My goal is to prove that some other problems cannot be solved finitely, using a reduction from known problems in that class.