On 25-Jun-01, Russell Standish wrote:
> Obviously, what you're looking for is some kind of counter example. I
> think the problem lies in not being able to determine at any point of
> the calculation just how many digits of the limit you have found.
OK, I can understand that. In order for a number to be considered
computable not only must there be an index m beyond which the the first
n places don't change, but we must be able to put a bound on m as a
function of n.
For
> the counterexample what we need is a computable series, which we know
> converges, yet we cannot compute the limit.
>
> Perhaps the more mathematically nimble might try the following example
> x_i = \sum_{j=0}^i 1/p_j, where p_j is the jth prime number. I suspect
> this is a convergent sequence, yet converges too slowly to compute the
> limit.
I don't think that's a counterexample, as Euler proved the sequence to
diverge (although *very* slowly).
Brent Meeker
>
> Cheers
>
> Brent Meeker wrote:
>>
>> On 25-Jun-01, Russell Standish wrote:
>> No - the set of computable numbers does not form a continuum.
>> Continuity is related to the concept of limits: {x_i} is a
>> convergent sequence if
>> \forall \epsilon>0, \exist N: |x_i-x_N|<\epsilon.
>> A continuous space is one for which every convergent sequence
>> converges to a limit, ie
>>
>> \exists x: \forall\epsilon>0\exists N: |x_i-x|<\epsilon \forall i>N.
>>
>> we commonly denote x by lim_{i->\infty}x_i.
>>
>> There are many convergent sequences x_i whose limits cannot be
>> computed (uncountably many, in fact).
>>
>> Thanks for the education vis a vis definition of a continuum, but now
>> I don't see why the computable numbers don't form a continuum.
>> Suppose a0,a1,a2,...ai,... is a convergent sequence of computable
>> numbers with limit A. Then it seems that A must be a computable
>> number since given any number of decimal places (or bits) n there is
>> a value of i=m such that am is equal to A for the first n places and
>>> m. Isn't this
>> the definition of a computable number - one whose representation can
>> be computed to a given accuracy in a finite number of steps? So the
>> computability of the sequence ai entails computability of the
>> sequences limit.
>>
>> thnx, Brent Meeker
>> I am very interested in the Universe - I am specializing in the
>> Universe and all that surrounds it.
>> --- Peter Cook
>>
>>
>
>
>
>
----------------------------------------------------------------------------
> Dr. Russell Standish Director High Performance Computing Support Unit,
> Phone 9385 6967 UNSW SYDNEY 2052 Fax 9385 6965 Australia
> R.Standish.domain.name.hidden Room 2075, Red Centre
> http://parallel.hpc.unsw.edu.au/rks
>
----------------------------------------------------------------------------
Regards
Received on Mon Jun 25 2001 - 22:21:26 PDT