That doesn't sound right. All my decider needs to do is wait for a repeated state (no halt) or a halt. If the state space is finite then one of these is guaranteed to happen.
That doesn't sound right. All my decider needs to do is wait for a repeated state (no halt) or a halt. If the state space is finite then one of these is guaranteed to happen.
And how does your decider recognize that a state has been attained twice? If I make the input system large enough then you don't have enough space in your decider to save all the states which it has observed.
> If I make the input system large enough then you don't have enough space in your decider to save all the states
We have cycle detection algorithms that don't require saving all states and work in the same big-O space complexity (constant factor overhead) as just running the input system normally without cycle detection.
To my understanding that means that, for any input system that runs in finite-but-unbounded space, the detector will determine whether it halts in finite-but-unbounded space - unless I am misunderstanding that term.
Right. Cycle detection can be done by running two copies of the program in lockstep, but at a 2:1 step rate. If the state of both programs match, you're in an infinite loop.
Assume your cycle detection D(TM, i) always outputs 1 when TM(i) doesn't halt (TM is the encoding of a turing machine and i is the input to TM). Otherwise, if TM(i) halts, D does NOT halt. [1]
We can construct a new turing machine F(TM) = D(TM, TM). That is: We ask D to detect a cycle when a TM receives its own encoding as an input. What is the output of F(F)?
F(F) = D(F, F) = 1 can only happen if your cycle detector detected a cycle in F(F) which we just saw terminates with 1. If F(F) doesn't halt, then your cycle detector claims that F(F) terminated, which it doesn't.
Therefore no such cycle detection can exist. It either has to bound the size of the input system or be non-exhaustive in its detection. The intuition here is: Assume the encoding of D has size N and D can check all encodings up to size N, then D must be able to dectect its own cycles. But the input to D(F, F) is size 2N (cause F is roughly the same size as D).
[1] If your original cycle detection outputs 0 if no cycle is present, then just wrap it in a TM that calls the original cycle detection and either returns on 1 or infinite loops on 0.
I believe the problem there is that the constructed F(F) input itself would not run in finite space:
* F(F) internally runs its implementation of D's code on (F, F)
* ...which runs F(F) plus some constant-factor-overhead
* ...which runs its implementation of D's code on (F, F)
* ...which runs F(F) plus some constant-factor-overhead
* etc.
Ends up with the F emulating itself recursively, with the overhead adding up.
Note that the claim I make of D is that for any input system that runs in finite-but-unbounded space it will determine whether it halts in finite-but-unbounded space - not for input systems that already by themselves use infinite space.
What do you mean "space in your decider"? My decider takes finite but unbounded memory, same as the machine it's deciding.
Ok, if that's the class of systems we are talking about, then the system that your decider wants to check does not need to attain the same state twice. It may or may not terminate, and your decider may never know. You can't have it both ways. Keep in mind that the input can be as adversarial as it wants and knows, including having full knowledge of what your decider is trying to do.
What class of system are you talking about where the claim is false? Can you express your statement/definitions rigorously? A system that enters the same state twice will never halt, we know it will keep cycling through the same list of states over and over again.