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!