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: 103376,86fd56abf3579c34 X-Google-Attributes: gid103376,public X-Google-Thread: 10db24,77f71d0bde4c5bb4 X-Google-Attributes: gid10db24,public From: crawford@cais2.cais.com (Randolph Crawford) Subject: Re: What good is halting prob? Date: 1995/04/19 Message-ID: <3n285v$9vl@news.cais.com> X-Deja-AN: 101107947 references: <3kaksj$iur@isnews.calpoly.edu> <3mve9b$gaj@news.cais.com> organization: Capital Area Internet Service newsgroups: comp.lang.ada,comp.edu Date: 1995-04-19T00:00:00+00:00 List-Id: In article , Robin Rowe wrote: >In article <3mve9b$gaj@news.cais.com>, >Randolph Crawford wrote: >>If you can identify a different problem as being basically the same as >>the halting problem.... > >The "if" was the point of my question. How do you prove equivalence to >the halting problem? Short of formal substitution or equivalence proofs, you recognize the same potential for failure, the likelihood that your program will not terminate as expected due to the introduction of data whose influence you cannot anticipate. > >>Let's say you wrote a program that you wanted to be "correct". >>[...] It behaves as it should, it halts, it's deterministic >>and decidable. You might conclude from having writen such a program that >>with enough effort on the part of the programmer, *every* program could be >>written the way this one was, ensuring correctness. But you'd be mistaken. > >Well, if anyone can write one non-trivial program to be "correct" I would >then be willing to reconsider if the general case is attainable. Until >then, I'm not in much danger of falling into the trap you suggest. If >someday machines become more intelligent than we are, correctness may >become very difficult to judge. Correctness itself is a very subjective term. You want a trivial correct program? main() { if (1) exit( 0); } It ain't much, but it's correct. It's easy to write correct programs. It's just that some programs (the UTMs or those programs that contain UTMs) can never be proven correct. And correctness is not subjective. It simply means that the program will always behave as expected, regardless of the input. If by correctness, you are thinking of "not incorrect", or "acceptably correct", there's a difference. You're talking about points on a continuum. Correct is clear at one end; it's perfect. You can write a program that performs properly in most or nearly all cases but fails to terminate under only ONE pathological input value, and while that program may be acceptable, it's not correct. It's equally possible for a correct program to do nothing useful. My point is, it's correct as long as it behaves entirely predictably (decidably). (Correctness doesn't have to be a reasonable demand on a program. It's an immutable point of reference, like "truth" or "justice".) > [...] >Perhaps I'm taking you too literally here. You can, of course, defend >yourself from anything you anticipate, but deciding what to if an event >occurs may not be feasible. Taking your example of divide by zero, this >halts any machine that I am familiar with. Do you feel any concern that it >won't halt? Yes, the program halts. The choice of halting (by the great masters of CS) was a somewhat arbitrary one. It's just a measure of whether a program is correct. (As it happens, properly functioning turing machines are supposed to do several things when they execute, one of which is halt. Ergo the choice of "not halting" as a measure of incorrectness.) Division by zero isn't important except as an exmple of failure. Likewise the inability to halt is a good example of failure. You can be certain of anticipating both of these failures *only* if your program is not a Universal Turing Machine. If it is a UTM, you cannot be certain that it will behave as you planned, because you cannot constrain your input data sufficiently. That's the purpose behind teaching the halting proglem. Yes, you can constrain the input of many programs to make them correct. You can constrain many more programs to make them *sufficiently* correct. But some programs can never be considered correct in light of the way they respond to data (by treating them as programs themselves). While this last class of programs may be relatively small, it illustrates the existence of a potential threat to any program. Like exponential search and NP-hardness, it's good to know the limits to how certain of perfection (and safety) you really can be when writing software. > >[...] No one expects every potential bridge or building design to be >decidedly correct. Designs are purposely engineered to be easy to analyze >(model). Is this remarkable? I think the blurring of the difference between software and bridges is where the confusion lies. No bridge can be proven correct. But it's traditional that the mathematical foundations used in building bridges *are* considered correct, ie. perfect. If a civil engineer found that error was cropping up in his computations *without his/her knowing* then any bridge or building he builds is at greater risk than he intended. THAT's the point behind correctness and the halting problem in computer science-- knowing that you can't assume *too much* when you write code. -- Randy crawford@mrj.com