From: Marko Schulz <in6x059@...>
Date: 2002-05-15T05:49:09+09:00
Subject: Halting Problem (was "Re: code coverage tool?")

On Wed, May 15, 2002 at 03:49:53AM +0900, Patrick May wrote:
> 
> What is The Halting Problem?

The Halting Problem says, that it is impossible to write a software
that can answer you for _every_ program within finite time, whether it
will ever come to an end.

The Halting Problem has been proved for the idealistic Turing-Machine,
which most people today consider an good enough sign, that it is valid
for a usual computer too.

This knowledge can be used to deduce that a lot of other programs
cannot be written either: No program can check whether a software will
print out "foobar". If you could, you could take a software, make it
print "foobar" only just before it exits and - voila! -, your program
does solves a job equivalent to the Halting Problem.

Note that you can write programs that do these decisions for a subset
of all software. They just will never be able to answer the question
for every possible piece of software. And usually the subset is quite
small, simple and boring.

-- 
marko schulz