[FOM] When is it appropriate to treat isomorphism as identity?

Vaughan Pratt pratt at cs.stanford.edu
Thu May 21 18:26:18 EDT 2009



On 5/21/2009 2:31 AM, karim zahidi wrote:
 > On Wed, 20 May 2009, Andrej Bauer <andrej.bauer at andrej.com> wrote:
>> Here is an example: a well educated computer scientist typically knows
>> that a polynomial (with real coefficients) has finitely many roots. He
>> therefore naturally expects that there is a thing called "the number of
>> distinct roots of a polynomial". Surely, such a simple number can be
>> computed, yes? No.
>>
>
> I'm a bit confused by this remark. Surely if the coefficients themselves
> are rational numbers (or even computable real numbers) then this number is
> computable. I guess it comes out of the elimination theory for the reals.

Consider (x+c)^2 where c is 1/n in case a given Turing machine halts 
within n > 0 steps, or zero if it never halts.  c is a computable real 
number (it can be computed to within any desired precision), but if you 
could decide whether (x+c)^2 had zero or one real root you would have 
decided whether the given Turing machine halts.

Vaughan Pratt


More information about the FOM mailing list