🚀 go-pugleaf

On 03/30/2011 10:21 AM, Daryl McCullough wrote:

> Here are two ways to think about computability for
> reals: (Off the top of my head, this is probably not
> the way that computability theorists would think of it).
>
> (1) If you view reals as equivalence classes of [sequences of] rationals,
> then you can define a function f from reals to reals to be
> computable if there is a corresponding computable function
> F from rationals to rationals such that whenever
> limit of q_0, q_1, ... = r
> then
> limit of F(q_0), F(q_1), ... = f(r)

The extrapolation from the previous post would be to define a real as a 
*particular* sequence of rationals.

If we require that the representation of a rational (as a real) be a 
constant sequence, then arithmetic on rationals would be computable.

Of course there are some problems with this. In the rational case there 
is a algorithm that finds the representative of any member of the 
equivalence class (divide both numbers by their gcd), but it is not even 
possible to tell if two Cauchy sequences are the same by examining a 
finite number of terms.

You could try to add additional requirements on canonical sequences, but 
there are already problems with the existing one. For example, what is 
the sequence for pi+e? It is represented by a constant iff it is 
rational. No one knows if it is rational or not, so its canonical 
sequence isn't known, even though it's decimal expansion is easy to compute.

Given a program that outputs a decimal expansion, it is undecidable if 
the resulting number is rational or not, so there are computable (in the 
normal sense) real numbers who's canonical sequence is not computable.

Ralph Hartley