# Turing Machine to return all prime numbers

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.

• When you say "all the prime numbers", is there a fixed upper limit, or should the TM run endlessly writing actually all primes? – siracusa Oct 20 '19 at 11:52
• 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. – Speedding Oct 20 '19 at 12:00
• 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 – HEKTO Oct 20 '19 at 15:10

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$$.