>> 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.

Right. You can't solve the problem for all possible programs, only for 
some of them.

So what's the smallest limitation you could impose on the programs to 
make it possible to solve them all?

>> 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.

I had a sinking feeling it might be...

Post a reply to this message