Ullman (TOC) Edition 3 Exercise 9.2 Question 3 (Page No. 391)

Question

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

1. The set of all perfect squares $\left\{1,4,9,\cdot\cdot\cdot\right\}$. 
2. The set of all primes $\left\{2,3,5,7,11,\cdot\cdot\cdot\right\}.$
3. 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$. 

Answer 1

please provide me this question answer for my study thank you