[FOM] Computing roots of a polynomial (was: isomorphism as identity)

Daniel Méhkeri dmehkeri at yahoo.ca
Fri May 22 19:46:10 EDT 2009

> Andrej, since your answer isn't entirely consistent with mine,
> maybe we should compare notes.  In my example of the polynomial
> x^2 + c where c is 1/n if a certain Turing machine halts at the
> n-th step and 0 otherwise, c meets the criterion for being a
> computable number.  However c is also clearly rational, we just
> don't find out which rational until T halts, and may never find
> out, in which case c = 0, which is still rational.

> To sort this out you might want to further specify that the rational
> coefficients are presented in some pre-agreed normal form for which
> equality is decidable.

> The concept of a rational number divorced from its representation is
> intrinsically nonconstructive.  Constructive analysts probably shouldn't
> talk about rational numbers at all, or integers for that matter, other
> than perhaps as a way of speaking about some pre-agreed representation
> of them for which equality is decidable, and then only in situations
> where there is no danger of this sort of confusion.

I guess we have stumbled on a neat example where classical recursion
theory and constructive mathematics are at odds: a constructive
mathematician would disagree that c is rational! (To say
"either T halts or it doesn't" is of course not kosher.)

So it would be correct, as is, to say that for rational coefficients
the roots are computable, without worry about the representation
concerns mentioned. 



      Découvrez les styles qui font sensation sur Yahoo! Québec Avatars.

More information about the FOM mailing list