2 ms·
And how do you tell (without running forever)?
by paulddraper 11y ago
And 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