Re: What good is halting prob?

[cpp@netcom.com (Robin Rowe)]

In article <dewar.798381929@gnat>, Robert Dewar <dewar@cs.nyu.edu> 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!