# Padding in proof of space hierarchy theorems

Referring to the Wikipedia proof :

Wikipedia proves the space hierarchy theorem using the following language: $$L = \{ (\langle M \rangle, 10^k) : \text{M does not accept (\langle M \rangle, 10^k) using space f(|(\langle M \rangle, 10^k)|)} \}.$$

Why do we need the padding with $$10^k$$? How does it help us in the proof, and where does it fail if we do not consider it?

I assume that the same reasoning would be valid also for the nondeterministic version.

Suppose that we consider instead the language $$L = \{ \langle M \rangle : \text{M does not accept \langle M \rangle in space f(\langle M \rangle)} \}.$$ We want to show that $$L \notin \mathsf{SPACE}(o(f(n))$$, that is, that if $$M$$ uses space $$o(f(n))$$ then $$L(M) \neq L$$. This should be the case since $$\langle M \rangle \in L \Leftrightarrow \langle M \rangle \notin L(M).$$ But is this really true? According to the definition of $$L$$, $$\langle M \rangle \in L$$ iff $$M$$ does not accept $$\langle M \rangle$$ in space $$f(\langle M \rangle)$$. It could be that $$\langle M \rangle \in L$$ and $$M$$ accepts $$\langle M \rangle$$ using more than $$f(\langle M \rangle)$$ space. The latter could actually happen, since we are only guaranteed that $$M$$ uses space $$g(n)$$ for some function $$g(n) = o(f(n))$$, which does not preclude $$g(|\langle M \rangle|) > f(|\langle M \rangle|)$$ at the particular value $$|\langle M \rangle|$$.
Adding the padding fixes this issue: it cannot be that $$g(|(\langle M \rangle, 10^k)|) > f(|(\langle M \rangle, 10^k)|)$$ for all $$k$$, since this would contradict $$g(n) = o(f(n))$$.