TM: Is the given string of the form uu?

[mathmari]

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? (Wondering)

 

[Evgeny.Makarov]

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.

 

[mathmari]

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)

 

[Evgeny.Makarov]

Yes, something like that. Of course, if you write an actual Turing machine, it would require a bit more care and perhaps debugging.

 

[mathmari]

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?