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,DIET_1,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 10:45:05 PST
Path: 
 archiver1.google.com!news2.google.com!news.maxwell.syr.edu!logbridge.uoregon.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 13:38:49 -0500
Organization: Michigan State University
Message-ID: <bts5ib$23a0$1@msunews.cl.msu.edu>
References: <3fe00b82.90228601@News.CIS.DFN.DE>
   <5802069.JsgInS3tXa@linux1.krischik.com>
 <1072464162.325936@master.nyc.kbcfp.com>
 <1563361.SfB03k3vvC@linux1.krischik.com>
 <11LvOkBBXw7$EAJw@phaedsys.demon.co.uk> <3ff0687f.528387944@News.CIS.DFN.DE>
 <1086072.fFeiH4ICbz@linux1.krischik.com> <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> Organization: LJK Software
 <AttdI2KzFEC2@eisner.encompasserve.org> <K5ydnZZB5rs1BWKi4p2dnA@comcast.com>
 <VK2Mb.2414$Qq.1124@nwrdny01.gnilink.net> <bts0sf$1vc3$1@msunews.cl.msu.edu>
 <tP2dndMsaLDKEpzd4p2dnA@comcast.com>
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:7277 comp.lang.ada:4339
Date: 2004-01-11T13:38:49-05:00
List-Id: <comp.lang.ada>


"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.

> If you allow the number of
> intermediate states for programs submitted to be unbounded, then you
> cannot bound the execution time for the (combination of) program and
> machine that implements the Halting problem.

This would be the specification of the Halting problem for a Turing
Equivalent machine.

> The Halting problem and a real time constraint is an impossible
> combination.

Yes, that was the point.  Writing the specification for the Halting problem
is much easier than writing the implementation since the implementation
doesn't exist.

> For that matter, anyone who works with hard real-time
> knows that you have to allow for the possibility that all of the
> constraints on the system cannot be met.  Then you have to do the
> engineering part of the job and select the right tradeoff.  (Which may
> include a higher power budget or extra weight, or even more money so you
> can build a custom chip.)

I completely agree.

> -- 
>                                            Robert I. Eachus

-CRM