|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |