[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: FW: data structure vs. mathematical structure (was: [Axiomdeveloper
From: 
Gabriel Dos Reis 
Subject: 
Re: FW: data structure vs. mathematical structure (was: [Axiomdeveloper] Graph theory) 
Date: 
14 Nov 2006 04:16:55 +0100 
[ Is it normal that I don't see Ralf's messages? ]
"Bill Page" <address@hidden> writes:
[...]
 So is computational complexity a relative thing, i.e. we take
 the operations from the representation as units and then express
 the complexity of the operations of the new domain in terms of
 these? Or is it an absolute thing that must be expressed in
 terms of the most primitive domain (Lisp) or even deeper in
 terms of a given hardware architecture?
relative.
 > After all that is a distincion between classic mathematics
 > and constructive mathematics.
 >

 I am not sure that I would agree that this is the right distinction.
 Ultimately in computer algebra systems I think all mathematics must
 be constructive. In a sense, that is what we mean by "algebra". An
 existence proof or a proof by contradiction is not of much use in
 such a system.

 > Example. You want to implement quicksort. Would someone choose
 > lists to do that instead of arrays?

 In Axiom this is not really an appropriate question. quicksort
 would be implemented in a generic manner so that it can be applied
 to any domain that provides the necessary methods. In fact in the
 Axiom book contains exactly this example (bubble sort actually).
However, to call it quicksort, you have to meet some algorithmic
complexity guarantee.
 > Both basically represent the mathematical idea of tuples.

 No, I don't think so. As mathematical objects lists, arrays and
 tuples are all quite distinct however I agree that they all provide
 the necessary methods on which sort may operate.
The notion of sorting is defined terms of order and permutation.
[...]
 > > For example, is an Axiom set, i.e. a member of the domain Set,
 > > a data structure or a mathematical structure?
 >
 > How expensive is it to add a new element to an existing set of
 > type Set(T) where T has no ordering function? How expensive is
 > it to add a new element to Set(T) if T provides an ordering
 > function?
 >

 All domains that have SetCategory are required to have a hash into
 SmallInteger.
That is not a mathematical requirement.
 I suppose that this means that the cost of adding
 new elements is independent of Type T.
Why?
 Re: data structure vs. mathematical structure (was: [Axiomdeveloper] Graph theory), Gabriel Dos Reis, 2006/11/13
 FW: data structure vs. mathematical structure (was: [Axiomdeveloper] Graph theory), Bill Page, 2006/11/13
 Re: FW: data structure vs. mathematical structure (was: [Axiomdeveloper] Graph theory),
Gabriel Dos Reis <=
 RE: FW: data structure vs. mathematical structure (was: [Axiomdeveloper] Graph theory), Bill Page, 2006/11/13
 Re: FW: data structure vs. mathematical structure (was: [Axiomdeveloper] Graph theory), Gabriel Dos Reis, 2006/11/14
 RE: FW: data structure vs. mathematical structure (was: [Axiomdeveloper] Graph theory), Bill Page, 2006/11/14
 Re: FW: data structure vs. mathematical structure (was: [Axiomdeveloper] Graph theory), Gabriel Dos Reis, 2006/11/14
 RE: FW: data structure vs. mathematical structure (was: [Axiomdeveloper] Graph theory), Page, Bill, 2006/11/14
 [Axiomdeveloper] Re: FW: data structure vs. mathematical structure, Ralf Hemmecke, 2006/11/14
 [Axiomdeveloper] Re: FW: data structure vs. mathematical structure, Gabriel Dos Reis, 2006/11/14
 [Axiomdeveloper] RE: FW: data structure vs. mathematical structure, Page, Bill, 2006/11/15
 [Axiomdeveloper] Re: FW: data structure vs. mathematical structure, Ralf Hemmecke, 2006/11/15
 Re: [Axiomdeveloper] Re: FW: data structure vs. mathematical structure, Martin Rubey, 2006/11/15