2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This seems to be a programming question, if on TMs. Community votes, please: is this ontopic? $\endgroup$ – Raphael Jun 6 '16 at 18:21
  • 1
    $\begingroup$ Why would I want to copy sequences using TMs? $\endgroup$ – user8 Jun 6 '16 at 18:25
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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