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-16 21:30:01 PST Path: archiver1.google.com!news2.google.com!news.maxwell.syr.edu!newspeer.monmouth.com!newshosting.com!news-xfer1.atl.newshosting.com!216.196.98.140.MISMATCH!border1.nntp.ash.giganews.com!border2.nntp.sjc.giganews.com!border1.nntp.sjc.giganews.com!nntp.giganews.com!local1.nntp.sjc.giganews.com!nntp.comcast.com!news.comcast.com.POSTED!not-for-mail NNTP-Posting-Date: Fri, 16 Jan 2004 23:29:58 -0600 Date: Sat, 17 Jan 2004 00:29:57 -0500 From: "Robert I. Eachus" User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.4) Gecko/20030624 Netscape/7.1 (ax) X-Accept-Language: en-us, en MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: Certified C compilers for safety-critical embedded systems References: In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit Message-ID: NNTP-Posting-Host: 24.34.214.193 X-Trace: sv3-MJ0C6e/xbffmWWtpuGMf3ABWxsh7F6lhOm3mTPK9EwL06skjfRrRxsv7NdC9vZIrdeZ7dkSJkqXiQuZ!E1N29SwnMblYbalVyZPdf2onhFnIGffK0SnmF5XbeMhmTiGzE8D45dm9K7rL2g== X-Complaints-To: abuse@comcast.net X-DMCA-Complaints-To: dmca@comcast.net X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.1 Xref: archiver1.google.com comp.lang.ada:4483 Date: 2004-01-17T00:29:57-05:00 List-Id: Aatu Koskensilta wrote: > The Halting Problems speaks about recursive functions. In order to make > applications of it to a real world situation, you have to be able to see > some things in the situation as being recursive functions. Otherwise > Halting Problem tells you nothing about the situation. The Halting problem and G�del's proof are two sides of the same coin, at least in computer science. The Halting problem is a constructive proof of G�del's proof. In any language without partial recursive functions, the halting problem is trivial. (All programs in that language always halt.) If a language allows partial recursive functions, then it is Turing complete, and there is no general solution of the halting problem. You can write a program that solves the halting problem correctly for some inputs. But there are either inputs for which the program produces incorrect outputs, or there are inputs for which it never halts. (And it is not difficult to prove that for some inputs, you won't be able to determine if the halting problem program will eventually halt.) -- Robert I. Eachus "The war on terror is a different kind of war, waged capture by capture, cell by cell, and victory by victory. Our security is assured by our perseverance and by our sure belief in the success of liberty." -- George W. Bush