Skip to main content
deleted 104 characters in body
Source Link
Robert Israel
  • 54.2k
  • 1
  • 76
  • 152

There is not even an algorithm to test whether a solution exists. See e.g. Richardson's theorem.

To have something sensible, you need at least to be able to restrict the domain to a bounded region.

EDIT: ... and even then, depending on the precise formulation of the problem, it can be impossible. Consider the following family of functions. Given Turing machines $T_0$ and $T_1$ (including specified inputs), let $$f(x) = \sum_{n=1}^\infty \left(a_n x^{n} + b_n (x-1)^{n}\right)$$ where

  1. If $T_0$ halts in exactly $n$ steps and $T_1$ has not halted by $n$ steps, $a_n = 1/n!$ and $ b_n = 0$.
  2. If $T_1$ halts in exactly $n$ steps and $T_0$ has not halted by $n$ steps, $a_n = 0$ and $b_n = 1/n!$.
  3. Otherwise $a_n = b_n = 0$.

If $T_0$ halts before $T_1$, $f(x)=0$ has the unique solution $x=0$; if $T_1$ halts before $T_0$, it has the unique solution $x=1$; if neither halts, or if they halt at the same step, all $x$ are solutions.

Note that $f(x)$ is a perfectly nice function, in fact a polynomial whose $n$'th coefficient can be found exactly by simulating $n$ steps of the Turing machines. Similarly, the The value of $f$ or any of its derivatives at a given point can be approximated with arbitrary precision by simulating sufficiently many steps of the Turing machines. But since there is no algorithm to determine whether a Turing machine halts on given input, there is no algorithm to find (or approximate) a solution to $f(x)=0$.

There is not even an algorithm to test whether a solution exists. See e.g. Richardson's theorem.

To have something sensible, you need at least to be able to restrict the domain to a bounded region.

EDIT: ... and even then, depending on the precise formulation of the problem, it can be impossible. Consider the following family of functions. Given Turing machines $T_0$ and $T_1$ (including specified inputs), let $$f(x) = \sum_{n=1}^\infty \left(a_n x^{n} + b_n (x-1)^{n}\right)$$ where

  1. If $T_0$ halts in exactly $n$ steps and $T_1$ has not halted by $n$ steps, $a_n = 1/n!$ and $ b_n = 0$.
  2. If $T_1$ halts in exactly $n$ steps and $T_0$ has not halted by $n$ steps, $a_n = 0$ and $b_n = 1/n!$.
  3. Otherwise $a_n = b_n = 0$.

If $T_0$ halts before $T_1$, $f(x)=0$ has the unique solution $x=0$; if $T_1$ halts before $T_0$, it has the unique solution $x=1$; if neither halts, or if they halt at the same step, all $x$ are solutions.

Note that $f(x)$ is a perfectly nice function, in fact a polynomial whose $n$'th coefficient can be found exactly by simulating $n$ steps of the Turing machines. Similarly, the value of $f$ or any of its derivatives at a given point can be approximated with arbitrary precision. But since there is no algorithm to determine whether a Turing machine halts on given input, there is no algorithm to find (or approximate) a solution to $f(x)=0$.

There is not even an algorithm to test whether a solution exists. See e.g. Richardson's theorem.

To have something sensible, you need at least to be able to restrict the domain to a bounded region.

EDIT: ... and even then, depending on the precise formulation of the problem, it can be impossible. Consider the following family of functions. Given Turing machines $T_0$ and $T_1$ (including specified inputs), let $$f(x) = \sum_{n=1}^\infty \left(a_n x^{n} + b_n (x-1)^{n}\right)$$ where

  1. If $T_0$ halts in exactly $n$ steps and $T_1$ has not halted by $n$ steps, $a_n = 1/n!$ and $ b_n = 0$.
  2. If $T_1$ halts in exactly $n$ steps and $T_0$ has not halted by $n$ steps, $a_n = 0$ and $b_n = 1/n!$.
  3. Otherwise $a_n = b_n = 0$.

