Банк задач по математике

Пример 5.9

Пусть множества $A$ и $B$ являются р.п. Покажите, что множества $A \cup B$ и $A \cap B$ также являются р.п.

?

Пример 5.10

Покажите, что множество $\left\{ y \mid W_{y} \neq \emptyset \right\}$ является р.п.

?

Пример 5.11

Покажите, что если $A$ является р.п., то $B=\bigcup_{y \in A} W_{y}$ также является р.п.

?

Пример 5.12

Покажите, что область значений частично рекурсивной функции $f$ : $\left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ является р.п. множеством.

?

Пример 5.16

Покажите, что если $A$ и $B$ — рекурсивные множества, то $A \cup B$ , $A \cap B$ и $\bar{A}$ также рекурсивны.

?

Задача 5.2.1

(a)(b)(c)

Пусть $A, B, C \subseteq \left\{ 0,1\right\}^{*}$ — р.п. множества. Пусть

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

?

(a)

Постройте ДМТ, которая моделирует параллельную работу трёх ДМТ, допускающих множества $A, B$ и $C$ , и допускает множество $D$ .

(b)

Постройте ДМТ, которая моделирует работу трёх ДМТ, допускающих множества $A, B$ и $C$ , методом чередования, и допускает $D$ .

(c)

Найдите рекурсивный предикат $R$ такой, что $D=\left\{ x \mid (\exists y) R(x, y)\right\}$ .

Задача 5.2.2

Разработайте два алгоритма чередования для множества $B$ из примера 5.11: первый — на основе интуитивного алгоритма, приведённого в решении, а второй — на основе последней строки доказательства с помощью теоремы о проекции.

?

Задача 5.2.3

(a)(b)

Пусть $A, B, C \subseteq \left\{ 0,1\right\}^{*}$ и $A \cap B=B \cap C=C \cap A=\emptyset$ . Пусть также существуют три частично рекурсивные функции $f_{1}, f_{2}, f_{3}$ , обладающие следующими свойствами:

\begin{aligned} & f_{1}(x)=\begin{cases} 1 & \text{ если } x \in A \cup B, \\ 2 & \text{ если } x \in C, \\ \uparrow & \text{ иначе } \end{cases} \quad f_{2}(x)= \begin{cases} \uparrow & \text{ если } x \in A \cup C, \text{ и } \\ 0 & \text{ иначе },\end{cases} \\ & f_{3}(x)= \begin{cases} \uparrow & \text{ если } x \in B \cup C, \\ 0 & \text{ иначе }\end{cases} \end{aligned}

?

(a)

Докажите, что множества $A, B, C$ все рекурсивны.

(b)

Пусть $M_{1}, M_{2}$ и $M_{3}$ — три ДМТ, вычисляющие функции $f_{1}, f_{2}$ и $f_{3}$ соответственно. Постройте ДМТ, которые моделируют работу $M_{1}, M_{2}$ и $M_{3}$ для вычисления $\chi_{A}, \chi_{B}$ и $\chi_{C}$ .

Задача 5.2.4

Покажите, что каждое бесконечное р.п. множество имеет бесконечное рекурсивное подмножество.

?

Задача 5.2.5

(a)(b)

?

(a)

Пусть $f: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ — частично рекурсивная функция, а $A$ — р.п. множество. Покажите, что $f(A)$ и $f^{-1}(A)$ являются р.п. (Напомним, что $f(A)=\left\{ f(x) \mid x \in A, f(x) \downarrow \right\}$ и $f^{-1}(A)=\left\{ x \mid f(x) \downarrow \text{, }f(x) \in A\right\}$ .)

(b)

Пусть $f$ — рекурсивная функция, а $A$ — рекурсивное множество. Является ли $f(A)$ рекурсивным? Является ли $f^{-1}(A)$ рекурсивным?

Задача 5.2.6

Функция $f: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ называется строго возрастающей, если $f(x)<f(x+1)$ для всех $x \in \left\{ 0,1\right\}^{*}$ . Покажите, что бесконечное множество $A$ рекурсивно тогда и только тогда, когда $A$ является областью значений строго возрастающей рекурсивной функции $f$ .

?

Задача 5.2.7

Покажите, что следующие множества являются р.п.

?

(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\}$ . [Указание: используйте гёделеву нумерацию, чтобы закодировать $n / 2$ строк в одну строку.]

(c)

$A_{3}=\left\{ \langle n, x\rangle \mid \text{ существуют }n_{1}, \ldots , n_{k}, k \geq 1\text{, такие, что }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{ существует целое число }n\text{ такое, что }\phi_{x}(y)=0\text{ для всех }y \in \left\{ 0,1\right\}^{n}\right\}$ .

(e)

$A_{5}=\left\{ n \mid \text{ в процессе вычисления }M_{n}(111)\text{ машина }M_{n}\text{ проходит через конфигурацию, содержащую подстроку 000 }\right\}$ .

Задача 5.2.8

(a)(b)

Напомним, что $A B=\left\{ x y \mid x \in A, y \in B\right\}$ . Определим $A+B=\left\{ n+m \mid n \in A, m \in B\right\}$ .

?

(a)

Покажите, что если $A$ и $B$ — р.п. множества, то $A B$ , $A+B$ и $A^{*}$ также являются р.п.

(b)

Покажите, что если $A$ и $B$ — рекурсивные множества, то $A B$ , $A+B$ и $A^{*}$ также рекурсивны.

Задача 5.2.9

(a)(b)

Определим множество $C=\left\{ \langle x, y\rangle \mid \text{ существует частично рекурсивная функция }f\text{ такая, что }f(x)\text{ определена и }f(x)=y\right\}$ .

?

(a)

Докажите, что $C$ является р.п.

(b)

Является ли $C$ рекурсивным? Почему?

Задача 5.2.10

Покажите, что следующая функция частично рекурсивна:

g(i, j, k)= \begin{cases} k & \text{ если }(\exists n)\left[\phi _{i}(n)=\phi _{j}(n)=k\right] \\ \uparrow & \text{ иначе }.\end{cases}

?

Рекурсивно перечислимые и рекурсивные множества