III.4

Нумерации Клини и Поста

[43/91%]
Показать
LaTeX
Задача III.4.1

Доказать, что:

?
(а)

[x,y][x,y] осуществляет взаимно однозначное соответствие между N2\mathbb {N}^{2} и N\mathbb {N};

(б)

[x1,…,xn][x_{1}, \ldots , x_{n}] осуществляет взаимно однозначное соответствие между Nn\mathbb {N}^{n} и N\mathbb {N};

(в)

[[x]12,[x]22]=x[[x]_{1}^{2}, [x]_{2}^{2}] = x, [[x,y]]12=x[[x,y]]_{1}^{2} = x, [[x,y]]22=y[[x,y]]_{2}^{2} = y;

(г)

[[x]1n,…,[x]nn]=x[[x]_{1}^{n}, \ldots , [x]_{n}^{n}] = x, [[x1,…,xn]]in=xi[[x_{1}, \ldots , x_{n}]]_{i}^{n} = x_{i};

(д)

[x1,…,xm,xm+1,…,xn]=[[x1,…,xm],xm+1,…,xn][x_{1}, \ldots , x_{m}, x_{m+1}, \ldots , x_{n}] = [[x_{1}, \ldots , x_{m}], x_{m+1}, \ldots , x_{n}];

(е)

c(x0,c(x1,x2))=[c(x0,x1),x2]c(x_{0}, c(x_{1}, x_{2})) = [c(x_{0}, x_{1}), x_{2}].

Задача III.4.2

Доказать, что:

?
(а)

Kn+m+1(x0,x1,…,xn,xn+1,…,xn+m)=Km+1([x0,x1,…,xn],xn+1,…,xn+m)K^{n+m+1}(x_{0}, x_{1}, \ldots , x_{n}, x_{n+1}, \ldots , x_{n+m}) = K^{m+1}([x_{0}, x_{1}, \ldots , x_{n}], x_{n+1}, \ldots , x_{n+m});

(б)

Kn(c(x0,x1),x2,…,xn)=Un+1(x0,x1,x2,…,xn)K^{n}(c(x_{0}, x_{1}), x_{2}, \ldots , x_{n}) = U^{n+1}(x_{0}, x_{1}, x_{2}, \ldots , x_{n}).

Задача III.4.3

Доказать, что:

?
(а)

Kn+1(x0,x1,…,xn)K^{n+1}(x_{0}, x_{1}, \ldots , x_{n}) является универсальной для всех nn-местных частично рекурсивных функций;

(б)

для любой частично рекурсивной функции fn+mf^{n+m} существует примитивно рекурсивная функция gng^{n} такая, что

f(x1,…,xn,y1,…,ym)=Km+1(g(x1,…,xn),y1,…,ym). f(x_{1}, \ldots , x_{n}, y_{1}, \ldots , y_{m}) = K^{m+1}(g(x_{1}, \ldots , x_{n}), y_{1}, \ldots , y_{m}).
Задача III.4.4

Доказать, что всякая частично рекурсивная функция ff имеет бесконечно много клиниевских номеров.

?
Задача III.4.5

Построить примитивно рекурсивные функции, дающие по клиниевским номерам исходных одноместных функций клиниевские номера функций, получающихся из исходных:

?
(а)

с помощью суперпозиции;

(б)

с помощью обращения;

(в)

с помощью итерации;

(г)

с помощью взятия суммы двух функций.

Задача III.4.6

Доказать, что существует рекурсивно перечислимое множество PP, удовлетворяющее условиям:

?
(а)

если x∈Px \in P, то κx\kappa_{x} есть примитивно рекурсивная функция;

(б)

для любой примитивно рекурсивной функции ff существует x∈Px \in P такое, что f=κxf = \kappa_{x}.

Задача III.4.7

Доказать, что существует общерекурсивная функция, универсальная для семейства всех одноместных примитивно рекурсивных функций.

?
Задача III.4.8

Построить примитивно рекурсивные функции, дающие по клиниевским номерам исходных функций клиниевские номера функций, получающихся из исходных:

?
(а)

с помощью суперпозиции;

(б)

с помощью примитивной рекурсии;

(в)

с помощью μ\mu-оператора.

Задача III.4.9

Доказать, что для любой частично рекурсивной функции f(x1,…,xn)f(x_{1}, \ldots , x_{n}) существует такая примитивно рекурсивная функция g(x1,…,xn)g(x_{1}, \ldots , x_{n}), что для любого xx

