Math Problems Vault

Example 5.9

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

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

?

Example 5.11

Show that if $A$ is r.e. then $B=\bigcup_{y \in A} W_{y}$ is also r.e.

?

Example 5.12

Show that the range of a partial recursive function $f$ : $\left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ is an r.e. set.

?

Example 5.16

Show that if $A$ and $B$ are recursive sets, then $A \cup B, A \cap B$ and $\bar{A}$ are all recursive.

?

Problem 5.2.1

(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

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

(a)(b)

Assume that $A, B, C \subseteq \left\{ 0,1\right\}^{*}$ and $A \cap B=B \cap C=C \cap A=\emptyset$ . Also assume that there exist three partial recursive functions $f_{1}, f_{2}, f_{3}$ that have the following properties:

\begin{aligned} & f_{1}(x)=\begin{cases} 1 & \text{ if } x \in A \cup B, \\ 2 & \text{ if } x \in C, \\ \uparrow & \text{ otherwise } \end{cases} \quad f_{2}(x)= \begin{cases} \uparrow & \text{ if } x \in A \cup C, \text{ and } \\ 0 & \text{ otherwise },\end{cases} \\ & f_{3}(x)= \begin{cases} \uparrow & \text{ if } x \in B \cup C, \\ 0 & \text{ otherwise }\end{cases} \end{aligned}

?

(a)

Prove that sets $A, B, C$ are all recursive.

(b)

Let $M_{1}, M_{2}$ and $M_{3}$ be three DTM's that compute functions $f_{1}, f_{2}$ and $f_{3}$ , respectively. Construct DTM's that simulate $M_{1}, M_{2}$ and $M_{3}$ to compute $\chi_{A}, \chi_{B}$ and $\chi_{C}$ .

Problem 5.2.4

Show that every infinite r.e. set has an infinite subset that is recursive.

?

Problem 5.2.5

(a)(b)

?

(a)

Assume that $f: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ is a partial recursive function, and $A$ is an r.e. set. Show that $f(A)$ and $f^{-1}(A)$ are r.e. (Recall that $f(A)=\left\{ f(x) \mid x \in A, f(x) \downarrow \right\}$ and $f^{-1}(A)=\left\{ x \mid f(x) \downarrow \text{, }f(x) \in A\right\}$ .

(b)

Assume that $f$ is a recursive function and $A$ is a recursive set. Is $f(A)$ recursive? Is $f^{-1}(A)$ recursive?

Problem 5.2.6

A function $f: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ is strictly increasing if $f(x)<f(x+1)$ for all $x \in \left\{ 0,1\right\}^{*}$ . Show that an infinite set $A$ is recursive if and only if $A$ is the range of a strictly increasing recursive function $f$ .

?

Problem 5.2.7

Show that the following sets are r.e.

?

(a)

$A_{1}=\left\{ n \mid \left\{ 0,1, \ldots , n\right\} \subseteq W_{n}\right\}$ .

(b)

$A_{2}=\left\{ n \mid \left|W_{n} \cap \left\{ 0,1, \ldots , n\right\} \right| \geq n / 2\right\}$ . [Hint: Use the Gödel numbering to encode $n / 2$ strings into a single string.]

(c)

$A_{3}=\left\{ \langle n, x\rangle \mid \text{ there exist }n_{1}, \ldots , n_{k}, k \geq 1\text{, such that }x \in W_{n_{1}}\text{, }n_{1} \in W_{n_{2}}, \ldots , n_{k-1} \in W_{n_{k}}, n_{k} \in W_{n}\right\}$ .

(d)

$A_{4}=\left\{ x \mid \text{ there exists an integer }n\text{ such that }\phi_{x}(y)=0\text{ for all }y \in \left\{ 0,1\right\}^{n}\right\}$ .

(e)

$A_{5}=\left\{ n \mid \text{ during the computation of }M_{n}(111), M_{n}\text{ has a configuration that contains a substring 000 }\right\}$ .

Problem 5.2.8

(a)(b)

Recall that $A B=\left\{ x y \mid x \in A, y \in B\right\}$ . Define $A+B=\left\{ n+m \mid n \in A, m \in B\right\}$ .

?

(a)

Show that if $A$ and $B$ are r.e. sets then $A B, A+B$ and $A^{*}$ are also r.e.

(b)

Show that if $A$ and $B$ are recursive sets then $A B, A+B$ and $A^{*}$ are also recursive.

Problem 5.2.9

(a)(b)

Define a set $C=\left\{ \langle x, y\rangle \mid \text{ there exists a partial recursive function }f\text{ such that }f(x)\text{ is defined and }f(x)=y\right\}$ .

?

(a)

Prove that $C$ is r.e.

(b)

Is $C$ recursive? why?

Problem 5.2.10

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}

?