Fooling Turing machines with sublogarithmic space: a note on 'For completeness, sublogarithmic space is no space' by M. Agrawal

摘要

M. Agrawal in his paper [1] uses the following lemma in order to prove his, main, Theorem 3. Lemma 1. Let M be a sublogarithmic space DTM (deterministic Turing machine). Then, there is a constant N such that for every n ≥ N, for all strings z_1, z_2, ω, and for every e≥0, the space used by M on the input z1ω~(n+en!)z_2 is the same as the space used on the input z1ω~nz2. He claims that this technical lemma was proved in [4], where Liskiewicz and Reischuk proved that the alternating hierarchy for sublogarithmic space is infinite (similar results were obtained in [2] and [3]). But in [4] there were additional assumptions not mentioned explicitly in the lemma. In this paper we show that the lemma in the form presented in [1] is not valid. This does not mean that Theorem 3 of [1] is wrong. In fact, it is valid and can be proved using essentially the same proof; only instead of Lemma 1 one should use directly the n→n + n! technique (described in [4] or [3]) or the following improved version of Lemma 1.