Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!thunder.mcrcim.mcgill.edu!snorkelwacker.mit.edu!bu.edu!wang!news
From: root@wiis.wang.com (Superuser)
Newsgroups: comp.theory
Subject: Real Number Model of Computation
Summary: Looking for papers
Message-ID: <azcssn.3a1@wang.com>
Date: 16 Jan 91 16:35:53 GMT
Sender: news@wang.com
Organization: Mail to News Gateway
Lines: 53


>>Thanks in advance for reading this very vague request for
>>information:
>>	Some time ago, but in last 2 years, I recall a mention of
>>a theoretical model of computation involving machines that could represent
>>and operate on Real Numbers (a uncountable set of symbols anyway).
>>Does anyone out in theory land know of references, papers about any
>>such models of computation?
>>	Thanks again for any info.


>>// *************************************************************** //
>>John Gossman
>>WWU Math Dept.
>>My employer stands behind all my opinions, except in public.
>>// ************************************************************** //


I think a good place to start is the work by Lenore Blum, M. Shub & Stephen 
Smale (at U.C. Berekely & the International Computer Science Institute). They
have generalized the classical notion of computability on the natural numbers, 
N, to computability over an arbitrary ordered commutative ring with unit 
element. Three examples of this kind of ring are the natural numbers, the real 
numbers & the complex numbers. This work of their's I believe is seminal in 
computability theory because of its generalizing of computability over natural
numbers (which is an ordered commutative ring) to any ordered commutative ring.
You may have to review your abstract algebra to learn what a ring is, but that
shouldn't be too hard. Here are two of their references:

1) L. Blum, "Lectures on a theory of computation and complexity over the reals
    (or an arbitrary ring), 1989. This you can get from Lenore Blum directly.
    I will try to get her email address for you.

2) L. Blum, M. Shub, and S. Smale, "On a theory of computation and complexity
    over the real numbers: NP-completeness, recursive functions, and
    universal machines", Bull. Amer. Math. Soc., 21 (1989), pp 1-46.

1) => is a best place for an introduction and to understand the motivation for 
   their work

2) => has more meat to it.

In both I seem (??) to have found a little imprecision in the exposition 
regarding the representation of an arbritrary machine so it could be simulated
by a universal machine, i.e. their equivalent of Godel numbering. I'm
still confused about their infinite direct product of an arbitrary ring, R, 
and N, the set of natural numbers. I think there are a couple mistakes 
in the papers in this area of universal machines, but maybe I just have
a mental block.

Anyway, I believe this is great work and we will continue to hear more about 
it as it deseminated more.
of an arbitrary machine