Can someone please describe how such a machine would work?

My approach:

Move the head full on the left. Scan the input to verify no # symbol exists. Add # at the end of input. Move the head full on the left. Move one position on the right.

Read character σ and replace it with σ'. Then go right to the 1st empty char and replace it with σ. Then go left till you found the 1st ' char. Remove the ' from that char. Move one position the the right and repeat.

When you do that for all characters stop.

  • $\begingroup$ Do you mean a machine that, starting with $w$ on its input tape, ends its computation with exactly $w\#w$ on its tape? $\endgroup$ – Purag Jun 7 '16 at 6:27
  • $\begingroup$ @Purag Yes, exactly that. I just stared with Turing Machines and have a hard time understanding how this can be done. $\endgroup$ – MATH000 Jun 7 '16 at 6:34
  • $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just do your exercise for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – D.W. Jun 7 '16 at 6:40
  • $\begingroup$ @D.W.♦ updated, can you please verify my approach is correct? $\endgroup$ – MATH000 Jun 7 '16 at 6:47
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. It's better to ask about a specific conceptual issue you're uncertain about. As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Jun 7 '16 at 7:04

Browse other questions tagged or ask your own question.