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-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-11 18:20:20 PST
Path: 
 archiver1.google.com!news2.google.com!news.maxwell.syr.edu!newsfeed.media.kyoto-u.ac.jp!newsfeed.icl.net!newsfeed.fjserv.net!news-FFM2.ecrc.net!nntp.abs.net!ash.uu.net!news.tufts.edu!elk.ncren.net!nntp.upenn.edu!msunews!not-for-mail
From: "Chad R. Meiners" <crmeiners@hotmail.com>
Newsgroups: comp.arch.embedded,comp.lang.ada
Subject: Re: Certified C compilers for safety-critical embedded systems
Date: Sun, 11 Jan 2004 21:13:53 -0500
Organization: Michigan State University
Message-ID: <btt08e$2pnv$1@msunews.cl.msu.edu>
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>
 <bsumbs$k9e$2@a1-hrz.uni-duisburg.de>
    <AttdI2KzFEC2@eisner.encompasserve.org>
 <K5ydnZZB5rs1BWKi4p2dnA@comcast.com>
 <VK2Mb.2414$Qq.1124@nwrdny01.gnilink.net> <bts0sf$1vc3$1@msunews.cl.msu.edu>
 <tP2dndMsaLDKEpzd4p2dnA@comcast.com> <bts5ib$23a0$1@msunews.cl.msu.edu>
 <btsrnj$gld$2@a1-hrz.uni-duisburg.de>
NNTP-Posting-Host: arctic.cse.msu.edu
X-Priority: 3
X-MSMail-Priority: Normal
X-Newsreader: Microsoft Outlook Express 6.00.2800.1158
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1165
Xref: archiver1.google.com comp.arch.embedded:7297 comp.lang.ada:4345
Date: 2004-01-11T21:13:53-05:00
List-Id: <comp.lang.ada>


"Georg Bauhaus" <sb463ba@l1-hrz.uni-duisburg.de> wrote in message
news:btsrnj$gld$2@a1-hrz.uni-duisburg.de...
> In comp.lang.ada Chad R. Meiners <crmeiners@hotmail.com> wrote:
> :
> : "Robert I. Eachus" <rieachus@comcast.net> wrote in message
> : news:tP2dndMsaLDKEpzd4p2dnA@comcast.com...
> :> Chad R. Meiners wrote:
> :>
> :> > Not always true---we can specify the Halting problem (for a Turing
> :> > Equavilent machine), but we cannot implement it without an oracle.
> :>
> :> Actually not quite true.  It is not hard to write a program that
> :> implements the Halting problem, and for any finite machine, it will
> :> always return the correct answer.
> :
> : This would be a specification for the Halting problem for a bounded
Turing
> : Machine.
>
> 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?

<humor>
Of course you can SAY it! I just did ;-)
</humor>

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.

-CRM