4 ms·
Easy solution: He should just run a static analyzer on the code first to see if it will terminate before he executes it.
by dlsspy 16y ago
Easy solution: He should just run a static analyzer on the code first to see if it will terminate before he executes it.
- devinj 16y agoThis sounds like a bad idea, but it's actually very reasonable. Students, especially in early courses, are generally taught a subset of the language that wouldn't be that difficult to check for halting. As a bonus, you could also have that program analyze asymptotic bounds to help with grading. Still, this isn't the easy solution. The easy solution is to use a process and terminate it if it takes too long. Threads can't be reliably terminated, and especially not without accidentally ruining internal state. (what happens with locks? etc.)
- tansey 16y agoThis is provably impossible in the general case [1] and almost impossible in his specific case. It's extremely difficult to know if/when a program will terminate using just static analysis. Edit: Why the down vote? [1] http://en.wikipedia.org/wiki/Halting_problem http://en.wikipedia.org/wiki/Halting_problem
- willvarfar 16y ago+1 Indeed. Its the classic problem.
- Adrock 16y agoThe down votes are because it was a joke, punctuated by the "easy solution" preface. The author is almost certainly aware of the halting problem.