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