Invisible <voi### [at] devnull> wrote:
> It's common knowledge that if you write an arbitrary program in a 
> Turing-complete programming language, it is impossible to determine 
> whether the program will ever halt.

  That's not stated correctly. It's impossible to create an algorithm which
would tell for all possible programs whether they terminate or not.

  It is, rather obviously, possible to create an algorithm which tells for
*some* programs whether they terminate or not.

  In other words, in the generic case the problem is unsolvable, but in
specific cases it can be solved.

> Can you determine whether a particular execution path is ever 
> taken? Or whether a given variable will ever be read/written?

  That's completely (and rather trivially) equivalent to the halting problem.

-- 
                                                          - Warp

Post a reply to this message