most recent 30 from http://mathoverflow.net 2013-05-25T21:21:02Z http://mathoverflow.net/feeds/question/111877 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/111877/undecidability-of-the-root-existence-problem-for-functions-with-bounded-domain peter franek 2012-11-09T09:24:31Z 2013-01-19T18:23:02Z

<p>The problem whether a real function $f$ has a root or not is undecidable, given that $f$ is from a class of functions including polynomials and the sine function (http://dl.acm.org/citation.cfm?id=321856). Usually, undecidability is proved by using a periodic function like sin to encode integer problems. Is there anything known about undecidability of the root existence problem for some "reasonable" class of functions with <em>bounded domains</em>, such as from a bounded $\Omega\subset\mathbb{R}^m$ to $\mathbb{R}^n$?</p>

http://mathoverflow.net/questions/111877/undecidability-of-the-root-existence-problem-for-functions-with-bounded-domain/111933#111933 Robert Israel 2012-11-09T20:05:31Z 2012-11-09T20:05:31Z

<p>Suppose $f$ is continuous (and therefore uniformly continuous) on a compact domain $K \subseteq {\mathbb R}^n$ (and this is effective in the sense that given $\epsilon > 0$ you can construct $\delta > 0$ such that $\|x - y\| &lt; \delta$ implies $\|f(x) - f(y)\| &lt; \epsilon$. Then if $f(x) = 0$ has no solution in $K$ you can prove that fact: take $\epsilon > 0$ small enough, take $\delta$ as above, cover $K$ with finitely many open balls of radius $\delta$, and compute the values of $f$ at the centres of these balls with sufficient precision to show they all have norm $> \epsilon$. </p>

http://mathoverflow.net/questions/111877/undecidability-of-the-root-existence-problem-for-functions-with-bounded-domain/119342#119342 alexod 2013-01-19T16:22:08Z 2013-01-19T18:23:02Z

<p>Suppose there is an algorithm that decides whether a function $f\colon \Omega \to \mathbb{R}$ has a root. Then one can also compute a root of $f$ if $f$ has one.</p> <p>One can see this using a standard bi-partition argument: Cover $\Omega$ with finitely many balls of radius $1$. This is possible since the closure of $\Omega$ is compact. Then using the algorithm we can find a ball that contains a root of $f$. Then we cover this ball with balls of radius $2^{-1}$ and again find a smaller ball which contains a root...</p> <p>Iterating this process yield a sequence converging to a root of $f$ with rate $2^{-n}$ or in other words a Cauchy-real representation for a root.</p> <p>Now, finding a root for a function implies Brouwer's fixed point theorem.</p> <p>To see that let $\Omega$ be bounded and closed and $g\colon \Omega \to \Omega$ continuous. $g$ has a fixed-point at any root of the function $f\colon \Omega \to \mathbb{R}$, $f(x):= \lvert g(x) - x\rvert$.</p> <p>For Brouwers fixed point theorem it is known that there is no algorithm to find solutions, see for instance <a href="http://arxiv.org/abs/0804.3199" rel="nofollow">Computable counter-examples to the Brouwer fixed-point theorem, Petrus H. Potgieter</a>.</p> <p>Thus, we can conclude that there is no algorithm which decides whether a function has a root.</p>