How to construct Turing Machine for the language $L= \{0^t \mid t \text{ is a composite number }\}$

Question

I am unable to get the way out for approaching this question. Please provide me with some insight.

Answer 1

Hint: A natural number $t$ is composite if $t = pq$, for natural numbers $p > 1, q > 1$. Try every $p$-candidate. You will need to figure out how one implements division on a Turing machine. Fortunately, your numbers are in unary notation, that is, of the form $0^t$.

Answer 2

Assuming that the machine has as input a single block (call this block $A$) of $m$ $0$'s on an otherwise blank tape, here is what I would do:

First see if there is only one $0$ .. If so, reject

Otherwise:

Copy the string of 0's (copying a block is a fairly straightforward thing to do for a turing machine) with a blank in between the original and the copy (call the copy block $B$)

Create a third block $C$ of $n$ $0$'s; start with $n=2$

And now go through the following loop:

keep removing $n$ $0$'s from $B$ (which of course you can do by removing as many $0$'S from block $B$ as there are in $C$). If this results in block $B$ being empty on the first pass (i.e. if there were as many $0$'s in $B$ as in $C$), then reject (you can conclude that $m$ was a prime number, and thus not composite). If this results in $B$ becoming empty on a later pass (i.e. If $m$ is a multiple of $n$), then accept. If $B$ has more than zero, but less than $n$ left at some later pass, then make $B$ the same size as $A$ again, add a $0$ to $C$, and go through the loop again.

This loop will end since if $m$ is composite, then the machine will accept in the case where $n$ is the smallest prime divisor of $m$, and if $m$ is not composite, then it is prime, and the machine will reject in the case where $m=n$.