RE: [Axiom-developer] StepThrough

[Bill Page]

On November 4, 2005 1:02 PM Bertfried Fauser wrote:
> 
> Bill Page wrote: 
> > I am not exactly sure what you mean by *model* in this case
> > but I do not think Float is any more of a model for reals than
> > is Fraction Integer. It is no more difficult to define 'nextItem'
> > in Float than it is in Fraction Integer. Instead of 'numer' and
> > 'denom' we have 'mantissa' and 'exponent'.
>
> Martin Rubey wrote:
> > OK, I surrender.

> On Fri, 4 Nov 2005, C Y wrote:
> > So we're agreeing nextItem makes sense in Float?
> 
> NO! IF float is a model for 'floats' then such a domain/category
> should NOT have an attribute COUNTABLE, otherwise it may run into
> logical inconsistencies.

What inconsistencies?

> 
> I promote this opinion even if I know that an actual digital 
> computer has only a finite (not even countable!) number of such
> objects available at a moment, but one can choose at random from
> an uncountable resource and a successor function (NextItem) does
> not make sense.

But Bertfried, we are talking about exact symbolic mathematics
here.  'Float' is not a correct model for the real numbers. That
is a common mistake that is promoted by the "numericists" (people
who like to do numerical calculations). The domain 'Float' is
countable because it is determined completely by exactly two
Integers just in the same way that Fraction Integer is countable.

> 
> I am not even sure if I appreciate that one has a 'standard?'
> nextItem in the rationals. It is quite not clear, what a unique 
> (canonical) order of the rationals is.

It isn't necessary that this ordering be unique.

> Stepping through a finite or countable set means to implement a
> total order starting with the smallest element init() and ending
> with the greatest (if finite).

But this total order need not be their order in a numerical
sense. I believe that is what Martin might have meant by
reference to the "gray code"

http://en.wikipedia.org/wiki/Gray_code

I know this sort of ordering is related to "z-ordering" in the
context of database theory. It also comes under the names of
"linear clustering" and space-filling curves (e.g. Hilbert curve).
See for example:

http://citeseer.ist.psu.edu/lawder01querying.html

> (Streams are infinite such things and I do not really see why one
> should not even have a sort of 'stream' object if a category has
> countable, something like nextItem() is nothing but a stream
> (isn't it?)

Yes.

> However a set may have many total orderings which can be
> different, hence its not canonical.
>

I agree.
 
> Eg what are the nextItems of partitions, compositions, etc. This
> is a concept which depends on an order. So first we would need to 
> introduce an (total) order then there is a canonical nextItem.
> 
> Partitions can be partially ordered, so that you do not find a
> unique successor,...

I think that 'nextItem' can be defined in a partial order but
not a unique 'previousItem' (or vice versa).

> 
> Moreover, stepping through a set might need other (efficiency,
> logical) structures, you might have a look at Don Knuth prefascicles 
> of his TAOCP
> http://www-cs-faculty.stanford.edu/~knuth/taocp.html where eg 
> codes are discussed so that you step through binary strings and in
> each step exactly one bit changes and other such options. Any such
> option needs a further nextItem()

Yes, these are gray codes or something like them.

> 
> > > Since the set of computable numbers is countable and we 
> > > can clearly only define domains containing computable numbers
> > > in Axiom, all domains would have COUNTABLE. Of course for some
> > > domains it will be more difficult to come up with an enumeration
> > > than for others.
> >
> > Indeed.
> 
> You can algebraically define %pi and %e, of course you cannot
> give a digital or decimal presentations, but would that be
> desirable? %pi is fine for me ;-)

This is not a matter of algebraic definition. Yes you can give
a digital representation. The thing is, it is just not finite.
The essence of the idea of exact real numbers is that it is
possible to finitely encode an algorithm which will compute
%pi (or any other "computable" real number) as an infinite stream
of digits. In any given computation though one does need the
entire infinite stream. Still one can treat the algorithm itself
as the representation of such a number.

This has been studied in some detail and there are some proposed
efficient implementations. Please see the "Some History" section
of:

http://wiki.axiom-developer.org/RealNumbers

Regards,
Bill Page.