Теория вычислимости

Покажите, что множество $L=\left\{ x \in \left\{ 0,1\right\}^{*} \mid x\text{ является корректным кодом }\right\}$ примитивно рекурсивно.

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

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

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

Завершите доказательство примера 5.4(c).

Покажите подробно, как универсальная ДМТ $U$ моделирует работу ДМТ $M_{y}$. В частности, приведите инструкции, которые ищут код инструкции, соответствующий текущему состоянию на ленте 3 и текущему символу на ленте 2. Затем покажите, как изменить состояние, изменить символ на ленте и сдвинуться влево или вправо в соответствии с кодом инструкции.

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

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

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

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

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

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

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

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

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

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

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

Напомним, что $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\}$.

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

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

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

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

Мы говорим, что частично рекурсивная функция $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$. Покажите, что существует частично рекурсивная функция, не являющаяся продолжимой.

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

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

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

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

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

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

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

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

Мы говорим, что два множества $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\}$.

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

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

Пусть $A$ и $B$ — непустые собственные подмножества $\Sigma^{*}$.

Покажите, что множество $\mathrm{EMP}=\left\{ x \mid W_{x}=\emptyset \right\}$ не рекурсивно.

Покажите, с помощью $s$-$m$-$n$-теоремы, что $K \leq_{m} \overline{\text{ EMP }}$.

Проблема останова $K$ полна.

Пусть $A$ — нетривиальное индексное множество функций. Покажите, что если EMP $\subseteq A$, то $A$ не является р.п. Таким образом, следующие индексные множества не являются р.п.: $\overline{A_{1}}$, EMP, $\overline{\text{ Tot }}$, Fin, Rec, Reg и Rev.

Пусть $A$ — р.п. индексное множество. Покажите, что если $x \in A$ и $W_{x} \subseteq W_{y}$, то $y \in A$. Таким образом, следующие множества не являются р.п.: $\overline{\operatorname {REC}}, \overline{\operatorname {REG}}, \overline{\operatorname {REV}}$.

Пусть $A$ — р.п. индексное множество функций. Покажите, что если $x \in A$, то существует $y \in A$ такое, что $W_{y}$ — конечное подмножество $W_{x}$. Таким образом, следующие множества не являются р.п.: Tot, $\overline{\text{ FIN }}$.

Покажите, что TOT $\leq_{m} \overline{\text{ FIN }}$ и $\overline{\text{ FIN }} \leq_{m}$ TOT.

Пусть $A \cup B= \left\{ 0,1\right\}^{*}$ и $A \cap B \neq \emptyset$. Покажите, что если $A$ и $B$ являются р.п., то $A \leq_{m} A \cap B$.

Если $g: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ инъективна, определим $g^{-1}(x)=(\min y) [g(y)=x]$. Покажите, что существует рекурсивная функция $f$ такая, что для каждой инъективной функции $\phi_{m}$ выполнено $\phi_{f(m)}=\phi_{m}^{-1}$.

Покажите, что существует рекурсивная функция $c(x, y)$ такая, что $\phi_{c(x, y)}(z)= \phi_{x}\left(\phi_{y}(z)\right)$.

(Теорема Райса для р.п. индексных множеств) Для конечного множества $D=\left\{ x_{1}, \ldots , x_{n}\right\}$ будем говорить, что $\left[x_{1}, \ldots , x_{n}\right]$ (в любом порядке) — код $D$. Покажите, что индексное множество $A$ является р.п. тогда и только тогда, когда

1. из $x \in A$ и $W_{x} \subseteq W_{y}$ следует $y \in A$;

2. из $x \in A$ следует, что существует $y \in A$ такое, что $W_{y}$ — конечное подмножество $W_{x}$; и

3. существует р.п. множество $B$, содержащее коды всех и только конечных множеств $W_{x}$ таких, что $x \in A$ (т.е. для каждого $x \in A$, для которого $W_{x}$ конечно, $B$ содержит хотя бы один его код, и для каждого $\left[x_{1}, \ldots , x_{n}\right] \in B$ и каждого $x$ такого, что $\left.W_{x}=\left\{ x_{1}, \ldots , x_{n}\right\} , x \in A\right)$.

Для каждой частично рекурсивной функции $f: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ обозначим через $D_{f}$ её область определения $\left\{ x \mid f(x) \downarrow \right\}$. Пусть $f, g, h: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ — три частично рекурсивные функции.

Определим

Является ли $f$ частично рекурсивной функцией? Докажите свой ответ.

Пусть $\mathcal{C}_{1}$ — класс всех рекурсивных множеств, $\mathcal{C}_{2}$ — класс всех р.п. множеств, не являющихся рекурсивными, $\mathcal{C}_{3}$ — класс всех ко-р.п. множеств, не являющихся р.п., а $\mathcal{C}_{4}$ — класс всех множеств, которые не являются ни р.п., ни ко-р.п. Для каждого из следующих множеств определите, какому классу $\mathcal{C}_{i}, i \in \left\{ 1,2,3,4\right\}$, оно принадлежит.

Множество $A$ называется однозначным, если для каждого $y$ существует не более одного $z$ такого, что $\langle y, z\rangle \in A$. Пусть $B_{12}=\left\{ x \mid W_{x}\text{ однозначно }\right\}$. Покажите, что EMP $\leq_{m} B_{12}$ и $B_{12} \leq_{m}$ EMP,

Докажите следующие сведения:

Пусть $B_{13}=\left\{ x \mid W_{x}=K\right\}$.

Пусть $B_{14}=\left\{ x \mid \left(\exists y \in W_{x}\right)[W_{y}\text{ бесконечно}]\right\}$.

