Informally describe multitape Turing machines that enumerate the following sets of integers, in the sense that started with blank tapes, it prints on one of its tapes $10^{i_{1}}10^{i_{2}}1\cdot\cdot\cdot$ to represent the set $\left\{i_{1},i_{2},\cdot\cdot\cdot\right\}$.
- The set of all perfect squares $\left\{1,4,9,\cdot\cdot\cdot\right\}$.
- The set of all primes $\left\{2,3,5,7,11,\cdot\cdot\cdot\right\}.$
- The set of all $i$ such that $M_{i}$ accepts $w_{i}$. Hint: It is not possible to generate all these $i's$ in numerical order. The reason is that this language, which is $\overline{L_{d}}$, is $RE$ but not recursive. In fact a definition of the $RE$- but-not-recursive languages is that they can be enumerated, but not in numerical order. The "trick" to enumerating them at all is that we have to simulate all $M_{i}'s$ on $w_{i}$, but we cannot allow any $M_{i}$ to run forever, since it would preclude trying any other $M_{j}$ for $j\neq i$ as soon as we encountered some $M_{i}$ that does not halt on $w_{i}$. Thus we need to operate in rounds, where in the $k^{th}$ round we try only a limited set of $M_{i}'s$ and we do so for only a limited number of steps. Thus each round can be completed in finite time. As long as for each $TM \ M_{i}$ and for each number of steps $s$ there is some round such that $M_{i}$ will be simulated for at least $s$ steps, then we shall eventually discover each $M_{i}$ that accepts $w_{i}$ and enumerate $i$.
