I have to design a Turing Machine to do the following, but I don't really know where to start with this question. Any help would be very much appreciated.

I should design a Turing Machine accepting language $L = \{ a^p |$ p is not a prime number$\}$. I know I should use some quality of prime numbers, but number theory never was my strong side. How do I proceed with this?

  • $\begingroup$ Did you try using the definition of a prime number? Write out by hand a calculation to see if 1331 is prime. See if you can turn it into a computer program in Java, C, etc. Then see if you can turn that into a Turing machine encoded program. $\endgroup$ – djechlin May 14 '17 at 18:13
  • $\begingroup$ I am supposed to solve this problem on paper, by my hand. Sure I can check if 1331 by trying to divide it by progressively larger numbers, but this is cumbersome even on paper; I don't have slightest idea how to encode this in TM. $\endgroup$ – Dark Archon May 14 '17 at 18:29
  • $\begingroup$ @DarkArchon Then start with simpler TMs. How would you check if the input is divisible by two? Three? ... $\endgroup$ – Raphael May 14 '17 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.