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

Пример 5.18

Покажите, что множество $F$ функций из $\mathbf{N}$ в $\left\{ 0,1\right\}$ несчётно.

?

Пример 5.19

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

?

Пример 5.21

Мы говорим, что частично рекурсивная функция $f: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ продолжима, если существует рекурсивная функция $g: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ такая, что $g(x)=f(x)$ всякий раз, когда $f(x) \downarrow$ . Покажите, что существует частично рекурсивная функция, не являющаяся продолжимой.

?

Пример 5.22

Покажите, что TOT $=\left\{ n \mid W_{n}= \left\{ 0,1\right\}^{*}\right\} =\left\{ n \mid \phi_{n}\text{ рекурсивна }\right\}$ не является р.п.

?

Пример 5.23

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

?

Задача 5.3.1

Пусть $A$ — произвольное множество (не обязательно счётное). Покажите, что не существует взаимно однозначного соответствия между множеством $A$ и множеством $2^{A}$ всех подмножеств $A$ .

?

Задача 5.3.2

Покажите, что множество $F_{1}$ всех инъективных возрастающих функций из $\mathbf{N}$ в N несчётно.

?

Задача 5.3.3

(a)(b)

Что не так в следующих диагональных доказательствах?

?

(a)

Мы покажем, что существует частично рекурсивная функция $f: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ , которая не перечислена среди $\phi_{0}, \phi_{1}, \ldots$ . Определим $f(n)= \phi_{n}(n)+1$ . Тогда, в силу существования универсальной ДМТ, видно, что $f$ частично рекурсивна. Таким образом, мы получили частично рекурсивную функцию $f$ , отличную от каждой $\phi_{n}$ на входе $n$ , $n \geq 0$ .

(b)

Мы покажем, что множество $\operatorname {REC}=\left\{ x \mid W_{x}\text{ рекурсивно }\right\}$ не является р.п. Предположим, от противного, что REC является р.п. Тогда существует рекурсивная функция $g$ , областью значений которой является REC. Определим $A=\left\{ x \mid x \notin W_{g(x)}\right\}$ . Поскольку каждое $W_{g(x)}$ рекурсивно, разрешимо, принадлежит ли $x$ множеству $W_{g(x)}$ . Следовательно, $A$ — рекурсивное множество. Но это противоречие, поскольку $A \neq W_{g(x)}$ для каждого $x \geq 0$ .

Задача 5.3.4

Пусть $A \subseteq \mathbf{N}$ — множество со следующими свойствами: (i) $\phi_{n}$ рекурсивна для всех $n \in A$ , и (ii) для каждой рекурсивной функции $f$ имеем $f=\phi_{n}$ для некоторого $n \in A$ . Покажите, что $A$ не является р.п. множеством.

?

Задача 5.3.5

(a)(b)

?

(a)

Покажите, что класс примитивно рекурсивных функций эффективно перечислим (в том смысле, что существует р.п. множество $B$ такое, что (i) $\phi_{n}$ примитивно рекурсивна для всех $n \in B$ , и (ii) для каждой примитивно рекурсивной функции $g$ имеем $g=\phi_{n}$ для некоторого $n \in B$ ).

(b)

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

Задача 5.3.6

Покажите, что множество $A=\left\{ n \mid \phi_{n}\text{ останавливается на }n\text{, и её выход больше }n\right\}$ не является рекурсивным множеством.

?

Задача 5.3.7

Покажите, что множество $\left\{ \langle i, j\rangle \mid W_{i}=\overline{W_{j}}\right\}$ не является р.п. множеством.

?

Задача 5.3.8

Мы говорим, что два множества $A$ и $B$ рекурсивно отделимы, если существует рекурсивное множество $C$ такое, что $A \subseteq C$ и $B \subseteq \bar{C}$ . Покажите, что для любых $n \neq m \in \mathbf{N}$ множества $K_{n}$ и $K_{m}$ не являются рекурсивно отделимыми, где $K_{n}=\left\{ x \mid \phi_{x}(x)\text{ определена и равна }n\right\}$ .

?

Задача 5.3.9

Дайте формальное доказательство того, что множество $S$ , определённое в примере 5.23, является р.п. А именно, пусть $h(e)$ — строка, печатаемая на стадии $e$ алгоритмом для $S$ ( $h(e) \uparrow$ , если на стадии $e$ не выводится никакая строка). Докажите, что $h$ частично рекурсивна (не используя тезис Чёрча — Тьюринга).

?

Задача 5.3.10

Покажите, что существует множество $A$ такое, что и $A$ , и $\bar{A}$ бесконечны, но ни одно из них не имеет бесконечного р.п. подмножества.

?

Диагонализация