Halting problem
Halting problem
Posted Dec 4, 2018 16:31 UTC (Tue) by dskoll (subscriber, #1630)In reply to: Halting problem by excors
Parent article: Bounded loops in BPF programs
Well, you know that N is so large that 2^N might as well be infinite for all practical purposes. Also, you assume that the computation is deterministic. In real-world situations where external events can change the state (a network packet arriving, for example), a program might terminate even if it repeats a state it has been in before.
Actually, it's trivial to prove that all programs on computers on earth will eventually halt, becuase the Sun will eventually expand and destroy the earth, thereby halting the program. That's the ultimate example of an external event affecting the state.
The LWN site is currently under high scraper load, so comment display has been suppressed for anonymous users. If you are a human, you may read the comments by clicking the button below:
Note: you can avoid this step in the future by logging into your LWN account.