Facebook Page
Twitter
RSS
+ Reply to Thread
Results 1 to 5 of 5
  1. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,546
    Thanks
    2,835 times
    Thanked
    917 times
    Awards
    MHB Model User Award (2017)  

MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)
    #1
    Hey!!

    I am looking at the following exercise:
    Construct a composite Turing machine $M$ that has a word $w$ over the alphabet $A = \{a, b\}$ tests to see if it's made up of two equal parts, that is, if $w = uu$ with $u \in {a, b}^+$.

    In this case, at the end of the method a $1$ has to be after the input $w$ otherwise a $0$.

    Furthermore, $M$ should stop on the space after the $1$ or $0$. At the beginning of
    the calculation the write/read head is on the first symbol of $w$.




    The idea of that TM is the following:
    • Finding the mid point of the string

      For that a head must be at the beginning of the string and a head at the end and each time we move the head one step to the right and one to the left rspectively.
      $$$$
    • After we have found the mid point we match the symbols of the two substrings

      For that we compare the two substrings.



    Is that correct?

  2. # ADS
    Circuit advertisement
    Join Date
    Always
    Posts
    Many
     

  3. MHB Master
    MHB Site Helper
    MHB Math Scholar

    Status
    Offline
    Join Date
    Jan 2012
    Posts
    2,467
    Thanks
    531 times
    Thanked
    4,393 times
    Thank/Post
    1.781
    Awards
    MHB University Math Award (2018)  

MHB Humor Award (2017)  

MHB Discrete Mathematics Award (2017)  

MHB Chat Room Award (2016)  

MHB Humor Award (2016)
    #2
    Quote Originally Posted by mathmari View Post
    For that a head must be at the beginning of the string and a head at the end and each time we move the head one step to the right and one to the left rspectively.
    Are you using a machine with two heads? A standard TM has only one head.

    You could mark symbols one by one from the beginning and the end of the string to discover the middle. By marking a symbol I mean replacing it by another from which the original one can be recovered. So you mark the first symbol, move to the end, mark the last symbol, move left until you find a marked symbol, move right and mark a new symbol (second from the left), move right until you find a marked symbol, move left and mark a new symbol (second from the right), etc.

  4. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,546
    Thanks
    2,835 times
    Thanked
    917 times
    Awards
    MHB Model User Award (2017)  

MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)
    #3 Thread Author
    Quote Originally Posted by Evgeny.Makarov View Post
    Are you using a machine with two heads? A standard TM has only one head.

    You could mark symbols one by one from the beginning and the end of the string to discover the middle. By marking a symbol I mean replacing it by another from which the original one can be recovered. So you mark the first symbol, move to the end, mark the last symbol, move left until you find a marked symbol, move right and mark a new symbol (second from the left), move right until you find a marked symbol, move left and mark a new symbol (second from the right), etc.
    Ahh ok! So if at the end just one symbol is left that is not marked, we know that the lenth of the string is odd and so it cannot be in the form $uu$ and so it the TM doesn't halt.
    If it halts, then we have to go to step 2 and we have to check if the substring before and after the midpoint is the same, correct? For that we delete the mark at the first part before the midpoint. Then we consider the first symbol and we go to the right till we find the first marked symbol and if they are the same we mark that one also or we replace it by a blank symbol. Then we repeat this procedure till we have reached the midpoint.
    Is that correct?
    Last edited by mathmari; October 9th, 2019 at 16:09.

  5. MHB Master
    MHB Site Helper
    MHB Math Scholar

    Status
    Offline
    Join Date
    Jan 2012
    Posts
    2,467
    Thanks
    531 times
    Thanked
    4,393 times
    Thank/Post
    1.781
    Awards
    MHB University Math Award (2018)  

MHB Humor Award (2017)  

MHB Discrete Mathematics Award (2017)  

MHB Chat Room Award (2016)  

MHB Humor Award (2016)
    #4
    Yes, something like that. Of course, if you write an actual Turing machine, it would require a bit more care and perhaps debugging.

  6. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,546
    Thanks
    2,835 times
    Thanked
    917 times
    Awards
    MHB Model User Award (2017)  

MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)
    #5 Thread Author
    At the end we have to write "1" after the input if it is of the form uu, otherwise 0.

    If we delete the symbols while we are checking if before after the midpoint we have the same substring, how do we know where we have to write "1" or "0" ?
    Or instead of deleting them do we have to mark them otherwise?

Similar Threads

  1. Help converting two standard form equations to slope intercept form?
    By matheus in forum Pre-Algebra and Algebra
    Replies: 8
    Last Post: May 5th, 2015, 04:55
  2. string access ops c++ 2
    By ineedhelpnow in forum Computer Science
    Replies: 5
    Last Post: September 25th, 2014, 15:12
  3. string access ops c++
    By ineedhelpnow in forum Computer Science
    Replies: 1
    Last Post: September 25th, 2014, 13:15
  4. Cost of the conversion of a string to an other string
    By evinda in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 20
    Last Post: August 22nd, 2014, 14:52
  5. [SOLVED] Normal Form and Canonical Form of a Quadratic
    By Sudharaka in forum Linear and Abstract Algebra
    Replies: 20
    Last Post: November 12th, 2013, 22:19

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Math Help Boards