Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
Try encoding the halting of a general turing machine into a transcendental equation. –  anon Aug 30 '10 at 16:15
1  
Uh, 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. Just sayin'. –  Balarka Sen Jan 21 at 13:54
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
1  
As 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? –  Pete L. Clark Aug 31 '10 at 21:40
add comment

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
alt text

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.