OK, so Darren will know the answer to this one...

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.

This poses several interesting questions. For example:

- What is the "most powerful" language for which you *can* tell is an 
arbitrary program will halt?

- If you have an arbitrary program written in a Turing-complete 
language, which properties *can* you determine, and which ones *can't* 
you determine?

You can't determine whether the program halts after a finite or infinite 
number of steps. But you can trivially determine whether it halts after 
less than 1,000 steps. You can't determine if it's type-safe [only 
whether it is well-typed according to some more restrictive set of 
rules]. Can you determine whether a particular execution path is ever 
taken? Or whether a given variable will ever be read/written? You can't 
determine whether two programs do the same thing, but can you determine 
whether one algorithm is the inverse of another? And so on...

Post a reply to this message