The halting problem: Difference between revisions
Jump to navigation
Jump to search
mNo edit summary |
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, as in, not continue running forever? | ||
For some code, absolutely. | For some code, absolutely. | ||
It would be trivial to make some examples that will halt. | It would be trivial to make some examples that will always halt. | ||
Yet, once you introduce programs for which the behaviour depends on the input, | |||
can you prove any given code will halt for all possible input? | |||
Also, you can figure this out for ''any'' possible code given to you? | |||
Spoilers: Nope. This problem is [https://en.wikipedia.org/wiki/Undecidable_problem undecidable], meaning it is ''proven'' to be impossible to give a correct yes-or-no answer. | |||