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. :-)
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!
2015-10-29 13:23 GMT+01:00 Roman Cheplyaka
What if it is additionally known that the shape represented by (x,y,z) -> Bool has a closed, convex area (for example)? Most likely there are then techniques from algorithmic geometry that can find an inside point more efficiently than by iterating blindly through all coordinate
On 10/29/2015 11:36 AM, Janis Voigtländer wrote: triples.
It's easy to prove that this is not decidable (assuming we're talking about unbounded numbers, such as Data.Ratio.Rational, and not finite Double).
Say you have an algorithm. Run it first on the empty space, and wait until it gives up after a finite number of probes. These probes all lie within some ball U. If you now insert your shape, however large, outside of the ball U, then the algorithm won't find it.
Roman
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe