From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII X-Google-Thread: 103376,a00006d3c4735d70 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2004-01-14 00:36:57 PST Path: archiver1.google.com!news2.google.com!news.maxwell.syr.edu!newsfeed.mathworks.com!wn11feed!worldnet.att.net!bgtnsc04-news.ops.worldnet.att.net.POSTED!not-for-mail From: David Starner Subject: Re: Certified C compilers for safety-critical embedded systems User-Agent: Pan/0.14.2 (This is not a psychotic episode. It's a cleansing moment of clarity. (Debian GNU/Linux)) Message-Id: Newsgroups: comp.lang.ada References: <4oqdnRwmhtQtd5ndRVn-jg@comcast.com> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit Date: Wed, 14 Jan 2004 08:36:57 GMT NNTP-Posting-Host: 12.72.182.207 X-Complaints-To: abuse@worldnet.att.net X-Trace: bgtnsc04-news.ops.worldnet.att.net 1074069417 12.72.182.207 (Wed, 14 Jan 2004 08:36:57 GMT) NNTP-Posting-Date: Wed, 14 Jan 2004 08:36:57 GMT Organization: AT&T Worldnet Xref: archiver1.google.com comp.lang.ada:4384 Date: 2004-01-14T08:36:57+00:00 List-Id: On Wed, 14 Jan 2004 02:07:27 -0500, Robert I. Eachus wrote: > David Starner wrote: > >> So obviously reasonable doesn't mean Turing-complete. But if it doesn't, >> where does G�del come in? It seems implausible that every "reasonable" >> language is uncompilable. A Basic subset with integer variables A-Z and >> POKE, PEEK, assignment, +, -, *, /, =, <, > and an if/then/goto construct >> is about equal to some real life Basics, so in some sense is reasonable. > > > Okay, let's try again. All major programming languages cannot be > recognized by a finite state machine. If a language can be recognized > by a FSM, it is not subject to G�del's Proof. Okay, I oversimplified the problem. But add a pair of parentheses to the above language, and it's not recognizable by a FSM. I don't see why a compiler implementing that language can't be correct. I do understand the basics of G�del's theorem. As a reasonable language, it's not that much different from the Basic's that shipped on every bitty box in the 80's. >> No completely optimizing compiler can exist for any reasonable programming >> language, but that's not what he said. Perhaps most languages in existence >> run into G�del problems on simple compilation, but I would hesitate to >> say that all "reasonable" languages fall into that category. > > I didn't hesitate, and I said it. You said it, but at least two of us don't agree. Would you care to back it up? Perhaps Ada is in that category, and template programming in C++ is compile-time Turing-complete. But what about simple languages like ISO non-extended Pascal, or Fortran 77? > All this should be standard material in any graduate level course on > computability. Not all programmers have a Masters in computer science, but I did just fine in my undergraduate class in computability.