Тезис Тьюринга-Чёрча и неразрешимые проблемы

Найти точное количество машин Тьюринга, которые имеют вид $\mathfrak {M}=\left(Q, \Sigma , P, q_{0}\right)$ с заранее зафиксированными множеством состояний $Q$ и алфавитом ленты $\Sigma$.

Пусть зафиксирован такой алфавит машин Тьюринга: $\left\{ \Lambda , \mid \right\}$. Для функции «усердного бобра» bb

Доказать, что отношение алгоритмической сводимости $\leqslant_{m}$ является рефлексивным и транзитивным.

Доказать алгоритмическую неразрешимость проблемы полноты тестовых данных $\mathrm{TEST}$. Проблема состоит из троек ($\pi (\mathfrak {M}), x, q)$ таких, что в вычислении машины Тьюринга $\mathfrak {M}$ на входе $x$ встречается состояние $q$.

Доказать алгоритмическую неразрешимость проблемы нуля $\mathrm{ZERO}$. Проблема $\mathrm{ZERO}$ состоит из кодов $\pi (\mathfrak {M})$ машин Тьюринга $\mathfrak {M}$ таких, что $\mathfrak {M}(x)=\varepsilon$ для всех $x$. Указание. Свести $\mathrm{TOTAL}$ к $\mathrm{ZERO}$.

Доказать алгоритмическую неразрешимость следующей проблемы эквивалентности $\mathrm{EQU}$. Проблема $\mathrm{EQU}$ состоит из пар $(\pi (\mathfrak {M}), \pi (\mathfrak {N}))$ таких, что машины $\mathfrak {M}$ и $\mathfrak {N}$ эквивалентны. Указание. Свести $\mathrm{ZERO}$ к $\mathrm{EQU}$.

Доказать алгоритмическую неразрешимость проблемы константы $\mathrm{CONST}$. Проблема $\mathrm{CONST}$ состоит из таких $\pi (\mathfrak {M})$, что машина Тьюринга $\mathfrak {M}$ на любом входе возвращает один и тот же результат, если вообще останавливается. Указание. Свести дополнение $\mathrm{SELF}$ к $\mathrm{CONST}$.

Доказать алгоритмическую неразрешимость проблемы возрастания $\mathrm{GROW}$. Проблема $\mathrm{GROW}$ состоит из таких $\pi (\mathfrak {M})$, что машина Тьюринга $\mathfrak {M}$ вычисляет арифметическую функцию и при этом выполнено $\mathfrak {M}(x)<\mathfrak {M}(y)$ для всех $x<y$, когда оба значения определены. Указание. Свести дополнение $\mathrm{SELF}$ к $\mathrm{GROW}$.

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

Доказать, что для двух разрешимых множеств $A$ и $B$ натуральных чисел их «сумма» $A+B=\left\{ x+y: x \in A, y \in B\right\}$ и «произведение» (не декартово!) $A \cdot B=\left\{ x \cdot y: x \in A, y \in B\right\}$ также являются разрешимыми множествами.

Доказать, что для двух разрешимых языков $L$ и $K$ в алфавите $\Sigma$ их конкатенация $L K$ и итерация $L^{*}$ тоже будут разрешимыми языками.

Пусть $A$ — разрешимое множество, а $g(x)$ и $h(x)$ являются о. р. ф. Доказать, что функция

также является общерекурсивной.

Доказать, что проблема ограниченной остановки разрешима. Проблема состоит из троек вида ($\pi (\mathfrak {M}), x, t)$ таких, что вычисление машины Тьюринга $\mathfrak {M}$ на входе $x$ останавливается не более чем за $t$ шагов.

Показать, что при построении проекции язык из разрешимого может стать неразрешимым.

Показать, что функция arc неограниченно возрастает, но не монотонна: может быть $\operatorname {arc}(u)<\operatorname {arc}(v)$, даже если слово $v$ короче слова $u$.

Показать, что функция arc растёт медленнее каждой вычислимой функции: если для о. р. ф. $f$ выполнено $f(x) \leqslant \operatorname {arc}(x)$ для всех $x$, то $f$ ограничена.

Пусть $T(n)$ — наибольшее время работы машины Тьюринга с $n$ состояниями на пустой ленте. Доказать, что функция $T(n)$ невычислима.

Рабочей областью машины Тьюринга $\mathfrak {M}$ на входе $x$ назовём множество ячеек, в которых побывала головка машины до её остановки. Обозначим с помощью $S(\mathfrak {M}, x)$ размер рабочей области машины $\mathfrak {M}$ на входе $x$. Если машина $\mathfrak {M}$ на $x$ не останавливается, то значение $S(\mathfrak {M}, x)$ может быть произвольным. Допустим, что для машины $\mathfrak {M}$ функция $S(\mathfrak {M}, x)$ мажорируется общерекурсивной функцией $S^{*}(x)$ : $S(\mathfrak {M}, x) \leqslant S^{*}(x)$ для всех $x$. Доказать, что проблема $\mathrm{HALT}_{\mathfrak {M}}$ остановки для машины $\mathfrak {M}$ алгоритмически разрешима.

Доказать, что функция $S(\pi (\mathfrak {M}), x)$ из предыдущей задачи невычислима.

Для любой пары множеств $A$ и $B$ определим

Доказать, что для любого множества $C$ условие $A \vee B \leqslant_{m} C$ выполнено тогда и только тогда, когда $A \leqslant_{m} C$ и $B \leqslant_{m} C$.

Непустое множество $A$ называется рекурсивно перечислимым, если оно является областью значений некоторой о. р. ф. $f$ : $A=\left\{ f(0), f(1), f(2), \ldots \right\}$. Доказать, что

Доказать, что множество $\mathrm{TOTAL}$ не является рекурсивно перечислимым. Указание. Для универсальной машины Тьюринга $\mathfrak {U}$ рассмотреть функцию $\mathfrak {U}(f(x), x) \& a$ (конкатенация с непустым символом).

Доказать, что существует ч.р.ф. $f$, которую нельзя дополнить ни до какой о. р. ф. $g$, то есть такой, что $f(x)=g(x)$ для всех $x \in \operatorname {dom} f$. Указание. Для универсальной машины Тьюринга $\mathfrak {U}$ рассмотреть арифметическую функцию $f(x)=\mathfrak {U}(x, x)+1$.