> 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 <roma@ro-che.info>:
On 10/29/2015 11:36 AM, Janis Voigtländer wrote:
> 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 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