Are any decisions required to be made in their implementation? If so, they are nontrivial. If not, they are trivial.
I was saying that for every general case in which a zero of a polynomial is guaranteed, there is a deterministic path to determine what the guaranteed zeros are.
Hrm. Is there a short proof of this claim? It’s not completely obvious to me. How do you know there isn’t some set of n-th degree polynomials, for which there’s a non-constructive proof that they have roots, but where there isn’t any known algorithm for finding them?
I suppose you could always do numeric evaluation with bisection or somesuch, since polynomials are smooth. But I think you’re saying something more than “iterative numerical methods can find zeros of polynomials over one variable.” I also imagine that you don’t want to include “explore all possible decision trees” as a valid solution method.
Part of my hesitation is that there are classes of equation (not polynomial) for which it’s believed that there aren’t efficient algorithms to find solutions. For instance, suppose we have a fixed g, k, n. There’s no known efficient technique to find x such that g^x = k, mod n. (This is the discrete logarithm problem.) It seems thinkable to me that there are similar cases over the reals, but where you can’t do exhaustive search.
Yes. I’m aware of them. But that’s not quite the question here. The question was whether there were equations that have solutions, that can be found, but where there’s no algorithm to do so. So by definition the numbers of interest are definable in some way more succinct than their infinite representation.
As a nitpick: My understanding is that algebraic just means a number is the root of some polynomial equation with rational coefficients. But that’s not the same as “cannot be described except with an infinite decimal string.” A number might be described succinctly while still being transcendental. The natural logarithm base is transcendental—not algebraic—but can be described succinctly. It has a one-letter name (“e”) and a well known series expression that converges quickly. I think you want to refer to something like the non-computable reals, not the non-algebraic reals.
Are any decisions required to be made in their implementation? If so, they are nontrivial. If not, they are trivial.
I was saying that for every general case in which a zero of a polynomial is guaranteed, there is a deterministic path to determine what the guaranteed zeros are.
Hrm. Is there a short proof of this claim? It’s not completely obvious to me. How do you know there isn’t some set of n-th degree polynomials, for which there’s a non-constructive proof that they have roots, but where there isn’t any known algorithm for finding them?
I suppose you could always do numeric evaluation with bisection or somesuch, since polynomials are smooth. But I think you’re saying something more than “iterative numerical methods can find zeros of polynomials over one variable.” I also imagine that you don’t want to include “explore all possible decision trees” as a valid solution method.
Part of my hesitation is that there are classes of equation (not polynomial) for which it’s believed that there aren’t efficient algorithms to find solutions. For instance, suppose we have a fixed g, k, n. There’s no known efficient technique to find x such that g^x = k, mod n. (This is the discrete logarithm problem.) It seems thinkable to me that there are similar cases over the reals, but where you can’t do exhaustive search.
There exist what is called non-algebraic reals, which cannot be described with anything other than the infinite string of decimals they are.
Yes. I’m aware of them. But that’s not quite the question here. The question was whether there were equations that have solutions, that can be found, but where there’s no algorithm to do so. So by definition the numbers of interest are definable in some way more succinct than their infinite representation.
As a nitpick: My understanding is that algebraic just means a number is the root of some polynomial equation with rational coefficients. But that’s not the same as “cannot be described except with an infinite decimal string.” A number might be described succinctly while still being transcendental. The natural logarithm base is transcendental—not algebraic—but can be described succinctly. It has a one-letter name (“e”) and a well known series expression that converges quickly. I think you want to refer to something like the non-computable reals, not the non-algebraic reals.
Yes, the distinction is this:
http://en.wikipedia.org/wiki/Computable_number
http://en.wikipedia.org/wiki/Algebraic_number