6 ms·
I mean if the program requires too much RAM then it will either crash & stop or glitch and run forever, but you can always tell which way it will break :)
by sp332 11y ago
I mean if the program requires too much RAM then it will either crash & stop or glitch and run forever, but you can always tell which way it will break :)
- paulddraper 11y agoAnd how do you tell (without running forever)?
- sp332 11y agoYou run the program for 2^(bits of state) steps. If it's still running, it will never stop because it must have repeated a state at least once. That means it's in a loop. So it takes a long time, but not an uncomputably long time. By bits of state, I only mean the bits that the program is allowed to change. It doesn't necessarily include OS code or initialization code, as long as they are immutable while the program is running.
- paulddraper 11y agoAh, yep, you're right. Finite state -> solved halting problem