Block, SkipCaptcha, apieditor, Automoderated users, Bots, edit, ratelimit-exempt
58,183
edits
Changes
mLine 6:
Line 6: − +
→top: clean up
halts for all valid input less than or equal to 0, and continues forever for all such input greater than 0.
halts for all valid input less than or equal to 0, and continues forever for all such input greater than 0.
In 1936, [[Alan Turing]] proved that there is no general algorithm that can decide this for every possible program and every possible input. (In other words, it is impossible to write a program that is capable of deciding whether a given program and given input will halt in all cases -- there will be some for which it is impossible for it to make such a determination.) As such, the halting problem is [[undecidable]] over Turing machines.
In 1936, [[Alan Turing]] proved that there is no general algorithm that can decide this for every possible program and every possible input. (In other words, it is impossible to write a program that is capable of deciding whether a given program and given input will halt in all cases—there will be some for which it is impossible for it to make such a determination.) As such, the halting problem is [[undecidable]] over Turing machines.
[[Category:Computer Science]]
[[Category:Computer Science]]