[Solved]: Turing machine with repeated strings

Problem Detail: 

How would I go about making a Turing machine to accept the following language L?

$$L = \{ www \mid w = \{0,1\}^* \text{ and } w > 0\}$$

I was thinking counting the number of symbols in the input string and then dividing by three to find the beginning of each instance of w and then testing if each instance is the same, but this seems a bit roundabout.

I feel like there is a way by marking the first three symbols and then moving the 2nd and 3rd markers until the strings in between them are the same but I'm having a hard time articulating this into an algorithm.

Can anyone point me in the right direction?

Asked By : MrDiggles

Answered By : Vor

From the comment: a quick way is to think that you are working on a two-tapes TM (initially the second tape is empty). You start placing $abc$ on it; then continue scanning it expanding the $a$, $b$ and $c$ substrings ($aabbcc,aaabbbccc,aaaabbbbcccc,...$) until the length of the second string matches the length of the input (or reject if you "overflow" it). During a scan simply replace the first $b$ with 1 $a$, the first 2 $c$s with 2 $b$s and append 3 $c$s at the end.

   Input: 011010110101101 2nd tape: <empty>   Scan 1: abc   Scan 2: aabbcc    Scan 3: aaabbbccc   Scan 4: aaaabbbbcccc   Scan 5: aaaaabbbbbccccc 

At this point it should be easy to check if the three subwords are equal ... finally think how to "merge" the second tape into a single one (just add extra symbols to the tape alphabet ...).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24184