This question already has an answer here:

Any algorithm or theorem to decide whether two functions that are polynomials,rationals and analytic over $\mathbb{N}$ or $\mathbb{Q}$ or $\mathbb{R}$ or $\mathbb{C}$ are equivalent ?


marked as duplicate by MJD, Joel Reyes Noche, Jonas Meyer, Claude Leibovici, Aditya Hase Nov 21 '14 at 6:27

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ What do we know about the functions? $\endgroup$ – Solomonoff's Secret Nov 21 '14 at 2:54
  • 1
    $\begingroup$ It's not clear what class of functions your referring to (since we can't just work with "functions" - we can only work with representations thereof), but this lovely theorem may be interesting to you. (Warning: Theorem is only lovely if you like things which say, "Nope, can't do that.") $\endgroup$ – Milo Brandt Nov 21 '14 at 3:14
  • $\begingroup$ @Meelo, thank you. But I have known the theorem for a long time, and possibly have known more than that. $\endgroup$ – XL _At_Here_There Nov 21 '14 at 3:18
  • 2
    $\begingroup$ @XL_at_China this is why we recommend you actually talk about your background when asking questions. From the question statement it's impossible to tell whether you know anything at all. $\endgroup$ – Kevin Carlson Nov 21 '14 at 3:23
  • $\begingroup$ @KevinCarlson Nothing is lost if that recommendation is simply ignored because answering the OP is not the only important thing here. Information that the OP might already know might be unknown for the next reader. $\endgroup$ – user194228 Nov 21 '14 at 3:26

For polynomials or for rational functions the algorithm is:

$$\text{Reduce both to a canonical form. Compare canonical forms.}$$

A canonical form can be: Sum of powers of $x$ for the case of a polynomial, and for rational functions a polynomial in canonical form plus a proper fraction with numerator and denominator in canonical form, and numerator and denominator relatively prime.

We need to show that reducing to these canonical forms is algorithmic. The one for polynomials is clear: Open parentheses and reduce common terms. Alternatively, compute the (finitely many) derivatives at the origin and write Taylor series (polynomial).

For rational functions first use long division to write as polynomial plus proper fraction. Then use Euclids algorithm to compute greatest common divisor of the numerator and denominator of the proper fraction. Finally divide numerator and denominator by the greatest common divisor.

For analytic there is no terminating algorithms. Perhaps you can compare the coefficients of a power series at certain point, but there are infinitely many coefficients to compare. This is not the proof that there is no algorithm. The proof is more complicated.

  • $\begingroup$ If you're representing real polynomials in binary, though, how can you know when to stop computing expansions of coefficients of a polynomial in standard form? Or is this just for rational polynomials? $\endgroup$ – Kevin Carlson Nov 21 '14 at 3:23
  • $\begingroup$ @KevinCarlson Considerations on algorithms are not limited to finite, binary machines. If you are just playing fool, just don't, it is boring. $\endgroup$ – user194228 Nov 21 '14 at 3:39
  • $\begingroup$ No, I'm not playing the fool, and I know about BSS machines-it just seems that people are most often interested in algorithms for finite, binary machines, since those are the machines that can be physically realized. These are the machines to which the words "computable" and "decidable" refer. If you're not even worried about finite machines, then there exists an "algorithm" to compare analytic functions, yes? $\endgroup$ – Kevin Carlson Nov 21 '14 at 3:45
  • $\begingroup$ @KevinCarlson It depends in which direction the hypercomputation goes. I think Richardson's theorem holds for real RAM. If you can do infinitely many step, sure, just check all derivatives at a point. $\endgroup$ – user194228 Nov 21 '14 at 3:52
  • $\begingroup$ @KevinCarlson Moreover, your initial question doesn't even have a point. In binary machines you can represent $\sqrt{2}$ (I just did). For the algorithms above you only need to be able to perform the arithmetic operations $(+,-,*,/)$ with the coefficients and comparison. You can deal with (for example but not limited to) algebraic coefficients expressible in radicals, for example. $\endgroup$ – user194228 Nov 21 '14 at 4:00

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