> 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.