Re: What good is halting prob?

[crawford@cais2.cais.com (Randolph Crawford)]

In article <cppD7880n.32B@netcom.com>, Robin Rowe <cpp@netcom.com> wrote:
>In article <3mve9b$gaj@news.cais.com>,
>Randolph Crawford <crawford@cais2.cais.com> 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