κg(x1,…,xn)={κf(x1,…,xn),если f(x1,…,xn) определено,ωв противном случае. \kappa _{g(x_{1}, \ldots , x_{n})} = \begin{cases} \kappa _{f(x_{1}, \ldots , x_{n})}, & \text{если } f(x_{1}, \ldots , x_{n}) \text{ определено,} \\ \omega & \text{в противном случае.} \end{cases}
?
Задача III.4.10
?
(а)

Доказать, что для каждой частично рекурсивной функции f(x1,…,xn,y)f(x_{1}, \ldots , x_{n}, y) существует такая примитивно рекурсивная функция g(x1,…,xn)g(x_{1}, \ldots , x_{n}), что

κg(x1,…,xn)={κf(x1,…,xn,g(x1,…,xn)),если f(x1,…,xn,g(x1,…,xn)) определено,ωв противном случае. \kappa _{g(x_{1}, \ldots , x_{n})} = \begin{cases} \kappa _{f(x_{1}, \ldots , x_{n}, g(x_{1}, \ldots , x_{n}))}, & \text{если } f(x_{1}, \ldots , x_{n}, g(x_{1}, \ldots , x_{n})) \text{ определено,} \\ \omega & \text{в противном случае.} \end{cases}
(б)

Доказать, что для каждой частично рекурсивной функции f(x)f(x) существует такое натуральное число aa, что

κa={κf(a),если f(a) определено,ωв противном случае \kappa _{a} = \begin{cases} \kappa _{f(a)}, & \text{если } f(a) \text{ определено,} \\ \omega & \text{в противном случае} \end{cases}

(теорема о неподвижной точке).

Задача III.4.11

Доказать, что для любой частично рекурсивной функции f(x,y)f(x,y) существует число nn такое, что f(n,y)=κn(y)f(n,y) = \kappa_{n}(y) для всех yy.

?
Задача III.4.12

Доказать, что существует число nn такое, что:

?
(а)

κn(0)=n\kappa_{n}(0) = n;

(б)

κn(n)=n\kappa_{n}(n) = n.

Задача III.4.13

Доказать, что существует примитивно рекурсивная функция ff такая, что для любого xx, если κx\kappa_{x} есть общерекурсивная функция, то

κκx(f(x))=κf(x). \kappa _{\kappa _{x}(f(x))} = \kappa _{f(x)}.
?
Задача III.4.14

Построить частично рекурсивные функции κa\kappa_{a} такие, что:

?
(а)

κa=χ{a}\kappa_{a} = \chi_{\left\{ a\right\} };

(б)

κa=χ{a}∗\kappa_{a} = \chi_{\left\{ a\right\} }^{*};

(в)

κa=χN−{a}∗\kappa_{a} = \chi_{\mathbb {N} - \left\{ a\right\} }^{*}.

Задача III.4.15

Пусть F\mathcal{F} --- семейство всех одноместных частичных функций. Отображение F:F→FF: \mathcal{F} \to \mathcal{F} назовем эффективным оператором, если функция g(n,x)=(F(κn))(x)g(n,x) = (F(\kappa_{n}))(x) частично рекурсивна. Доказать, что для любого эффективного оператора FF существует частично рекурсивная функция ff такая, что f=F(f)f = F(f).

?
Задача III.4.16

Доказать, что для любых частично рекурсивных функций α,γ,δ\alpha , \gamma , \delta существует частично рекурсивная функция ff, удовлетворяющая условиям:

?
(а)

если α(x)=0\alpha (x) = 0, то f(x)=0f(x) = 0;

(б)

если α(x)>0\alpha (x) > 0, то f(x)=γ(f(δ(x)))f(x) = \gamma (f(\delta (x))).

Задача III.4.17

Пусть A\mathcal{A} --- некоторое непустое семейство одноместных частично рекурсивных функций, отличное от семейства всех таких функций. Доказать, что множество

κ−1(A)={x∣κx∈A} \kappa ^{-1}(\mathcal{A}) = \left\{ x \mid \kappa _{x} \in \mathcal{A}\right\}

не является рекурсивным (теорема Райса).

?
Задача III.4.18

Доказать, что следующие множества не рекурсивны:

?
(а)

A1={x∣κx — константа}A_{1} = \left\{ x \mid \kappa_{x} \text{ --- константа}\right\};

(б)

A2={x∣κx(a)=b}A_{2} = \left\{ x \mid \kappa_{x}(a) = b\right\}, где a,ba, b --- фиксированные числа;

(в)

A3={c(x,y)∣y∈δκx}A_{3} = \left\{ c(x,y) \mid y \in \delta_{\kappa_{x}}\right\};

(г)

A4={c(x,y)∣y∈ρκx}A_{4} = \left\{ c(x,y) \mid y \in \rho_{\kappa_{x}}\right\};

(д)

A5={c(x,y)∣κx=κy}A_{5} = \left\{ c(x,y) \mid \kappa_{x} = \kappa_{y}\right\}.

Задача III.4.19

Доказать рекурсивную перечислимость множеств всех клиниевских номеров следующих семейств одноместных частично рекурсивных функций:

?
(а)

функций, определенных в точке 00;

(б)

функций ff таких, что f(a)=bf(a) = b для данных чисел aa и bb;

(в)

функций с непустой областью определения.

Задача III.4.20

Доказать, что всякое рекурсивно перечислимое множество имеет бесконечно много постовских номеров.

?
Задача III.4.21

Пусть A\mathcal{A} --- некоторое непустое семейство рекурсивно перечислимых множеств, отличное от семейства всех рекурсивно перечислимых множеств. Доказать, что множество

π−1(A)={x∣πx∈A} \pi ^{-1}(\mathcal{A}) = \left\{ x \mid \pi _{x} \in \mathcal{A}\right\}

не является рекурсивным (теорема Райса).

?
Задача III.4.22

Доказать, что не рекурсивны множества:

?
(а)

{x∣πx≠∅}\left\{ x \mid \pi_{x} \neq \emptyset \right\};

(б)

{x∣πx=N}\left\{ x \mid \pi_{x} = \mathbb {N}\right\};

(в)

{x∣a∈πx}\left\{ x \mid a \in \pi_{x}\right\}, где aa --- фиксированное число;

(г)

{x∣πx конечно}\left\{ x \mid \pi_{x} \text{ конечно}\right\};

(д)

{c(x,y)∣πx=πy}\left\{ c(x,y) \mid \pi_{x} = \pi_{y}\right\}.

Задача III.4.23

Доказать, что рекурсивно перечислимы множества всех постовских номеров следующих семейств рекурсивно перечислимых множеств:

?
(а)

содержащих данное число aa;

(б)

непустых.

Задача III.4.24

Доказать, что для любой частично рекурсивной функции fnf^{n} существует примитивно рекурсивная функция gng^{n} такая, что

πg(x1,…,xn)={πf(x1,…,xn),если f(x1,…,xn) определено,∅в противном случае. \pi _{g(x_{1}, \ldots , x_{n})} = \begin{cases} \pi _{f(x_{1}, \ldots , x_{n})}, & \text{если } f(x_{1}, \ldots , x_{n}) \text{ определено,} \\ \emptyset & \text{в противном случае.} \end{cases}
?
Задача III.4.25

Доказать, что для каждого рекурсивно перечислимого множества P⊆Nn+1P \subseteq \mathbb {N}^{n+1} (n>0n > 0) существует такая примитивно рекурсивная функция α(x1,…,xn)\alpha (x_{1}, \ldots , x_{n}), что

⟨x0,x1,…,xn⟩∈P⇔x0∈πα(x1,…,xn). \langle x_{0}, x_{1}, \ldots , x_{n} \rangle \in P \Leftrightarrow x_{0} \in \pi _{\alpha (x_{1}, \ldots , x_{n})}.
?
Задача III.4.26

Доказать, что существуют примитивно рекурсивные функции f,g,h,u,v,wf, g, h, u, v, w такие, что:

?
(а)

πx∩πy=πf(x,y)\pi_{x} \cap \pi_{y} = \pi_{f(x,y)};

(б)

πx∪πy=πg(x,y)\pi_{x} \cup \pi_{y} = \pi_{g(x,y)};

(в)

{x}=πh(x)\left\{ x\right\} = \pi_{h(x)};

(г)

{c(s,t)∣s∈πx,t∈πy}=πu(x,y)\left\{ c(s,t) \mid s \in \pi_{x}, t \in \pi_{y}\right\} = \pi_{u(x,y)};

(д)

κy(πx)=πv(x,y)\kappa_{y}(\pi_{x}) = \pi_{v(x,y)};

(е)

κy−1(πx)=πw(x,y)\kappa_{y}^{-1}(\pi_{x}) = \pi_{w(x,y)}.

Задача III.4.27

Доказать, что существуют примитивно рекурсивные функции ff и gg такие, что:

?
(а)

δκx=ρκf(x)\delta_{\kappa_{x}} = \rho_{\kappa_{f(x)}};

(б)

ρκx=δκg(x)\rho_{\kappa_{x}} = \delta_{\kappa_{g(x)}}.

Задача III.4.28
?
(а)

Доказать, что для любой частично рекурсивной функции fn+1f^{n+1} существует примитивно рекурсивная функция gng^{n} такая, что

πg(x1,…,xn)={πf(x1,…,xn,g(x1,…,xn)),если f(x1,…,xn,g(x1,…,xn)) определено,∅в противном случае. \pi _{g(x_{1}, \ldots , x_{n})} = \begin{cases} \pi _{f(x_{1}, \ldots , x_{n}, g(x_{1}, \ldots , x_{n}))}, & \text{если } f(x_{1}, \ldots , x_{n}, g(x_{1}, \ldots , x_{n})) \text{ определено,} \\ \emptyset & \text{в противном случае.} \end{cases}
(б)

Доказать, что для любой частично рекурсивной функции ff существует такое число aa, что

πa={πf(a),если f(a) определено,∅в противном случае \pi _{a} = \begin{cases} \pi _{f(a)}, & \text{если } f(a) \text{ определено,} \\ \emptyset & \text{в противном случае} \end{cases}

(теорема о неподвижной точке).

Задача III.4.29

Доказать, что для любого рекурсивно перечислимого множества M⊆Nn+2M \subseteq \mathbb {N}^{n+2} существует примитивно рекурсивная функция gng^{n} такая, что

⟨x0,x1,…,xn,g(x1,…,xn)⟩∈M⇔x0∈πg(x1,…,xn). \langle x_{0}, x_{1}, \ldots , x_{n}, g(x_{1}, \ldots , x_{n}) \rangle \in M \Leftrightarrow x_{0} \in \pi _{g(x_{1}, \ldots , x_{n})}.
?
Задача III.4.30

Доказать, что существует число nn такое, что:

?
(а)

πn={n}\pi_{n} = \left\{ n\right\};

(б)

πn={n2}\pi_{n} = \left\{ n^{2}\right\};

(в)

πn=N∖{n}\pi_{n} = \mathbb {N} \setminus \left\{ n\right\}.

Задача III.4.31

Доказать, что отношение ≤m\leq_{m} рефлексивно и транзитивно.

?
Задача III.4.32

Доказать, что всякое рекурсивное множество mm-сводимо к любому непустому множеству с непустым дополнением.

?
Задача III.4.33

Доказать, что если AA mm-сводимо к рекурсивному (рекурсивно перечислимому) множеству, то AA рекурсивно (рекурсивно перечислимо).

?
Задача III.4.34

Доказать, что множество

K1={c(x,y)∣x∈πy} K_{1} = \left\{ c(x,y) \mid x \in \pi _{y}\right\}

является mm-универсальным.

?
Задача III.4.35

Доказать, что каждое mm-универсальное множество не рекурсивно.

?
Задача III.4.36

Доказать, что множество

K={x∣x∈πx} K = \left\{ x \mid x \in \pi _{x}\right\}

является креативным.

?
Задача III.4.37

Доказать, что каждое креативное множество не рекурсивно.

?
Задача III.4.38

Доказать, что если AA --- креативное множество, A≤mBA \leq_{m} B и BB рекурсивно перечислимо, то BB креативно.

?
Задача III.4.39

Доказать, что каждое креативное множество является mm-универсальным.

?
Задача III.4.40

Доказать, что множество mm-универсально тогда и только тогда, когда оно креативно.

?
Задача III.4.41

Доказать, что множество

K2={x∣πx≠∅} K_{2} = \left\{ x \mid \pi _{x} \neq \emptyset \right\}

является креативным.

?
Задача III.4.42

Доказать, что существует примитивно рекурсивная функция σ(x)\sigma (x) такая, что машина Тьюринга с номером σ(x)\sigma (x) вычисляет функцию κx\kappa_{x}.

?
Задача III.4.43

Доказать, что множество HH из задачи III.3.43 из 3 является креативным.

?