n8443916@unicorn.cc.wwu.edu (John Gossman) (01/16/91)
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. // ************************************************************** //
cl@lgc.com (Cameron Laird) (01/16/91)
In article <1991Jan16.000305.2989@unicorn.cc.wwu.edu> you write: . . . > 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? . . . 'Twas the lead article in the Bulletin of the American Mathematical Society of approximately June 1989, with co-authors Steven Smales, someone, and someone. Smales et al. have published a number of other versions of these ideas. I'm likely to bring some of these references to work in the next week; perhaps I'll post more details. -- Cameron Laird USA 713-579-4613 cl@lgc.com USA 713-996-8546 -- Cameron Laird USA 713-579-4613 cl@lgc.com USA 713-996-8546
root@wiis.wang.com (Superuser) (01/17/91)
>>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
tuttle@crl.dec.com (Mark R. Tuttle) (01/17/91)
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".dvjm@cs.glasgow.ac.uk (David Murphy) (01/17/91)
>In article <1991Jan16.000305.2989@unicorn.cc.wwu.edu> you write: > 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? One thing you might find of interest is X machines and the Halting Problem; Building a SuperTuring Machine. Mike Stannett, Formal Aspects of Computing, Vol. 2, No. 4. Oh, and there's something wrong with the mailer at your end; it doesn't recognise the return address it generates ... D. -- David Murphy, | JANET: dvjm@cs.glasgow.ac.uk Dept. of Computing Science, | UUCP: ..!mcsun!ukc!cs.glasgow.ac.uk!dvjm University of Glasgow, | ARPA: dvjm%cs.glasgow.ac.uk@nsfnet-relay.ac.uk Glasgow G12 8QQ, SCOTLAND + Necessity is the mother of strange bedfellows
traff@ecrc.de (Jesper Larsson Traff) (01/21/91)
On the same line, has anybody seen the article by Mike Stannett: "X-machines and the Halting Problem" in Formal Aspects of Computing, no. 2, 1990, in which the author proposes a model of computation that is strictly more powerful than the Turing-machine. It is shown that there exists a machine-instance that can solve the halting problem for Turing machines. The "new" model is a kind of analog computer, therefore a) I'm not sure the result is new, b) I don't think models of this kind captures the intuitive notion of mechanical computation c) the presentation seemed somewhat naive to me. The author claims that an approximation of the machine proposed can actually be built. If so, this is of course interesting. Comments? Jesper Larsson Traff, ECRC (traff@ecrc.de)