Why Has None of Computer Science been Formalized?
in [Logic]
|
Prev: Simple yet Profound Metatheorem
Next: Modal Logic
From: Jack Campin - bogus address on 18 Sep 2006 09:00 >>> from a formal point of view, no program that uses a function that >>> computes the root of 2 terminates. Any function using such a function >>> that does terminate is employing a pragmatic that results in >>> implementation specific behavior. >> You seem to be thinking of conventional imperative implementations. >> There's nothing very implementation-specific about a lazy functional >> version of square root - it will generate as many places of precision >> as the caller asks for, and you need know nothing about the hardware >> or the compiler technology to know what answers you'll get. > That is a fair observation. What do you plan to do with your arbitrary > precision value of root 2 when you have it? Are you going to use it in > an operation? If so, will you be able to maintain the specified > accuracy? The accuracy is determined by the caller. Traditional (pre-computer) error analysis will work fine. The nice thing about lazy computation is that a lot of it can be deferred to run-time - you still need to structure expressions to avoid blow-ups, but the details of how much precision you need in subsidiary parts of a computation to guarantee a specific precision in the answer can be worked out on the fly. Googling "haskell numerical analysis" shows quite a few approaches to this. (Being able to do numerical analysis properly was one of the design goals of Haskell). Your suggestion of using continued fractions is certainly possible, and has been done in experimental implementations, but I doubt you could get acceptable performance out of it - the period length will blow up with simple arithmetical expressions, and real-world constants in the computation will usually have unreasonably long periods to begin with. > Since when is root 2 a real number? It is in most programming language type systems. What else do you want it to be? (I know of an extension of Algol68 that allocated a type for every algebraic extension of the rationals, so there could have been a more refined answer in that system - you could do that in Haskell if you wanted, I guess). ============== j-c ====== @ ====== purr . demon . co . uk ============== Jack Campin: 11 Third St, Newtongrange EH22 4PU, Scotland | tel 0131 660 4760 <http://www.purr.demon.co.uk/jack/> for CD-ROMs and free | fax 0870 0554 975 stuff: Scottish music, food intolerance, & Mac logic fonts | mob 07800 739 557
From: Charlie-Boo on 18 Sep 2006 09:23 Steven Zenith wrote: > Charlie-Boo wrote: > > "Computable" refers to manipulating recursively enumerable sets (e.g. > > integers or character strings), not the real numbers. > Since when is root 2 a real number? You're saying that the square root of 2 isn't a real number? OMG You don't even know fundamental mathematics. C-B > With respect, > Steven
From: Charlie-Boo on 18 Sep 2006 09:29 Steven Zenith wrote: > A function terminates when it produces a result > (and one might possibly add "and performs no further action"). When a function produces a result, it's called "defined". There are no other "actions" that a function does. A program terminates or not, and can perform other actions. Your terminology is all screwed up. This conversation has degrade to being so dumb - I can't teach you basic concepts of Mathematics and computer programming. Sorry. C-B > With respect, > Steven
From: Charlie-Boo on 18 Sep 2006 09:35 Steven Zenith wrote: > Charlie-Boo wrote: > > How about zero times the square root of 2? > > That is an interesting case. And the answer in practice will be, it > depends (an optimizer may remove the expression, an interpreter may > disregard the function root 2 - all on the basis of the zero). > > But the answer formally is no, it does not terminate - because the > function that computes the root of 2 does not terminate. Functions don't terminate. Functions are defined or not. Programs terminate or not. No program can return the infinite decimal expansion of the square root of 2 because computers produce only finite outputs when they terminate. However, computers can manipulate a symbolic representation of the square root of 2. This is what Mathematica does. Please learn about the basic concepts and terminology of mathematical functions and computer programming. C-B > With respect, > Steven
From: Charlie-Boo on 18 Sep 2006 09:56
Steven Zenith wrote: > Charlie-Boo wrote: > > Steven Zenith wrote: > > > > > I have referred you to the relevant literature that more than > > > adequately explains the formalism and methods of transformation. > > > > No it doesn't. It is your responsibiity to prove your point. > > It is not my responsibility to do your work for you. Following > references is a well established and practical convention. I simply do > not have the time to teach you. You have the time to write about 10 pages of claims, but not enough time to write 1/2 page giving the formalization of some results to prove your claims? I see. Ok, I'll do the work. . . . Hmmm . . . Gee, there is no result as you describe. I have done the work, and the conclusion that I reach is that there is no formalization of any branch of Computer Science. Do you somehow reach a different conclusion? How's that? Since 1977 (when I developed my 8 Rules of Inference for creating computer programs - see my ARXIV paper) I have read on the order of 1,000 articles, conference proceedings papers, internet sites and books, from the Harvard McKay library, the MIT Barker library (photocopies), the Boston Publc library (which can obtain books from any public library in Massacusetts), PhD Thesis reprints, from the Harvard Coop, amazon.com, and used book dealers throughout the United States to obtain my own copy of out-of-print books. I just haven't found it, myself. Exactly what were you referring to (that I must have missed somehow)? What branch of Computer Science is it that has been formalized? What results have been shown formally? What are the formal expressions that represent them? You can end my 29 year quest in 5 minutes! Thanks, C-B > With respect, > Steven |