title: Detecting if a Program is in an Infinite Loop (Read: Solving the Halting Problem)
body: <p>Is detecting whether a <em>deterministic</em> program (i.e. state machine) is in an infinite loop equivalent to solving the halting problem?</p>
  
  <p>I came up with a solution, and I'm not sure why it shouldn't work:</p>
  
  <ul>
  <li>Let the program run</li>
  <li>When you think it's in an infinite loop, take a snapshot of its memory regular intervals</li>
  <li>If you ever detect the same snapshot, the program is in an infinite loop</li>
  <li>As long as you don't get the same snapshot twice, it's either (1) not in an infinite loop, or (2) you need to take snapshots more quickly (perhaps once on every memory access?)</li>
  </ul>
  
  <p>I'm assuming this doesn't work... but why?</p>
  
  <p>It seems like a perfectly reasonable way to detect if a program is in an infinite loop (e.g. especially if you store hashes rather than the memory itself, although that will not be 100% accurate)... what's wrong with it, if anything?</p>