A constructive algorithm for finding the exact roots of polynomials with computable real coefficients

In this paper we will show that it is possible to generate the roots of monic polynomials with computable real coefficients as computable complex numbers. A result from constructive analysis has already shown that the roots are computable numbers; however, because the proof is non-constructive it does not provide an effective method for finding the roots. In this work we combine two extra stages to a standard numerical algorithm: an exact error analysis, and a method for aligning sets of complex rational numbers so that the result is a set of computable complex numbers. The method of effectivization is of interest as it can be used in other situations where an algorithm will work with rational approximations, but comparison operations prevent its use with computable numbers. (C) 2002 Elsevier Science B.V. All rights reserved.