The halting problem: Difference between revisions
Jump to navigation
Jump to search
(Created page with "<!-- ===The halting problem=== Given the code of a program, can you say that it will ever stop? For some code, absolutely. It would be trivial to make some examples that will halt. But you can easily prove that you cannot do so for ''all'' possible code? As to software we didn't make, well, a lot of software is written in a relatively straightforward recipe form, and finishes just because what it does doesn't vary, much or at all, with the data you give it. H...") |
mNo edit summary |
||
| Line 1: | Line 1: | ||
<!-- | <!-- | ||
Given the code of a program, can you say that it will ever stop? | Given the code of a program, can you say that it will ever stop? | ||
| Line 9: | Line 8: | ||
But you can easily prove that you cannot do so for ''all'' possible code? | But you can easily prove that you cannot do so for ''all'' possible code? | ||
(Note that this problem addresses correct, deterministic things. Yes, bad thread locking can cause race conditions that deadlock or livelock, but that's not the point of the exercise) | |||
| Line 98: | Line 100: | ||