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:


Move a head to the right until the head encounters an unmarked symbol.
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.
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.
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.
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:


Start with $n=2$ - this is prime.
Set $j$ equal to $n$.
Add $1$ to $n$
Set $k$ equal to $n$.
Subtract $j$ from $k$.
If $k$ is greater than $0$ go to step $5$.
If $k$ equals $0$ then $n$ is not prime; go to step $2$.
Subtract $1$ from $j$.
If $j$ equals $1$ then $n$ is prime; go to step $2$.
Go to step $4$.