My task is to design Turing Machine that ignores its input and returns all the prime numbers. I have some basic idea how to do that but I am not completely sure whether my approach is correct or not.

So no matter what the input is, we should ignore it. I think it would be sufficient to add another tape with cells $1^*,2,\dots,n$. Now, I would use Sieve of Eratosthenes algorithm as follows:

  1. Move a head to the right until the head encounters an unmarked symbol.
  2. Mark the symbol with a star and write it down to another write-only tape representing the output, i.e. the symbol is a prime number.
  3. Now, for $n$ being prime, I am supposed to mark every $n$-th symbol with a star. I am not sure how to do it.
  4. Reset.

For the third step, I think I should utilize another marking mechanism to denote a gap between the beginning and the prime resolved in that round. Then, I would be moving that "window" and whenever the beginning of the "window" would reach the prime, I would mark the symbol at the end of the "window" with a star. Not sure how to express this formally.

  • $\begingroup$ When you say "all the prime numbers", is there a fixed upper limit, or should the TM run endlessly writing actually all primes? $\endgroup$
    – siracusa
    Commented Oct 20, 2019 at 11:52
  • $\begingroup$ There should be no limit, and I am aware of that my Sieve of Eratosthenes approach might not work then. That's why I have asked for help, my interpretation of Turing Machine is incorrect maybe. $\endgroup$
    – Speedding
    Commented Oct 20, 2019 at 12:00
  • 2
    $\begingroup$ It seems to me that this exercise is not about effective primes generation, it's about how to describe a TM. So you could implement a trivial algorithm - take the next odd number, divide it by all already generated primes etc $\endgroup$
    – HEKTO
    Commented Oct 20, 2019 at 15:10

1 Answer 1


Designing a Turing machine is very laborious, even for simple tasks. So I suggest you keep the algorithm as simple as possible, even if it is very inefficient.

The very simplest prime generating algorithm (even simpler than the sieve of Eratosthenes) is as follow:

  1. Start with $n=2$ - this is prime.
  2. Set $j$ equal to $n$.
  3. Add $1$ to $n$
  4. Set $k$ equal to $n$.
  5. Subtract $j$ from $k$.
  6. If $k$ is greater than $0$ go to step $5$.
  7. If $k$ equals $0$ then $n$ is not prime; go to step $2$.
  8. Subtract $1$ from $j$.
  9. If $j$ equals $1$ then $n$ is prime; go to step $2$.
  10. Go to step $4$.
  • $\begingroup$ Is there a name for this algorithm? I would love to see motivation and proof. $\endgroup$ Commented Apr 25 at 3:22
  • 1
    $\begingroup$ @HunterKohler This is a version of the trial division algorithm - see en.wikipedia.org/wiki/Trial_division. The loop in steps 5 and 6 calculates $n \mod j$ by repeatedly subtracting $j$ from $n$. $\endgroup$
    – gandalf61
    Commented Apr 25 at 6:25

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.