Xref: utzoo comp.theory:1785 comp.lang.functional:725 Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!rex!fs From: fs@rex.cs.tulane.edu (Frank Silbermann) Newsgroups: comp.theory,comp.lang.functional Subject: Re: do computers believe in real numbers? Message-ID: <6924@rex.cs.tulane.edu> Date: 7 Apr 91 20:05:10 GMT References: <91090.154205NN1@awiwuw11.wu-wien.ac.at> <6878@rex.cs.tulane.edu> Organization: Computer Science Dept., Tulane Univ., New Orleans, LA Lines: 37 >> Also, consider the fact that mathematics >> has not given us any single notation >> suitable for expressing _every possible_ >> computable function over the reals (or even the rationals). In article rjc@cstr.ed.ac.uk (Richard Caley) writes: > Apologies if I am being slow, but if a function is computable, > does that not imply that it can be denoted in some notational > scheme which someone has decided is a reasonable model > of `computation' (e.g. TMs, Markov Algorithms or whatever). A Turing-complete formalism can _model_ the computation of any computable function. That does not mean that every such formalism can _directly express_ every computable function. For instance, you can model any parallel computation with a sequential Turing machine, but you cannot using a sequential Turing machine to _directly express_ parallel computation. Most mathematicians working with real arithmentic care only that their ad-hoc notations communicate the concepts and relations (e.g. functions) that interest them at the moment. Most do not concern themselves that their notation is complete -- i.e. that they have set up a language suitable for expressing every possible computable function over the reals. When the topic of discourse changes, the notation is enriched as needed. When trying to design a functional programming language to work with objects of a given semantic domain, I analogously argue that we ought not require that the function from syntax to semantic domain (expressed by the denotational equations) be "onto", i.e. that full abstraction is a luxury we cannot always afford. (This has nothing to do with the language's Turing equivalence.) Frank Silbermann fs@cs.tulane.edu Tulane University New Orleans, Louisiana USA