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

39 views

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

## Related questions

1
66 views
In the box "Why 'Recursive'?" in Section $9.2.1$ we suggested that there was a notion of "recursive function" that competed with the Turing machine as a model for what can be computed. In this exercise, we shall explore an example of the recursive-function notation. A recursive function is a ... $A(2,1).$ What function of $x$ is $A(x,2)$? Evaluate $A(4,3)$.
Tell whether each of the following are recursive, RE-but-not-recursive, or non-RE. The set of all $TM$ codes for $TM's$ that halt on every input. The set of all $TM$ codes for $TM’s$ that halt on no input. The set of all $TM$ codes for $TM's$ that halt on at least one input. The set of all $TM$ codes for $TM's$ that fail to halt on at least one input.
Show that the following problems are not recursively enumerable: The set of pairs $(M,w)$ such that $TM \ M$, started with input $w$, does not halt. The set of pairs $(M_{1},M_{2})$ such that $L(M_{1}\cap L_(M_{2})=\phi$. The set of triples $(M_{1},M_{2},M_{3})$ such that $L(M_{1}) = L(M_{2})L(M_{3})$ ; i.e., the language of the first is the concatenation of the languages of the two $TM's$.
Let $L$ be the language consisting of pairs of $TM$ codes plus an integer, $(M_{1},M_{2},k)$, such that $L(M_{1})\cap L(M_{2})$ contains at least $k$ strings. Show that $L$ is $RE$, but recursive.