Dovetailing

[6/33%]

Show

LaTeX

Show LaTeX

Problem 5.2.1 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 5.2 "R. E. Sets and Recursive Sets"

(a)(b)(c)

Assume that $A, B, C \subseteq \left\{ 0,1\right\}^{*}$ are r.e. sets. Let

D=(A \cap B) \cup (B \cap C) \cup (C \cap A).

(a)

Construct a DTM that simulates the three DTM's accepting sets $A, B$ , and $C$ in parallel and accepts set $D$ .

(b)

Construct a DTM that simulates the three DTM's accepting sets $A, B$ , and $C$ by the dovetailing method and accepts $D$ .

(c)

Find a recursive predicate $R$ such that $D=\left\{ x \mid (\exists y) R(x, y)\right\}$ .

Problem 5.2.2 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 5.2 "R. E. Sets and Recursive Sets"

Design two dovetailing algorithms for set $B$ of Example 5.11, the first based on the intuitive algorithm given in the solution, and the second based on the last line of the proof by the projection theorem.

Problem 5.2.10 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 5.2 "R. E. Sets and Recursive Sets"

Show that the following function is partial recursive:

g(i, j, k)= \begin{cases} k & \text{ if }(\exists n)\left[\phi _{i}(n)=\phi _{j}(n)=k\right] \\ \uparrow & \text{ otherwise }.\end{cases}

Problem 6.3.2 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 6.3 "Hierarchy Theorems"

In the proof of Theorem 6.17, we used the dovetailing technique to perform the parallel simulation of $M_{w}$ and $M^{c}$ . Can we use, instead, the product Turing machine method of Example 5.9 to perform the parallel simulation?

Example 5.9 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 5.2 "R. E. Sets and Recursive Sets"

Assume that sets $A$ and $B$ are r.e. Show that sets $A \cup B$ and $A \cap B$ are also r.e.

Example 5.10 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 5.2 "R. E. Sets and Recursive Sets"

Show that the set $\left\{ y \mid W_{y} \neq \emptyset \right\}$ is r.e.

References

[DuKo01] Du D., Ko K. Problem Solving in Automata, Languages, and Complexity. John Wiley & Sons, 2001.