RE: [Axiom-developer] StepThrough

[Bill Page]

On November 3, 2005 4:42 AM Martin Rubey wrote:
> ...
> there are hardly any requirements on nextItem. Only 
> duplicates are forbidden, that's not much.

I was referring to:

> > only return "failed" after exhausting all elements of the
> > domain

If you can start with a unique "first" element than this is
easier. Also I am not convinced that "forbidding duplicates"
is always that easy either. Doing this could imply either
impossibly large storage requirements or run times.

> ...
> Float is -- although obviously different from the reals 
> -- a *model* for them. So it would *not* have COUNTABLE.
>

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'.

The Float domain has to do with numerical computation which,
while easier and faster than exact symbolic computation in
some respects, is actually more complicated than the real
numbers algebraically. E.g. Addition and multiplication of
floating point numbers is not associative.

On the other hand there is some very important work on
"Exact Real Numbers" and "Computable Numbers". See:

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

which in my opinion might well be said to be models for the
reals. Although these numbers are "computable" it seems to
me that it might be rather hard to construct a useful total
ordering and to compute something like 'nextItem'.

Axiom currently does not have any domain for Real that is
symbolically exact in the same sense in which the domain
Integer is exact.
 
> > As far as I know there is no operation of 'prevItem' 
> > anywhere in Axiom and implementing it in addition to
> > 'nextItem' or 'memberOf' might be challenging in some
> > peculiar cases.
> 
> No, it is trivial given nextItem.

In what sense? Of course you can always write

 prevItem(x) ==
  n=init()
  repeat
    p=n
    n=nextItem(n)
    x=n ==> p

But this could take a long time or a lot of space. Or are
you claiming there is always an effectively computable total
ordering? No partial orders?

> However, it is *necessary* for implementing
> nextItem$COUNTABLE for the Fractions, for example.
> Here comes some code:
>
> This would replace STEP in catdef.spad:
> ...
> ++ For infinite domains, repeated application of
> ++ \spadfun{nextItem} is guaranteed to reach all possible
> +  domain elements starting from the initial element.

So the main difference between Countable and the original
StepThrough category:

> ++ For infinite domains, repeated application
> ++ \spadfun{nextItem} is not required to reach all possible
> ++ domain elements starting from any initial element.

is replacing 'not required to' with 'guaranteed to' 

> 
> And here is an example for an implementation for the domain FRAC
> in fraction.spad:
> ... 
> It is a straightforward implementation of the diagonal 
> argument I posted in a previous mail.
> ... 
> Now you hopefully see what I meant: The above is code for an 
> implementation of COUNTABLE for FRAC...
>

Yes I see. The current code in Fraction is:

if S has StepThrough then
  init() == init()$S / 1$S
  nextItem(n) ==
    m:= nextItem(numer(n))
    m case "failed" =>
      error "We seem to have a Fraction of a finite object"
    m / 1

------

So although it obviously is not guaranteed to reach all
possible domain elements, it does "StepThrough" it.

> I claim that STEP is brain-dead, because it achieves much less 
> than what can be achieved.
> 

I agree. But worse than that, it seems that the current
implementation of 'nextItem' in 'Fraction' does not even meet
the requirements of 'StepThrough' for finite Fraction objects!

> ++ only return "failed" after exhausting all elements of
> ++ the domain

Regards,
Bill Page.