Re: What's wrong with C++?

[Jeffrey Carter <spam.jrcarter.not@spam.not.acm.org>]

On 10/04/2011 07:13 PM, Yannick Duchêne (Hibou57) wrote:
> Le Wed, 05 Oct 2011 03:53:28 +0200, Peter C. Chapin <PChapin@vtc.vsc.edu> a écrit:
>> I don't think this is a big deal. It's an interesting theoretical
>> observation with little practical significance.
> Bad theoretical background is no good (at least, it matters to me, to me, it is
> a base of trustability).

Most people misunderstand the halting problem, thinking it proves that it is 
impossible to prove whether a program halts. In fact, it says it's impossible to 
write a program that, in finite time, can say whether any possible program halts 
for all inputs. It does not say it's impossible to write a program that can say 
whether a specific program halts for all inputs, or whether a subset of programs 
halt for all inputs.

In fact, there are programs now that can prove whether most sequential programs 
halt for all inputs. See the article "Proving Program Termination" by Cook, 
Podelski, and Rybalchenko in the 2011 May /Communications of the ACM/ for an 
overview of current work on this subject. These programs can, in finite time, 
return Terminates, Doesn't Terminate, or Unknown, on real code of reasonable 
size, with Unknown returned infrequently enough that the programs are useful in 
practice.

So I agree that the Turing completeness of C++ templates is unlikely to be a 
problem for real-world programs.

-- 
Jeff Carter
"I was hobbling along, minding my own business, all of a
sudden, up he comes, cures me! One minute I'm a leper with
a trade, next minute my livelihood's gone! Not so much as a
'by your leave!' You're cured, mate. Bloody do-gooder!"
Monty Python's Life of Brian
76