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.


1 Answer 1


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$.

Final point. You state "non-deterministically try different divisions". Technically a deterministic machine would try various divisions. A non-deterministic machine tries only one. If there is a way to guess right, the string will be accepted.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.