Turing Machine remembering copied symbols

Question

So, I know that any multiple-tape TM can be in theory turned into a one-tape TM. However, it is too easy to copy, let's say, binary numbers from one tape to another. That's why I thought about putting a separator between the two copies and then taking symbols one after the other and writing them after the separator until the separator itself is encountered. The problem, however, is that I am not sure how it could remember places where it has already been/copied the characters. Example:

First we have:

##1011##

Then we put the separator '&' at the end

##1011&##

Read back to beginning and change the state accordingly so that it will write $1$ or $0$ after the separator. So far, so good, then we read back again, and now:

How could we know that we have already copied the first $1$ and must now copy the $0$ without putting any restriction on the input length (in regards to the number of states)? In other words, how could we remember the last copied symbol?

I have thought of putting an extra parameter - just a integer ≤ length (something like $\delta (z_1,1,L,1)$ where the last one would be the number of already written-out symbols). This would be easy to understand, but would be nowhere near the definition of Turing machine. So, any useful ideas?

Thanks.

Answer 1

Once you've hit the '&' separator, move left until you see the '#', then move one cell to the right and replace the '1' with an 'x' (and change to state $p$ to "remember" you've seen a 1) or a '0' with a 'y' (changing to state $q$ to "remember" you've seen a 0). Now move right until you pass the '&' separator and see a '#'. Replace that with a '1' if you were in state $q$ or with a '0' if you were in state $p$. Now move to the left until you see a 'x' or a 'y', move one cell to the right and repeat what you've done before. Continue the process until everything on the left is a string of 'x's and 'y's, then make one more pass, restoring the values to their originals.

Answer 2

Remember that Turing machines were designed as, essentially, a simulation of what a person could do with pencil and paper. That's what it meant to be a computer in those days: a person who computes!

So, how would you copy a long string of zeroes and ones using a pencil and paper? You'd probably do something like this:

• read the first character and remember what it is;
• put a pencil mark by that character to say that it's been copied;
• write a copy of the character in the place you're copying to;
• go back to the first unmarked character and repeat until you've marked every character;
• go back and erase all the marks.

And that's how you do it with a Turing machine, too.