MHB TM: Is the given string of the form uu?

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Form String
AI Thread Summary
The discussion centers on constructing a composite Turing machine (TM) to determine if a string w over the alphabet A = {a, b} can be expressed as uu, where u is a non-empty substring. The proposed method involves finding the midpoint of the string by using a single head to mark symbols from both ends, ensuring that if an unmarked symbol remains, the string cannot be in the form uu. After confirming the string's length is even, the TM checks if the two substrings around the midpoint are identical by marking and comparing symbols. Concerns are raised about how to manage symbols during the comparison process without losing track of where to write the final output of "1" or "0." The conversation emphasizes the need for careful implementation and debugging in the TM design.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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? (Wondering)
 
Technology news on Phys.org
mathmari said:
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.
 
Evgeny.Makarov said:
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? (Wondering)
 
Last edited by a moderator:
Yes, something like that. Of course, if you write an actual Turing machine, it would require a bit more care and perhaps debugging.
 
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?
 
Dear Peeps I have posted a few questions about programing on this sectio of the PF forum. I want to ask you veterans how you folks learn program in assembly and about computer architecture for the x86 family. In addition to finish learning C, I am also reading the book From bits to Gates to C and Beyond. In the book, it uses the mini LC3 assembly language. I also have books on assembly programming and computer architecture. The few famous ones i have are Computer Organization and...
I have a quick questions. I am going through a book on C programming on my own. Afterwards, I plan to go through something call data structures and algorithms on my own also in C. I also need to learn C++, Matlab and for personal interest Haskell. For the two topic of data structures and algorithms, I understand there are standard ones across all programming languages. After learning it through C, what would be the biggest issue when trying to implement the same data...
Back
Top