Sure, you just have to execute it and check if the internal state matches one of the previously recorded states, in which case it contains a cycle and doesn't halt.

The subtle problem is that it's impossible to define such a halting "oracle" as a program running within the same machine running the program you want to check whether it halts. It's possible to define a "deceiver" program that will use the oracle itself to change it's behavior.

    def deceiver(oracle):
      if oracle(Deceiver, oracle):
        while True:
          continue
      return

    print oracle(deceiver, oracle)

This doesn't mean that an external observer doesn't know whether running the oracle on the deceiver halts, but that it's impossible to write an oracle within that machine which will be a real oracle, since it will give a wrong answer for the deceiver program (and hence it wouldn't be an oracle).

Or, put in other words, even on a machine with finite memory, it's impossible to write a program (the oracle) in that machine that determines whether any possible program on that machine halts, because "any" program includes the oracle itself.

But what does "define a program that runs within that machine" mean?

Let's cheat a little bit. What if we build a machine that will record all it's internal states somewhere and when it detects that a program cannot possibly halt (because it reached a previously recorded state) asserts some IO line that can cause the cpu make it look like the oracle returns true?

    def oracle(program, input):
      # registerTrap will only work the first time it's executed
      # then it will be nop.
      registerTrap(on IO.cycleDetected, do nonLocalReturn(false))
      call program(input)

What did we achieve with this cheat? Now we can execute an oracle which will soon enter in a cycle executing oracle -> deceiver -> oracle -> .... and then the IO line will be asserted which will cause the oracle to abort the execution and return false (the program doesn't halt).

It can be argued that this oracle is non deterministic, because it won't give any answer when it's executed by the oracle itself (i.e. it won't terminate, only the outer oracle terminates). But nowhere we did specify that the oracle had to be reentrant!

Note that we didn't include the IO.cycleDetected input as part of the program input, because it's not an input. In fact, the IO.cycleDetected bit can be seen as part of the machine state. It's a state that is modifiable by the program by introducing a cycle in all other states (except this bit). But by reaching this subset of states (all of the states which include the IO.cycleDetected bit set), the machine halts AND the oracle correctly computes whether ANY program halts, including deceivers which invoke the oracle itself.

The main trick is to introduce hidden (inaccessible) states in the system: the write-once trap handler and the "detected cycle" state. This is not a "pure" machine, but it can nevertheless be built.

But what does this mean? We showed that it's possible to create a machine which can execute a program which can tell if any possible program of that machine terminates.

Can we build a machine where this is impossible? Yes. We just have to give to every program the possibility to get to all possible states, including the ones that would stomp on any attempt by any kind of oracle to determine whether there has been a cycle.

Imagine a degenerate case of a machine allowing any program to just "reboot" the execution of the oracle. The oracle itself couldn't possibly know that it has been unwound and thus cannot ever return saying so.

But we can always discern this situation if we look from outside. But what if the top level oracle performs a simulation of the machine? Even if the deceiver reboots, the oracle could still detect cycles by checking the simulated state. However, the inner oracle cannot do the same thing, because it would require infinitely nested simulators and we have only finite memory.

So there will always be one layer which doesn't allow to execute a working oracle from within.