Question

Formally describe a 2-tape deterministic Turing Machine that accepts strings on the {0,1} alphabet. Such strings have the number of "0" double than "1".

Answer 1

RIGHT/LEFT : When N moves RIGHT by one cell, M does as well, unless it reaches an end of row marker “#”. In this case, we expand each row of M by one cell to the right, namely mark the current tape position, rewind to the start of the tape, and move RIGHT. When an end of row marker is encountered, move all tape contents one cell to the RIGHT. Now we can rewind again and go back to the old head position, and move one cell to the right. The LEFT move is similar. (b) UP/DOWN : In order to simulate an UP move of N, we need to move left beyond the end of row marker to the the row above. However, we also need to ensure we are at the same column. This can be done by marking all the tape contents from the current head position to the end of row marker. Then, counting off the columns by unmarking the contents of the old row and marking the cell of the new row.i.e., the head moves LEFT from the current position, marking each cell until it reaches the end of row marker #. Upon encountering the #, we know we have moved to the row above. Now, we move RIGHT, unmark the rightmost marked cell, traverse LEFT till we find the first unmarked cell after the # and mark this cell. This way, we count the columns so at the end when there are no more marked cells to thr right of #, we have reached the corresponding column of the row above. Now we can unmark all the cells till the current cell and we have in effect executed an UP move. The DOWN move is similar.