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-17 18:34:44 PST
Newsgroups: comp.arch.embedded,comp.lang.ada
Path: 
 archiver1.google.com!news2.google.com!news.maxwell.syr.edu!transit.news.xs4all.nl!newsfeed.xs4all.nl!xs4all!sparc!albert
From: albert@spenarnc.xs4all.nl (Albert van der Horst)
Subject: Re: Certified C compilers for safety-critical embedded systems
Organization: Dutch Forth Workshop
Message-ID: <HrLnw2.1ut.1.spenarn@spenarnc.xs4all.nl>
References: <3fe00b82.90228601@News.CIS.DFN.DE>
 <bts5ib$23a0$1@msunews.cl.msu.edu> <btsrnj$gld$2@a1-hrz.uni-duis
 <2GsAAls/KX7Z089yn@the-wire.com>
Date: Fri, 16 Jan 2004 20:36:02 GMT
Xref: archiver1.google.com comp.arch.embedded:7705 comp.lang.ada:4515
Date: 2004-01-16T20:36:02+00:00
List-Id: <comp.lang.ada>

In article <2GsAAls/KX7Z089yn@the-wire.com>,
Mel Wilson <mwilson@the-wire.com> wrote:
<SNIP>
>
>   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.

This may be a lemma, but it not a consequence of the Turing
halting problem. The latter is really fairly trivial.

Suppose you have a machine that analyses any machine whether it
stops. It prints yes or no. Now modify such that
instead of printing yes you go in an infinite loop.
Feed this modified machine to the original machine.
If it says yes it halts, than it says no, so the original
machines would have to say no too. Likewise the other
possibility leads to contradiction.

Your lemma requires a much harder proof (if it is true).

>        Regards.        Mel.
--
Groetjes Albert.
-- 
Albert van der Horst,Oranjestr 8,3511 RA UTRECHT,THE NETHERLANDS
        One man-hour to invent,
                One man-week to implement,
                        One lawyer-year to patent.