I'm learning about the Savitch's theorem, and while the construction proof is straightforward, I still don't understand one part about it.
The proof I'm talking about is the same as is currently on Wikipedia. It starts by describing a function - let's call it
CAN_YIELD(start, end, limit) for now.
It is then said that the non-deterministic Turing Machine can be simulated by a deterministic Turing Machine by calling
CAN_YIELD(start_state, end_state, f(n)).
The proof then continues by describing that the function takes
O(f(n)) space for one configuration and
O(f(n)) for the recursion of the function. This nicely results in
O(f(n)^2) which is the result we want.
The issue is that if the
f(n) is not space-constructible, we don't know what limit number we should input into the
CAN_YIELD function. I've seen some proofs saying that we can add something like a 'size' parameter and check if it is large enough - but again, we don't know the actual
f(n) value, so I don't understand how this works.
One example of such proof can be found here. Another instance is this answer that states that we can replace the space-constructability requirement of the function by using a fixed space bound, which we increase after every iteration. Same issue as before, I don't see how that might work without knowing when to stop.
I'd be happy for any insight into this issue, or any corrections made to my statements!