Turing machine to accept words that are same twice

[kockasinges]

I would like to construct a TM, that can accept words like these: tmtm or samesame. I plan to use up 3 tapes for this and copy all the symbols one by one from input to 2nd tape. Don't know, when and how should I examine back the copied characters. How should I know, where is half part?

[Commander]

I would like to construct a TM, that can accept words like these: tmtm or samesame. I plan to use up 3 tapes for this and copy all the symbols one by one from input to 2nd tape. Don't know, when and how should I examine back the copied characters. How should I know, where is half part?

 

You need to traverse the entire word [tape1] from left to right and keep copying into tape2

 

And then return to the center point [if the length of the word is even sized (is required to be so-if odd Reject)] while doing that write that into the tape3 and clear those letters from tape2.

 

After reaching the halfway mark compare tape2 with tape3 and if that equals Accept else Reject.

[kockasinges]

How should I know, where is halfway in the word. These aren't fixed length.

[Endy0816]

Divide word length by two?

[Commander]

How should I know, where is halfway in the word. These aren't fixed length.

 

 

The following was suggested :

 

 

You need to traverse the entire word [tape1] from left to right and keep copying into tape2

And then return to the center point [if the length of the word is even sized (is required to be so-if odd Reject)] while doing that write that into the tape3 and clear those letters from tape2.

After reaching the halfway mark compare tape2 with tape3 and if that equals Accept else

 

On the step 2 : And then return to the center point [if the length of the word is even sized (is required to be so-if odd Reject)] while doing that write that into the tape3 and clear those letters from tape2.

 

Add here : At each backward step move tape1 two letters back for each letter and at the mid point tape1 would reach its starting point.

 

In any case as you are allowing comparison of the two half strings which needs some external memory/computation you can use that feature to count the number of letters in the first step too.

Edited September 10, 2015 by Commander

[kockasinges]

So, please see this part of the exercise:
moveX are the direction of the moving of tapes.

(state, (sign1, sign2)) -> (state', (sign1', sign2'), (move1', move2', move3'))

(START, (*,U,U)) -> (g1, (*,*,U), (1,1,0))
(g1, (U,U,U)) -> (g2, (*,*,U), (-2,0,0))

(g2, (U,U,U)) -> (STOP, (U,U,1), (0,0,0))

 

So, I have iterating through the tape and after that go back to the start of the tape, then STOP. But first of all, how to count characters on tape3?

[Strange]

You might need to Google backtracking algorithms (for regular expression matching). But note that the size of your Turing machine (and therefore run time) may grow exponentially with the size of pattern it needs to recognize.

[kockasinges]

It seems, doesn't needs AI to solve this problem. I would like to get a bit more accurate answer.