Вычислимость и неразрешимые проблемы

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

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

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

Реализовать машину, вычисляющую сводящую функцию $f$ из доказательства теоремы 170 на стр. 446 в случае алфавита $\Sigma =\left\{ a, b\right\}$.

Теорема 170: Проблема $\mathrm{TOTAL}$ неразрешима.

Доказать алгоритмическую неразрешимость проблемы полноты тестовых данных $\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}$.

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

Доказать, что для двух разрешимых множеств $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$ шагов.

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

Реализовать машину $\mathfrak {M}$ из доказательства теоремы 173 на стр. 451 в случае алфавита $\Sigma =\left\{ a, b\right\}$.

Теорема 173: Функция оптимального сжатия arc невычислима.

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