If you want to make money online : Register now

# How can an LBA check legality of TM transitions without extra memory?

, ,
Problem Detail:

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.

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.