[FOM] When is it appropriate to treat isomorphism as identity?
Vaughan Pratt
pratt at cs.stanford.edu
Thu May 21 18:31:27 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^2 + c where c is 1/n in case a given Turing machine halts at
step n (counting from n = 1), 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^2 + c 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