5 ms·

Writing a program to determine if another program will complete, error, or run indefinitely is quite doable given reasonable constraints: Run the program! One

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.

X-Istence 13y ago
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.
- absherwin 13y ago
  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.
hobs 13y ago
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.
A1kmm 13y ago
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.

X-Istence 13y ago

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.

absherwin 13y ago
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.

hobs 13y ago

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.

A1kmm 13y ago

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.