Turing Machine to accept strings of prime lengths

Question

I have a homework problem that asks me to describe a program for a non deterministic Turing Machine that accepts L = {a^n: n is prime}. I'm not sure on how to go about this. do i know n? do i use the as as unary digits and count them? can i just ignore the string, and just test for the primarily of n? or are the prime values known, and thus only those cell locations are accepting states, and i can just read in the data like normal?

how should i go about this?

Answer 1

First you could use a memory location somewhere to flag whether the string has been found to be of prime length or not, and then do more or less what Ness suggested (although I don't really understand his answer in its entirety).

Use the Sieve of Eratosthenes. Start with a helper string of length 2, and move one right in the input string and the helper string, returning to the start of the helper string when you hit the end character of the helper string, until you hit the end character of the input string. In this way, you can see if the helper string divides the input string. Then move on to a helper string of length 3 and do the same, and so on. Only if none of the helper string lengths divide the input string length is the input string length prime. If one helper string length DOES divide the input string length, use your flag memory slot to show that. And have the algorithm check the flag memory slot, and if it's flagged, abort all processing so that the string can be rejected.

Now, at any point while iterating over the input allow a non-deterministic jump out of the inner loop so the machine can begin testing the helper string of the next length. In this way, in a sense, helper strings of all length will be being tested simultaneously, but when your flag slot is flagged, they all cease processing and reject the string.

One final problem. Strings might get accepted before (although time is sort of a non-concept here) they are found to be non-prime. If you can figure out that problem, you're one step ahead of me.

P.S. Drineas is evil