NetNews Usenet Archive 1992 #20/NN_1992_20.iso/spool/sci/math/11300

Internet Message Format | 1992-09-11 | 1.6 KB

Path: sparky!uunet!cis.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!ucbvax!WATSON.IBM.COM!lucas
From: [e-mail] ("Bruce Lucas")
Newsgroups: sci.math
Subject: computable reals
Message-ID: <[e-mail]>
Date: 12 Sep 92 04:24:12 GMT
Sender: [e-mail]
Lines: 25

In a related vein to the recent discussion about the "computability of
the universe", I have always found it in some way a little disturbing
that we feel compenent to reason about uncountable sets such as the reals
using a language that, being based on discrete symbols, can actually only
represent a countable subset of them.

So, suppose we decided to limit the discussion to the set of "computable"
reals.  This set could be defined in a number of ways which I suspect
are all equivalent: for example a real is computable if there is a
computable function f(n) that produces its nth digit; or, a real is
computable if there are computable functions f(n) and g(n) that produce
an approximation f(n)/g(n) to within 1/n.

This gives us a countable set that forms a field and contains all the
"useful" reals (pi, e, sqrt(2), ..., and in fact probably all the reals
anyone would want to talk about except bizarre examples described by
diagonalization to prove that the set of reals isn't countable).  It
has the satisfying property that we could actually write down a
representation of any member of the set.

My question is is this in any way an interesting thing to do?  For example,
what properties of the reals does this set have and which does it lack?

Cheers,
Bruce Lucas