# Design a Turing Machine Checking if power is prime

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?

• 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. – djechlin May 14 '17 at 18:13
• 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. – Dark Archon May 14 '17 at 18:29
• @DarkArchon Then start with simpler TMs. How would you check if the input is divisible by two? Three? ... – Raphael May 14 '17 at 19:13