Writing a program to determine if another program will complete, error, or run indefinitely is quite doable given reasonable constraints: Run the program!
One need only specify some reasonable length either equivalent to infinity for such a program, use a heuristic of checking whether the program is in the same loop and if so, whether any of the variables involved in determining loop termination are changing. Of course, proper security precautions are required.
For a certain subset of problems, it is possible to do this.
For any finite number of clock cycles N, in a Turing-complete language, I can write you a program which terminates but takes longer than N cycles. There is therefore no value of N which will consistently give the correct results in your program.
Turing machines have an infinite tape, so under a Turing machine model, there are infinitely many loop termination conditions, and so it is possible to craft a program which never repeats the same state within N cycles for any N but still terminates.
If your machine is finite state (with no inputs) and s possible states, rather than a Turing machine, you can check if the program halts:
halts s program initialState = do
seenState <- newBooleanArrayOfSize s
setBooleanEntry seenState initialState
halts' initialState
where
halts' state0 =
if state0 == HaltingState
then return True
else
do
seenAlready <- getBooleanEntry seenState state0
if seenAlready
then return False
else
state1 <- nextState program state0
setBooleanEntry seenState state1
halts' state1
In practice, s might be very large (even a 64 bit integer in the state will contribute 2^64 to s) so this algorithm isn't necessarily usable in practice, but it does complete in finite time.
It also says it must take "the source code", so that means you would have to be able to build any arbitrary program from source?
That would be a huge pain in the ass in general, above and beyond actually doing the things you mention.
You forgot about the butterfly. Even if it looks like nothing could change, something could due to a bit flipping in memory, which would allow the program to halt.
Right. Any statement that the program is in an infinite loop will usually be subject to error.
Of course, the real question anyone asked to develop such a program would be what runtime is equivalent to an infinite loop. Any real-world program must have a runtime bound that is predictable on invocation or it's useless.
One need only specify some reasonable length either equivalent to infinity for such a program, use a heuristic of checking whether the program is in the same loop and if so, whether any of the variables involved in determining loop termination are changing. Of course, proper security precautions are required.