4 ms·
You can determine if a program halts by running two copies in lockstep, one at half the speed of the other. If their states are ever the same after the first st
by Animats 5y ago
You can determine if a program halts by running two copies in lockstep, one at half the speed of the other. If their states are ever the same after the first step, they're in an infinite loop.
That was actually used in an early batch system for running student jobs in an interpreter. A successful student job ran for under a second; one in a loop ran for 30 seconds until it was killed for taking too long. So detecting simple loops, even with substantial extra overhead, was worth it.
- PoignardAzur 5y agoYes, but the point is, if you have an amount of memory M, there exists an amount of memory N for which there is no program that fits into M that can successfully predict whether an arbitrary that fits into N will halt. No infinites required. (since your example is using two copies, you're essentially using 2M memory)