If $T_0$ halts before $T_1$, $f(x)=0$ has the unique solution $x=0$; if $T_1$ halts before $T_0$, it has the unique solution $x=1$; if neither halts, or if they halt at the same step, all $x$ are solutions.

Note that $f(x)$ is a perfectly nice function, in fact a polynomial. The value of $f$ or any of its derivatives at a given point can be approximated with arbitrary precision by simulating sufficiently many steps of the Turing machines. But since there is no algorithm to determine whether a Turing machine halts on given input, there is no algorithm to find (or approximate) a solution to $f(x)=0$.

added 1212 characters in body
Source Link
Robert Israel
  • 54.2k
  • 1
  • 76
  • 152

There is not even an algorithm to test whether a solution exists. See e.g. Richardson's theorem.

To have something sensible, you need at least to be able to restrict the domain to a bounded region.

EDIT: ... and even then, depending on the precise formulation of the problem, it can be impossible. Consider the following family of functions. Given Turing machines $T_0$ and $T_1$ (including specified inputs), let $$f(x) = \sum_{n=1}^\infty \left(a_n x^{n} + b_n (x-1)^{n}\right)$$ where

  1. If $T_0$ halts in exactly $n$ steps and $T_1$ has not halted by $n$ steps, $a_n = 1/n!$ and $ b_n = 0$.
  2. If $T_1$ halts in exactly $n$ steps and $T_0$ has not halted by $n$ steps, $a_n = 0$ and $b_n = 1/n!$.
  3. Otherwise $a_n = b_n = 0$.

If $T_0$ halts before $T_1$, $f(x)=0$ has the unique solution $x=0$; if $T_1$ halts before $T_0$, it has the unique solution $x=1$; if neither halts, or if they halt at the same step, all $x$ are solutions.

Note that $f(x)$ is a perfectly nice function, in fact a polynomial whose $n$'th coefficient can be found exactly by simulating $n$ steps of the Turing machines. Similarly, the value of $f$ or any of its derivatives at a given point can be approximated with arbitrary precision. But since there is no algorithm to determine whether a Turing machine halts on given input, there is no algorithm to find (or approximate) a solution to $f(x)=0$.

There is not even an algorithm to test whether a solution exists. See e.g. Richardson's theorem.

To have something sensible, you need at least to be able to restrict the domain to a bounded region.

There is not even an algorithm to test whether a solution exists. See e.g. Richardson's theorem.

To have something sensible, you need at least to be able to restrict the domain to a bounded region.

EDIT: ... and even then, depending on the precise formulation of the problem, it can be impossible. Consider the following family of functions. Given Turing machines $T_0$ and $T_1$ (including specified inputs), let $$f(x) = \sum_{n=1}^\infty \left(a_n x^{n} + b_n (x-1)^{n}\right)$$ where

  1. If $T_0$ halts in exactly $n$ steps and $T_1$ has not halted by $n$ steps, $a_n = 1/n!$ and $ b_n = 0$.
  2. If $T_1$ halts in exactly $n$ steps and $T_0$ has not halted by $n$ steps, $a_n = 0$ and $b_n = 1/n!$.
  3. Otherwise $a_n = b_n = 0$.

If $T_0$ halts before $T_1$, $f(x)=0$ has the unique solution $x=0$; if $T_1$ halts before $T_0$, it has the unique solution $x=1$; if neither halts, or if they halt at the same step, all $x$ are solutions.

Note that $f(x)$ is a perfectly nice function, in fact a polynomial whose $n$'th coefficient can be found exactly by simulating $n$ steps of the Turing machines. Similarly, the value of $f$ or any of its derivatives at a given point can be approximated with arbitrary precision. But since there is no algorithm to determine whether a Turing machine halts on given input, there is no algorithm to find (or approximate) a solution to $f(x)=0$.

Source Link
Robert Israel
  • 54.2k
  • 1
  • 76
  • 152

There is not even an algorithm to test whether a solution exists. See e.g. Richardson's theorem.

To have something sensible, you need at least to be able to restrict the domain to a bounded region.