A Hierarchy Theorem for Polynomial-Space Recognition
Óscar H. Ibarra · SIAM Journal on Computing · 1974
The effect of increasing the size of the worktape alphabet of Turing machines with a read-only input and a single worktape operating within space $L(n) = n^r $ is investigated. In particular, it is shown that nondeterministic such machines with $m + 1$ worktape symbols are more powerful than those with m symbols.