Being motivated by this post, I was wondering if there is a proof (analogous to the case of Diophantine equations) that there is no general method for solving transcendental equations? It seems pretty clear, intuitively, that there can be no general method; but the only reason I feel strongly about that is because I can't conceive that transcendental equations have a general method, but Diophantine equations don't. I was never able to understand the proof for the case of Diophantine equations, so I am not in a position to even know where to begin thinking about this. Has any work been done on this problem?
Is there a proof that there is no general method to solve transcendental equations?
-
2Try encoding the halting of a general turing machine into a transcendental equation. – 2010-08-30
-
1Uh, this is an old question, I agree, and there is no sense in posting something after all the answers are well-accepted and voted, but I see that none of the answers below mention that this question essentially asks for the [_Constant problem_](http://en.wikipedia.org/wiki/Constant_problem). Just sayin'. – 2014-01-21
3 Answers
A general method for solving a given equation $H(x)=0$ is to apply the compositional inverse $H^{-1}$ of $H$: $x=H^{-1}(0)$. In general, $H$ and $H^{-1}$ are correspondences. But often it is possible to split the problem into subproblems where $H$ and $H^{-1}$ are functions.
For applying this method, $H$ and $H^{-1}$ have to be known. That means they have to be in closed form (Wikipedia: Closed-form expression). "Closed form" means expressions of allowed functions. If an equation is solvable in closed form depends therefore on the functions you allow.
There is a general method for the elementary functions.
The elementary functions are according to Liouville and Ritt those functions of one variable which are obtained in a finite number of steps by performing algebraic operations and taking exponentials and logarithms (Wikipedia: Elementary function).
The incomprehensibly unfortunately hardly noticed theorem of Joseph Fels Ritt in [Ritt 1925] Ritt, J. F.: Elementary functions and their inverses. Trans. Amer. Math. Soc. 27 (1925) (1) 68-90 answers which kinds of Elementary functions can have an inverse which is an Elementary function. You can also take the method of Rosenlicht, M.: On the explicit solvability of certain transcendental equations. Publications mathématiques de l'IHÉS 36 (1969) 15-22.
If $H$ can be decomposed into compositions of algebraic functions and other known Standard functions than $\exp$ and $\ln$, an analog theorem to the theorem of Ritt of [Ritt 1925] could be applied. I hope to prove such a generalization of Ritt's theorem for this class of functions.
-
1Please stop editing all your old answers and bumping them up to the front page. – 2017-11-16
Intuition may be misleading here. In fact transcendental cases are often much easier than the integer Diophantine case. For example below is a table listing the known decidability results in various rings for Hilbert's tenth problem and the full first order theory, excerpted from Bjorn Poonen's interesting paper Hilbert's tenth problem over rings of number-theoretic interest
Yes. The problem is that the term "transcendental function" is absurdly general. For example, pick a computable bijection between the integers and the set of Turing machines and consider the function $f : \mathbb{R} \to \mathbb{R}$ which is $0$ on the integers corresponding to halting Turing machines, $1$ on the integers corresponding to non-halting Turing machines, and smoothly interpolated in between (for example via bump functions) such that if $x$ is not an integer then $0 < f(x) < 1$. Then the problem of determining the solutions to $f(x) = 1$ is equivalent to the halting problem. (And $f$ is even smooth.)
So to get any reasonable answer to this question one must pick a much more specific definition of transcendental function. One must also specify what it means to find a solution to an equation; is it enough to give an algorithm which will compute it to arbitrary accuracy, or must we get the answer in "closed form" (whatever that means)? There are a lot of issues here.
-
1As you point out, the problem is that -- wikipedia article notwithstanding -- there is not an agreed upon definition of "transcendental function". I was thinking about this question a bit myself and had decided that a transcendental function should be a complex analytic function on $\mathbb{C}^n$ which is not algebraic. Suppose we ignore the non-algebraic part and just ask whether there is an algorithm to tell whether a system of (recursive?) complex-analytic functions has a common solution. What do we think about that? – 2010-08-31