1 Replies - 1410 Views - Last Post: 21 September 2012 - 09:23 AM

#1 mrproper  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 21-September 12

Very basic Turing machine question

Posted 21 September 2012 - 05:38 AM

We have Turing machine M with one work tape, which is it's output. The tape heads of input and work tape can move only left and right (basic definition, there is no staying at the current position movement). And we want to execute simple algorithm. We want to duplicate each symbol on the input tape twice and write it to the output tape. So if the input tape reads >ABCDE# in respective alphabet, we want to produce >AABBCCDDEE# on the output tape. How do we do that?

Obviously wrong way to do it: Simulate no movement of the work tape with a pair of forward - back movements.
What will happen? We will read the current symbol on the input tape and write it to the output tape. Then we have to move both tapes. We can move both tapes in the same direction, so the difference between their two positions will be 0. We can move the input tape back and the output tape forward, which will result difference between their positions of 2. There is no way we can move the tape heads so the difference between their positions is odd. So we can't reach situation where the read tape is at position n and the work tape is at position n+1 (For example position 1 for input tape and position 2 for output tape). How we do proceed then with the algorithm?

Is This A Good Question/Topic? 0
  • +

Replies To: Very basic Turing machine question

#2 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 771
  • Joined: 27-June 09

Re: Very basic Turing machine question

Posted 21 September 2012 - 09:23 AM

That's not wrong. Break it into two parts

Part 1 will produce A _ _ B C _ _ D E _ _ F G ... by reading from the input tape and moving as needed.

Part 2 will fill in the blanks by reading from the input tape, moving work tape to appropriate blank location, then writing that character in that new location. Then adjust both tapes so the input is at the next character it needs to read.

This post has been edited by mojo666: 21 September 2012 - 09:26 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1