🚀 go-pugleaf

On Apr 5, 8:40 am, Ralph Hartley <hart...@aic.nrl.navy.mil> wrote:
> 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.

Isn't the program that outputs a rational expansion going to have an
infinite loop that you are going to recognize as such?

>
> Ralph Hartley