Множество $B \subseteq \left\{ 0,1\right\}^{*}$ называется продуктивным, если существует частично рекурсивная функция $f$ такая, что для каждого $x$, если $W_{x} \subseteq B$, то $f(x) \downarrow$ и $f(x) \in B-W_{x}$.

Покажите, что существуют два р.п. множества $A$ и $B$ такие, что $A \leq_{m} B$ и $B \leq_{m} A$.

(Продолжение) Докажите теорему Райса с помощью теоремы о рекурсии.

Напишите программу (на псевдо-Паскале), которая на любом входе печатает свой собственный программный код в качестве выхода (такая программа называется самовоспроизводящейся).

Пусть $f: \mathbf{N} \rightarrow \mathbf{N}$ — рекурсивная функция. Покажите, что существует целое число $n$ такое, что $W_{n}$ — рекурсивное множество, и наименьшее целое число $m$ такое, что $W_{m}=\bar{W}_{n}$, больше $f(n)$.

(Трудолюбивый бобр) Пусть $f(x)=\min \left\{ n \mid \phi_{n}(\varepsilon )=x\right\}$. Покажите, что $f$ не является рекурсивной функцией.

Для каждой строки $x \in \left\{ 0,1\right\}^{*}$, $f(x)$ — это минимальная машина Тьюринга (в нашей стандартной нумерации), которая печатает $x$, начиная с пустого входа. Интуитивно мы можем рассматривать $f(x)$ как строку, кодирующую минимальную информацию о $x$, необходимую для того, чтобы восстановить $x$ с помощью универсальной ДМТ $U$. (Замечание: по определению, $U(f(x), \varepsilon )=x$.) Идея доказательства состоит в том, что если бы $f$ была рекурсивна, мы могли бы использовать ДМТ $M^{f}$, вычисляющую $f$, чтобы искать строки $y$, чьи «коды минимальной информации» намного больше размера $M^{j}$, и напечатать такую строку $y$. Однако, поскольку мы могли бы получить $y$, моделируя $M^{f}$, машина $M^{f}$ была бы по существу её собственным кодом минимальной информации. Таким образом, это приводит нас к противоречию. Далее мы приведём два доказательства. Первое представляет собой неформальное построение, а второе — формальное доказательство с помощью теоремы о рекурсии.

Если внимательнее посмотреть на самовоспроизводящуюся программу с рисунка 5.5 (и программу $P_{4}$ с рисунка 5.4(b)), можно увидеть, что она всё ещё не совсем корректна, поскольку все двойные кавычки в программе печатаются на выходе как одинарные кавычки. Точнее, каждая двойная кавычка в правой части первого оператора присваивания «$e_{1}:=\ldots$» сохраняется в $e_{1}$ в виде одинарной кавычки, и поэтому третий оператор «write$(e_{1})$;» печатает правую часть первого оператора с каждой двойной кавычкой, заменённой на одинарную. Исправьте эту проблему, чтобы программа печатала в точности свой собственный программный код.

Напишите компьютерную программу (на любом удобном вам языке высокого уровня), которая печатает свой код в обратном порядке.

Напишите компьютерную программу (на любом удобном вам языке высокого уровня), которая читает вход $n$ и печатает свой код $n$ раз.

Напишите компьютерную программу (на любом удобном вам языке высокого уровня), которая читает вход $x$ и выдаёт 1, если $x$ в точности совпадает с её собственным программным кодом, и выдаёт 0 в противном случае. (Такая программа называется самораспознающей.)

Докажите, что существует целое число $e \geq 0$ такое, что $W_{e}=W_{e-1} \cup W_{e+1}$.

Докажите, что для каждой рекурсивной функции $f$ существует константа $e$ такая, что $\phi_{f(e)}=\phi_{e}$.

Докажите, что существует рекурсивная функция $f$ такая, что $\phi_{\phi_{e}(f(e))}(x)= \phi_{f(e)}(x)$ для всех $x$.

Докажите, что существуют два целых числа $m \neq n$ такие, что $W_{m}=\left\{ n\right\}$ и $W_{n}=\left\{ m\right\}$.

Существует ли целое число $m$ такое, что $W_{m}=\left\{ x \mid \phi_{x}(m)\text{ определена }\right\}$? Существует ли целое число $n$ такое, что $W_{n}=\left\{ x \mid \phi_{x}(n)\text{ не определена }\right\}$? Докажите свои ответы.

Покажите, что существуют целые числа $m$ и $n$ такие, что $W_{m}=W_{n}=K$, причём $m \in K$ и $n \notin K$.

Используя теорему о рекурсии, докажите, что следующие множества не являются р.п.: Fin, Rec, $\overline{\mathrm{REC}}$.

Пусть $f$ — функция, определённая в примере 5.40. Определим $f^{*}$ как обратную к ней функцию: $f^{*}(n)=(\max x)[f(x) \leq n]$. Докажите, что $f^{*}$ растёт быстрее, чем любая рекурсивная функция $g$. То есть для любой рекурсивной функции $g$ существует $n_{0}$ такое, что $f^{*}(n)>g(n)$ для всех $n \geq n_{0}$. (Функция $f^{*}$ называется функцией трудолюбивого бобра и растёт даже быстрее функции Аккермана.)

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

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

Покажите, что проблема определения того, верно ли, что данная контекстно-свободная грамматика $G$ над алфавитом $\left\{ 0,1\right\}$ удовлетворяет условию $L(G)= \left\{ 0,1\right\}^{*}$, неразрешима.

Докажите, что задача $\mathrm{PCP}$ неразрешима (относительно некоторого алфавита $\Sigma$).