The Gateway to Computer Science Excellence

0 votes

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,508 answers

195,530 comments

100,965 users