[FOM] computing over the reals

Jeffery Zucker zucker at cas.mcmaster.ca
Thu Feb 23 00:34:55 EST 2006


>From John Baldwin:
> The lead article in the March 2006 AMS notices is entitled: Computing
> over the reals: Foundations for Scientific Computing.
> 
> Mark Braverman and Steve Cook begin with an illuminating discussion of
> the difference between the algebraic model (e.g. Blum, Shub, and Smale)
> and the bit model of computing over the reals. They continue with a more
> detailed exposition of the bit model.


In connection with this, subscribers to FOM might be
interested in two recent papers by John Tucker and myself,
listed below, which explore in some detail the relationship
(and in fact equivalence, under broad conditions) between
algebraic models and bit models -- which we call, respectively, 
abstract and concrete models of computation.
The difference between the two types of model can be
summarised by saying that abstract models, unlike concrete
models, are implementation independent.

Our abstract models differ from the BSS model in that the
basic operations (and hence all the computable functions) are
continuous with respect to the usual topology on the reals.
This is achieved by considering partiality and many-valuedness 
of functions in the abstract model.  

This work applies, more generally, to metric algebras 
such as Banach spaces.

The two papers are:


(1) ABSTRACT VERSUS CONCRETE COMPUTATION ON METRIC PARTIAL ALGEBRAS
    ACM Transactions on Computational Logic, 5 (2004), 611-668

Available from the ACM Digital Library:

http://delivery.acm.org/10.1145/1030000/1024924/p611-v_tucker.pdf?key11024924&key2=7252370011&coll=portal&dl=ACM&CFID=31683244&CFTOKEN=48614742


(2) COMPUTABLE TOTAL FUNCTIONS, ALGEBRAIC SPECIFICATIONS AND DYNAMICAL SYSTEMS
    Journal of Logic and Algebraic Programming, 62 (2005), 71-108

Available at the 2 sites:

http://scholarsportal.info/pdflinks/06012110394524004.pdf

http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6W8D-4BNVRWS-4-3&_cdi=6652&_user=1067350&_orig=browse&_coverDate=01%2F01%2F2005&_sk=999379998&view=c&wchp=dGLbVlz-zSkWz&md5=ff3abd5c62ef09870a595fc9c83bf54c&ie=/sdarticle.pdf


If you have difficulty in downloading either of these, please contact me.

Jeff Zucker

----------------------------------------------------------------------------
Dept of Computing & Software, McMaster Univ., Hamilton, Ont. L8S 4K1, Canada
zucker at mcmaster.ca        ||    http://www.cas.mcmaster.ca/~zucker
(905) 525-9140 x 23438    ||    fax  (905) 524-0340


More information about the FOM mailing list