In Sipser's book there is a proof that an emptiness of LBA is undecidable, with the help of reduction to A_$_{\text{TM}}$.

The reduction is proposed in the following manner: we receive a TM $M$ and a word $w$, and build an LBA $B$ that accepts if is fed an accepting computation history of $M$ on $w$.

At page 224, it describes how $B$ checks that the configuration $C_{i+1}$ is legal for M on $w$ at the step $i+1$, and states "then $B$ verifies that the updating was done properly by zig-zagging between corresponding positions of $C_i$ and $C_{i+1}$. To keep track of the current positions while zig-zagging, $B$ marks the current position with dots on the tape."

How can we know that $B$ does not need additional memory to check for legality of configuration change from $i$ to $i+1$? $B$ is an LBA, that says it has only the memory it got with initialisation and cannot go beyond it on the tape, so if it needs additional memory it has a problem.

  • 1
    $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. Note furthermore that not everybody has a copy of Sipser handy, so you should always define or explain non-standard jargon like "Atm" and "zig-zagging". $\endgroup$
    – Raphael
    May 7, 2014 at 11:22

1 Answer 1


B is given the complete computation history as input. All it does on that input, according to the description, is moving around, reading, marking, and unmarking things. Moving around and reading obviously don't need extra space, and marking/unmarking can be done in-place as well. (For each letter of M's alphabet B's alphabet can contain a marked copy, so that marking just means replacing the unmarked symbol with the marked one.) Thus, all is well.

  • $\begingroup$ Yes, this is a description. But doesn't he need to prove that concluding that Ci+1 is legal can be done merely by "moving around, reading, marking, and unmarking things."? Maybe it can be done only by "moving around, reading and marking things", or by "moving around, reading, marking things and saving additional state information" (in this case you need more memory)? How can machine description be formulated in such a way that B doesn't need to store additional information? $\endgroup$
    – alex440
    May 7, 2014 at 8:47
  • 1
    $\begingroup$ His description is not very detailed, but it is not that hard to see that no extra storage is needed: First note that only the content of the current cell and position of the head may change, so most of the work is just comparing that everything else is unchanged. For the parts that may change, we need to read the old character, the new character and the type of movement in order to determine validity. Since there are only finitely many options for this information, we can store it in the state of B. $\endgroup$
    – FrankW
    May 7, 2014 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.