On 10/29/2015 02:45 PM, Janis Voigtländer wrote:
It's easy to prove that this is not decidable
I'm not sure what you mean by "this", but if you mean "to find a point in an infinitely large space by finitely many experiments", then of course it is not decidable, and I'm surprised you go to such length to prove it. :-)
I guess I was equally surprised to see you suggesting doing that!
It is not in the original question as formulated (except as hints if you look for them), but let's assume the problem is that you have (x,y,z) -> Bool for x,y,z natural numbers below 100. And some of the 10^6 points are True, others False. Is there a better algorithm for finding a True point than blindly iterating through all 10^6 points?
I suggested that yes, there might be, if the shape is known to be convex and a ratio is known of how much volume of the whole region it takes up.
Consider, for example, that the ratio is 0.5. Then only one check suffices to find a point!
Now we are guessing, of course, but in my experience, when people casually talk about a shape in a 3-dimensional space without further clarification, they usually mean the 3d real Euclidean space or some approximation thereof.