I was reading the proof of speed-up lemma from this slide (page 10 to 13) but I could not understand why the plus two factor appears in the new space bound. Would anybody elaborate?
Furthermore for a Turing machine that uses a linear amount of space, isn’t it possible to reduce the amount of space used by a constant factor without additional constant overhead? (i.e. to have only the εf(n) part as the new space)
Theorem: Suppose TM M decides language L in space f(n). Then for any ε > 0, there exists TM M’ that decides L in space εf(n) + 2.