🚀 go-pugleaf

On 03/30/2011 10:21 AM, Daryl McCullough wrote:
> (1) If you view reals as equivalence classes 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)

Real numbers with that property are called "recursively enumerable" 
(r.e.). Generally they are *not* thought of as computable. The normal 
definition of computable reals are "recursive" numbers, which can be 
calculated to any desired accuracy.

A real number x is recursive if there is a computable function F from 
positive rationals to rationals such that |F(epsilon)-x|<=epsilon.

An example of a number that is r.e. but not r. is Chaitin's constant 
Omega, the probability that a random program will halt. It does have a 
computable a Cauchy sequence (compute the probability that one of the 
first i  programs is chosen and halts in less than i steps), so it 
satisfies (1), but there is no program that can compute it to a given 
accuracy. The sequence converges, but it is undecidable how close a 
given term is to the limit.

The computable (recursive) functions are a countable algebraically 
closed field.

You can think of computable reals as an equivalence classes of programs 
that satisfy the requirements for defining a computable real (something 
like for all x,y |F(x)-F(y)|<x+y), with F~G iff for all x |F(x)-G(x)|<=2x

If you wanted to avoid equivalence classes, each computable real could 
be represented by the shortest program that computes it. However, given 
a program, there is is no algorithm for determining the shortest program 
that computes the same number.

For that matter, there is no algorithm that determines if a program 
represents zero, or represents a real number at all.

Ralph Hartley