Develop a Turing machine that will make a copy of the input right next to the in

Question

Develop a Turing machine that will make a copy of the input right next to the input after leaving a blank space. Note that it does not matter what the alphabet contains, but to make things simple, we will assume that the input alphabet contains at least 0 and 1. The left end of the tape is marked by the tape symbol , at which the machine starts. Tape alphabet contains at least the input alphabet, , and the blank symbol (). You may add symbols to the tape alphabet if needed for any other reason.

Can someone explain this to me?

Explanation / Answer

A first solution is possible if you assume that the head can go over a cell and read it without writing on it.

If you assume that you can tell the two ends of your input, the answer to your question is just that you copy/translate the input to unary form on some other part of the tape, so that you do not run the risk of erasing a part of the input that has not been copy/translated yet. If you copy/translate the input from left to right, you start the copying on some part of the tape that is on the right of the original input.

For that purpose, you need markers, and you can for example use 010 to mark the place where you copy the translation of the next symbol. You can erase original symbols as you copy them, and possibly also mark the last erased symbol with 010 (wich you then do not use as translation of an original symbol). Part of the control is teh used to move bertween the two 010 marks during the translation phase.

But you cannot make the number of states dependent on the length of the input. The TM uses the same finite state control independently of input size, which implies not changing th number of states.

If you do not allow reading a cell without overwriting it, things are more complicated. I further assume that the head is initially on the left side of the input. In ordr to make a copy translation without destroying the input, one has to start from the left, and make the copy further on the left.

Since it is impossible to foresee how much space will be needed, the trick is to copy/translate the input into a mirror image, so that it grows on the left, and never risk erasing the original input.

Then you can either decide to compute with a mirror image, or you can just make a second pass on the copy/translated input, so as to reverse it again and have it in the right order.

Using 1 in the original input.

I think that it is possible to do the same when 1 is used in the original alphabet. But one must be very careful not to confuse its use in the original input, and in the copy part. This can be done with a specific configuration appearing only a fixed number of times in the created copy, the rightmost one dentifying precisely the beginning of the rest of the original input to be copied.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.