Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!thunder.mcrcim.mcgill.edu!snorkelwacker.mit.edu!bloom-beacon!deccrl!news.crl.dec.com!tuttle
From: tuttle@crl.dec.com (Mark R. Tuttle)
Newsgroups: comp.theory
Subject: Re: Real Number Model of Computation
Message-ID: <1991Jan16.172311.1908@crl.dec.com>
Date: 16 Jan 91 17:23:11 GMT
References: <1991Jan16.000305.2989@unicorn.cc.wwu.edu>
Sender: news@crl.dec.com (USENET News System)
Organization: DEC Cambridge Research Lab
Lines: 25
In-Reply-To: n8443916@unicorn.cc.wwu.edu's message of 16 Jan 91 00:03:05 GMT

In article <1991Jan16.000305.2989@unicorn.cc.wwu.edu> n8443916@unicorn.cc.wwu.edu (John Gossman) writes:

   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?

FOCS 88 had a paper "On a Theory of Computation over the Real Numbers: NP
Completeness, Recursive Functions and Universal Machines" by L. Blum, M.
Schub, and S. Smale (pages 387-397).

The abstract reads: "We present a model for computation over an arbitrary
(ordered) ring R.  In this general setting, we obtain universal machines,
partial recursive functions, as well as NP complete problems.  While our
theory reflects the classical over Z (e.g., the computable functions are the
recursive functions) it also reflects the special mathematical character of the
underlying ring R (e.g., complements of Julia sets provide natural examples of
R.E. undecidable sets over the reals) and provides a natural setting for
studying foundational issues concerning algorithms in numerical analysis.

Mark Tuttle

P.S. Mail sent to n8443916@unicorn.cc.wwu.edu fails with the error message
"Service unavailable".