Question

Give a high-level description of a TM (how it moves its head around, etc.) that

takes a string of the form x#y where x, y ∈ {a, b}* are guaranteed to have |x| = |y| ≥ 1,

and swaps x and y (i.e., it should halt with y#x written on the tape). For example, if the

input is abb#bab then the output should be bab#abb. Do not give a state diagram. Use the

“marking” idea to keep track of where the TM left off in each half.

Answer 1

Here is how the TM works to accomplish the given task:

1. The TM machine reads the first letter from x. Call it "a". It writes a "blank" at this place. (Marking)
2. It then moves to the # symbol and reads what is written on the next cell ("b") and writes "blank" there.
3. It moves back to the first blank it wrote and writes "b" there and moves right to the next cell and reads what is written there ("a1") and writes a blank at this place.
4. Moving towards the right it finds a blank symbol and writes a there and moves to the next cell and reads what is written there ("b1") and writes a blank here.
5. It proceeds, in the same way, to exchange each letter of the strings x and y and finally halts.

You can comment below the answer in case of any doubts and I will be happy to help.

Please give a thumbs up if the answer could be of help!

All the best!