# Build a deterministic turing machine to decide L = { ww }

As the title says. w is in {a, b}^*.Note that I am not looking for the non-deterministic one. Use a Turing machine of one tape and "pointer".

An idea:

I thought that I would do something like R_until_end, then go back in the middle, add a special symbol like '#' and then I know how to tackle the problem. However, how would I fint the middle of it?

UPDATE:

• The algorithm will go like this: Make the first char an upper one. Go to the last char and convert it to an upper one. Do this until no lower chars exist. Now the "pointer" is set on the first letter of the 2nd string of the middle. Make all the chars of the 2nd string (i.e. after the middle of the input, which we found as described above). Then parse the input and when you have a match, place a blank. You are done when tape has only blanks. Now, I do not know how to express this in Turing machine language, with δ() and all this, but I will have to search..

DONE:

• Yep, it worked. I did some modifications to my approach, but this should be enough for someone to get started. If someone wants more info, let me know. :)

SOLUTION-2nd:

• I think you are making this needlessly complicated. Replace 1st symbol with _ Traverse to the end of the input with a state that remembers what the 1st symbol was. If matches, replace with _, go back and continue doeing the same for the smaller string. Otherwise go to an invalid state and end. Stop when all input is consumed. source
• What is your question? Yes, such a machine exists. Commented Mar 17, 2014 at 1:01
• Oops, mistyped in the title. See edit please. :) Commented Mar 17, 2014 at 1:05
• Are you interested in finding a determistic algorithm to solve the problem? Or do you really need to know a Turing machine specification, with states and transition functions and the like?
– GMB
Commented Mar 17, 2014 at 1:19
• The second, in order to understand the problem better. Commented Mar 17, 2014 at 1:22

Edited to redact palindromic assumption. Sorry for the confusion!

After thinking about it more, I would approach it first by counting the length of the string. If it is odd, reject. Otherwise, partition the string in half. So you want to test if i and (n/2 + i) are the same, where $n$ is the length of the string. The state transitions would be similar as if you were dealing with a palindrome. So that's a good place to start.

• Sorry the problem states that we should use one tape and one "pointer". Commented Mar 17, 2014 at 14:02
• Any Turing Machine that on k-tapes can be simulated using a single tape. I'll edit to add more detail on a one-tape alternative. Commented Mar 17, 2014 at 14:15
• Why do you assume that reading $w$ from the right is the same as reading it from the left? i.e. why do you assume that $w$ is a palindrome?
– DKal
Commented Mar 17, 2014 at 14:18
• I don't. If it isn't a palindrome, the characters won't be the same at the i and (n-i) positions, for some i, and we reject. Commented Mar 17, 2014 at 14:19
• That is my point exactly! your solution would reject $abab$ for example, but $abab\in L$. That is, you DO need to accept words $ww$ where $w$ is NOT a palindrome, but your machine will not accept them.
– DKal
Commented Mar 17, 2014 at 14:20

$$ww$$ with
$$ww^r$$ (with w^r = reserve of w)