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 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: f849b,b8d52151b7b306d2 X-Google-Attributes: gidf849b,public X-Google-Thread: 103376,a00006d3c4735d70 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2004-01-12 08:49:56 PST Path: archiver1.google.com!news2.google.com!news.maxwell.syr.edu!newsfeed.mathworks.com!wn13feed!worldnet.att.net!207.35.177.252!nf3.bellglobal.com!news.uunet.ca!nnrp1.uunet.ca.POSTED!not-for-mail From: mwilson@the-wire.com (Mel Wilson) Newsgroups: comp.arch.embedded,comp.lang.ada Subject: Re: Certified C compilers for safety-critical embedded systems Message-ID: <2GsAAls/KX7Z089yn@the-wire.com> References: <3fe00b82.90228601@News.CIS.DFN.DE> <3ff18d4d.603356952@News.CIS.DFN.DE> <1731094.1f7Irsyk1h@linux1.krischik.com> <3ff1b8ef.614528516@News.CIS.DFN.DE> <3FF1E06D.A351CCB4@yahoo.com> <3ff20cc8.635997032@News.CIS.DFN.DE> X-Newsreader: VSoup v1.2.9.37Beta [95/NT] Date: Mon, 12 Jan 2004 10:48:06 -0500 NNTP-Posting-Host: 205.206.39.68 X-Complaints-To: abuse@ca.mci.com X-Trace: nnrp1.uunet.ca 1073926196 205.206.39.68 (Mon, 12 Jan 2004 11:49:56 EST) NNTP-Posting-Date: Mon, 12 Jan 2004 11:49:56 EST Organization: MCI Canada News Reader Service Xref: archiver1.google.com comp.arch.embedded:7340 comp.lang.ada:4354 Date: 2004-01-12T10:48:06-05:00 List-Id: In article , "Robert I. Eachus" wrote: > > >Chad R. Meiners wrote: > >> "Georg Bauhaus" wrote in message > >>>Are you sure you can say that a program that implements the Halting >>>problem for a bounded Turing machine does not implement the same >>>problem for a Turing machine? >> >> It depends what you mean by implement. I tend to think of implementations >> as algorithms (which must halt). Therefore, since there is no algorithm >> that satisfies the Halting problem's specification (it is undecidable), >> there is not an implementation. If you want to define implementation as >> something else (reasonable or unreasonable), all bets are off of course. > >Excatly, or anyother way of making my point. All physical machines have >limits even if someone builds a self-replicating von Neuman system that >keeps growing itself, it would be limited by the available matter in the >universe. But in reality, for realistic time frames even the PC on your >desk is a sufficiently close approximation to an infinite Turing >machine. Does it really matter if I give you an implementation of the >Halting problem for your PC that will always halt within a trillion >years, instead of one that does not halt for some inputs? (And are you >sure, if you had both in hand, you could tell which was which?) A lemma, or consequence (if I'm not mistaken) is that you can calculate the fate, Halting or Not-Halting, of every program in a finite set of programs S, but the program that does this can't be in S. Even if the program took a trillion years, it would take them on a bigger machine than yours. Douglas Adams' _The Hitchhiker's Guide to the Galaxy_ does nice work with this in the nest of computer-designing hyper-super computers that would calculate the question to the great answer of Life, the Universe and Everything. Regards. Mel.