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.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 10db24,77f71d0bde4c5bb4 X-Google-Attributes: gid10db24,public X-Google-Thread: 103376,86fd56abf3579c34 X-Google-Attributes: gid103376,public From: cpp@netcom.com (Robin Rowe) Subject: Re: What good is halting prob? Date: 1995/04/20 Message-ID: #1/1 X-Deja-AN: 101283291 sender: cpp@netcom6.netcom.com references: <3kaksj$iur@isnews.calpoly.edu> <3n285v$9vl@news.cais.com> organization: NETCOM On-line Communication Services (408 261-4700 guest) newsgroups: comp.lang.ada,comp.edu Date: 1995-04-20T00:00:00+00:00 List-Id: In article , Robert Dewar wrote: >Robin is certainly right to point out that a program on its own cannot >usefully be said to be correct or incorrect.... I didn't go quite that far. I can envision the program itself being the specification. In fact, I see no other way to guarantee that a program really matches its specification. >But Robin, don't make the mistake of assuming that because a problem is >undecidable it is impossible to write a program that decides it in >most or some cases. Not only don't I make this mistake, it is the tendency toward that misconception on the part of halting problem believers that made me question its value in the first place. However, now that I've used the halting problem a couple time in replies on this thread I have new respect for the halting problem's usefulness. >then our task as a programmer is simply to avoid the cannot_tell cases >in our programs if we are interested in correct programs. In practice it is not feasible to statically eliminate the cannot_tell cases because a real computer doesn't have an infinite tape (or time). It can be painted into a corner. What I think is achievable is to design a program that knows it doesn't know and fails gracefully. Robin -- ----- Robin Rowe cpp@netcom.com 408-626-6646 Carmel, CA Rowe Technology C++ Design/Training Email for sample C++ Newsletter!