# Informal description of Non-deterministic TM for the language $L = \{w^n \mid w \in \{a, b\}^* \text{ and } n \geq 2\}$

From a list of practice problems for a graduate Theory of Computation course. I've done quite a few problems at this point on deterministic Turing Machines, I just don't think I have fully grasped the notion of non-determinism in the context of TM's yet.

I suppose this TM would work something like this: Given an input $$x$$, non-deterministically try different divisions of $$x$$. For instance, if $$x$$ was of length 10, $$x$$ could be divided as $$w_1w_2$$ or $$w_1w_2w_3w_4w_5$$. Then, for each "guess" check if each of the substrings is the same.

I understand this is in and of itself an "informal description," but I would like to include some more "implementation-level" details. Some things that are confusing me... How can we be sure that the possible subdivisions of $$x$$ where the number of subdivisions does not divide the length of $$x$$ will not accept? For instance, in my example, how can we enure that the "guess" of $$w_1w_2w_3$$ will not accept? Furthermore, how can we go about the actual process of ensuring each $$w_i$$ are equal? I am familiar with the construction of the TM for $$L = \{ww \mid w \in \{a, b\}^*\}$$ where you first mark the midpoint with a $$\#$$, but I am not sure how you would mark the subdivision points when there can be an arbitrary number of substrings.

Anyway, hints are appreciated.

When "marking a letter" on the Turing tape, we replace a symbol $$a$$ by another symbol, like $$X$$, $$\bar a$$, or $$\underline a$$. Since various markings might be needed it is practically more convenient to consider a tape with various parallel components. We may write on each of these components to record phases of the computation.
The first $$w$$ can be guessed by marking its last position on the tape. Then is is straightforward to check whether the next segment also equals $$w$$. Just match the letters of $$w$$ one by one with the letters of the next segment. The machine marks the letters that have been checked. When everything is OK, unmark initial $$w$$ and repeat for the next segment. Etcetera, until the final segment is empty.
We accept if the segments match. In case the length of the string is not a multiple of $$|w|$$ the machine will be unable to match the final segment with initial $$w$$.