<div dir="ltr"><div><div><div><div>> It's easy to prove that this is not decidable<br><br></div>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. :-)<br><br></div>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?<br><br></div>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.<br><br></div>Consider, for example, that the ratio is 0.5. Then only one check suffices to find a point!<br><div><div><div> <br></div></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">2015-10-29 13:23 GMT+01:00 Roman Cheplyaka <span dir="ltr"><<a href="mailto:roma@ro-che.info" target="_blank">roma@ro-che.info</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On 10/29/2015 11:36 AM, Janis Voigtländer wrote:<br>
> What if it is additionally known that the shape represented by (x,y,z)<br>
> -> Bool has a closed, convex area (for example)? Most likely there are<br>
> then techniques from algorithmic geometry that can find an inside point<br>
> more efficiently than by iterating blindly through all coordinate triples.<br>
<br>
It's easy to prove that this is not decidable (assuming we're talking<br>
about unbounded numbers, such as Data.Ratio.Rational, and not finite<br>
Double).<br>
<br>
Say you have an algorithm. Run it first on the empty space, and wait<br>
until it gives up after a finite number of probes. These probes all lie<br>
within some ball U. If you now insert your shape, however large, outside<br>
of the ball U, then the algorithm won't find it.<br>
<span class="HOEnZb"><font color="#888888"><br>
Roman<br>
<br>
</font></span><br>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br></div>