Notices
Results 1 to 6 of 6
Like Tree1Likes
  • 1 Post By MagiMaster

Thread: Theory of Automata 2 - Q: Make/Draw a Turing Machine which reverses a string consisting of an alphabet {b,C,2}?

  1. #1 Theory of Automata 2 - Q: Make/Draw a Turing Machine which reverses a string consisting of an alphabet {b,C,2}? 
    New Member
    Join Date
    Jan 2014
    Posts
    3
    Hello,

    I don't know how to do this. Can anybody please help me to create this turing machine for me?

    Thanks in advance,
    momersaleem


    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    This sounds like a homework problem, so no one's going to do it for you. Instead, show what you've done and we can point out what errors you might be making.


    Reply With Quote  
     

  4. #3  
    Forum Junior TridentBlue's Avatar
    Join Date
    Jan 2013
    Posts
    207
    Quote Originally Posted by momersaleem View Post
    Hello,

    I don't know how to do this. Can anybody please help me to create this turing machine for me?

    Thanks in advance,
    momersaleem
    Some Socratic guidance: What is a Turing Machine? What does it do? What are the most basic functions its capable of?

    Also, remember every computer program is reducible to a Turing machine, and vice versa. Can you come up with a computer program that solves the problem? How might that look in terms of the very basic operations a Turing machine is capable of? (hint, think of memory as the tape)
    Reply With Quote  
     

  5. #4  
    New Member
    Join Date
    Jan 2014
    Posts
    3
    Hello,

    Yes it's an assignment. I have basic idea of turning machine and I have made multiple turing machines like "check if the number is even or odd" etc. But it's a different kind of problem for me and I am confused where to start and what to do with it. I just need a starting point if you can help me.

    TridentBlue, you hint "hint, think of memory as the tape" could be helpful but I am still confused.

    Thanks,
    momersaleem
    Reply With Quote  
     

  6. #5  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    Posts
    3,440
    Perhaps you should try and work the problem by hand first. Write out a sample string or two and then (with the limitations of Turing machines in mind) try and manipulate the symbols yourself until you get them reversed. I will tell you that it won't matter which end of the string you start with since flipping a string one way or the other gives the same answer.
    TridentBlue likes this.
    Reply With Quote  
     

  7. #6  
    Forum Junior TridentBlue's Avatar
    Join Date
    Jan 2013
    Posts
    207
    Quote Originally Posted by momersaleem View Post
    Hello,

    Yes it's an assignment. I have basic idea of turning machine and I have made multiple turing machines like "check if the number is even or odd" etc. But it's a different kind of problem for me and I am confused where to start and what to do with it. I just need a starting point if you can help me.

    TridentBlue, you hint "hint, think of memory as the tape" could be helpful but I am still confused.
    Thanks,
    momersaleem
    What I would do if you're still having problems with it is write down a string from the alphabet on a piece of graph paper, and then set up another area where you write down the reverse of that string, one step at a time. Create an algorithm for doing this. Now tell me what you think a Turing machine can NOT do that prevents it from doing whatever you did, and we'll see what's holding you back here...
    Turing machine - Wikipedia, the free encyclopedia
    The thing is there are a lot of ways of doing this. One question I might start with, is how could I move the tape head to the end of the string I'm reversing? It also might be helpful to remember that the input may be symbols are a SUBSET of the possible tape symbols.
    Reply With Quote  
     

Similar Threads

  1. need help in Theory of Automata?
    By Hussamgala in forum Computer Science
    Replies: 7
    Last Post: March 29th, 2013, 12:03 AM
  2. Help in Theory of Automata
    By adi.shoukat in forum Mathematics
    Replies: 0
    Last Post: December 9th, 2009, 05:30 AM
  3. Turing Machine Theory for Humanities student - Help
    By sr388frau in forum Computer Science
    Replies: 2
    Last Post: November 19th, 2008, 12:30 PM
  4. Turing machine Help please!!
    By bladeb2k in forum Computer Science
    Replies: 0
    Last Post: August 15th, 2007, 07:57 AM
Tags for this Thread

View Tag Cloud

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •