Re: Proposal: 6NF

On 2006-10-18, Marshall wrote:

> I would be hard pressed to figure out how to represent an uncomputable
> number with a computer. Unless we give it a name like, say, "Fred" and
> store "Fred" as a string. But then we're representing the name of the
> value, and not the value itself.

That's what computer algebra systems routinely do with transcendental numbers like pi and e. Also, if you think about it a bit, each fixed width representation of numbers is essentially a similar enumeration of a finite set of real values, each bignum scheme is (ideally) an enumeration of a countable set, and obviously no uncountable set can be enumerated.

This way of looking at things might seem a bit weird, but it becomes relevant when we note that the countable sets enumerated by bignums in different prime bases are already mutually incomparable: none of them properly contains the other ones. For example, 1/5 is exactly 0.2 in base 10 and so you can represent it precisely using a small fixpoint decimal, but no finite representation will suffice in binary. From the point of view of binary, 1/5 is almost as nasty as pi or e. There's also no reason why you couldn't work in arbitrary binary fractions of 5 or e, which would make those numbers exactly representable (and 1/2 less so), or in fact go with any countable basis of reals and, say, their fractional linear combinations (which is essentially what base 10 is for the two element basis {2,5} and number fields are for bases which include irrational but still algebraic reals).

So, when we pick a particular base for our system of numbers, we're already picking an arbitrary basis of real numbers on which to calculate. It's already about names instead of values proper, and there's really no shame in including "Fred" in the basis as well.

From this perspective, you can always name any number and compute with it using its known algebraic properties (which aren't accessible in the case of uncomputable numbers.) However, you can never escape the fact that any computable system of numbers is at most countable, and so of measure zero when embedded inside the reals. Any countable set of numbers can be enumerated and any finite subset of it can be manipulated, but it's always guaranteed that the vast majority of real numbers lies beyond the reach of your representation. Usually the only way around that dilemma is to resort to approximation, which is enabled by the density of e.g. finite fractions within the reals, and of different families of e.g. polynomials of finite degree within broad classes of real functions.

Once we've decided to approximate, efficiency in working with high precision is then what counts. That's why fixpoints, floats and rationals are so important. It's not because they're somehow fundamentally more representable than the rest of the reals, but because real algebraic operations on them can be neatly reduced to integer arithmetic and that in case can be efficiently implemented in binary, thanks to the algebraic regularity of this particular naming scheme.

-- 
Sampo Syreeni, aka decoy - mailto:decoy_at_iki.fi, tel:+358-50-5756111
student/math+cs/helsinki university, http://www.iki.fi/~decoy/front
openpgp: 050985C2/025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2