Algorithm for computing algebraic numbers? (Why are algebraic numbers computable?)

166 Views Asked by At

Suppose $b$ is algebraic over the rationals.

In other words: $p(b) = 0$ for some polynomial where all the coefficients are rational.

I am told $b$ is computable. But why?

  1. Can I derive a polynomial from $p$ that I can evaluate to get $b$? edit: commentor clearly pointed out no. Rationals are closed under those operations.

  2. Is there some other algorithm for computing $b$ given the polynomial? edit: accepted answer: a root finding algorithm.

  3. If not what is the general argument that algebraic numbers are computable? edit: an argument that the root finding algorithm will converge.

1

There are 1 best solutions below

1
On BEST ANSWER

The answer is that iterative root-finding algorithms, like the Aberth method, exist to numerically find the roots of polynomials whose coefficients are themselves computable. Therefore if p(x) has rational coefficients, there exists a program that will produce b. So b is computable.