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.2 required=5.0 tests=BAYES_00,INVALID_MSGID, PLING_QUERY autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,4873305131bf4d94 X-Google-Attributes: gid103376,public From: cgreen@yosemite.atc.com (Christopher Green) Subject: Re: How big is an int? (was: Yet another stupid language war (was: ... the only languages you need!!)) Date: 1997/11/15 Message-ID: <64iper$fji@newshub.atmnet.net>#1/1 X-Deja-AN: 290126026 References: <879433137snz@genesis.demon.co.uk> <64fbr2$76k$1@route1.mdrf.france3.fr> <346C4CED.2A84@sh.bel.alcatel.be> Organization: Advanced Technology Center, Laguna Hills, CA Newsgroups: comp.lang.ada Date: 1997-11-15T00:00:00+00:00 List-Id: In article <346C4CED.2A84@sh.bel.alcatel.be>, Jos De Laender wrote: >Boyd Roberts wrote: >> >> In article <879433137snz@genesis.demon.co.uk>, fred@genesis.demon.co.uk (Lawrence Kirby) writes: >> >In article <879381995snz@genesis.demon.co.uk> >> > fred@genesis.demon.co.uk "Lawrence Kirby" writes: >> > >> >>Simply knowing a program is strictly conforming does not mean you can >> >>predict what it will output. However if you do know what input a >> >>strictly conforming program receives you should be able to predict from >> >>the standard alone what output it generates (although I'm not 100% sure of >> >>that). >> > >> >After sleeping on it it is fairly obvious that isn't true. >> >> Obviously, because you're talking about the halting problem. > > Can someone explain this more to me. (Maybe including the >halting problem, which I forget since university, and the relation >with this problem ?) [snip] Somewhat oversimplified, the Halting Problem is this: Given a programming environment that meets some rather minimal conditions (able to emulate a universal Turing machine, I believe), it is always possible to construct a program in that environment, such that it is impossible to determine whether the program will ever terminate. I will conjecture, but will not attempt to prove, that most useful programming language standards specify environments that are sufficient for the premise of the Halting Problem. If so, it is impossible to predict whether certain strictly con- forming programs will terminate. A fortiori, it is impossible to predict the entire output of such a program, and it is impossible to predict it solely from knowledge of any standard. Chris Green Email cgreen@atc.com Advanced Technology Center Phone (714) 583-9119 22982 Mill Creek Drive ext. 220 Laguna Hills, CA 92653 Fax (714) 583-9213