6. Проблема остановки. Теорема Тьюринга.

Пусть M_S – множество всех пар цепочек в алфавите V, в каждой паре первая цепочка – это словарное представление некоторой МТ, а вторая цепочка – это такая цепочка, на которой данная МТ останавливается.

Теорема Тьюринга:

Проблема остановки МТ неразрешима.

Доказательство.

В данной теореме необходимо установить, является ли вычислимой характеристическая функция . Пусть это так, и пустьT_F соответствует машине Тьюринга вычисляющей эту функцию. Из вычислимости функции и разрешимости множестваM_T словарных представлений всех МТ в алфавите V следует, что вычислимой будет частичная одноместная функция , которая задаётся следующим образом:,. ФункцияG не определена для цепочек . Введём ещё одну функцию. Эта функция определена только для тех цепочек α, для которых, причём. ФункцияK вычислима, если вычислима функция G. Действительно, т.к. МТ T_K совпадает с машиной Тьюринга T_G, за исключением случая, когда T_G останавливается. В этом случае T_K продолжает работу, выявляя, какой будет результат 1 или 0. В первом случае она зацикливается, а во втором – останавливается.

Пусть β_K – словарное представление МТ T_K в алфавите V. Нужно узнать, определено ли значение K(β_K), т.е. необходимо решить проблему остановки для машины T_K и её словарного представления.

Допустим, что значение K(β_K) не определено. Это означает, что машина T_K не останавливается, начав работу над цепочкой β_K. В этом случае . Следовательно,G(β_K)=0, поэтому K(β_K)=0, т.е. значение функции K(β_K) – определено, что противоречит сделанному предположению. Аналогично получается противоречие в предположении, что K(β_K) определено, что в итоге завершает доказательство теоремы Тьюринга.

7. Проблема пустой ленты. Проблема зацикливания.

Здесь решается частичная проблема остановки. Остановка МТ применяется к пустой ленте, т.е. проверяется, разрешимо ли множество M_ε словарного представления всех тех МТ, которые останавливаются, начав работу с пустой лентой.

Теорема: Проблема пустой ленты не разрешима.

В доказательстве используется метод сведения.

Известная проблема, про которую мы хотим узнать, сводится к исследованной. Здесь первая проблема будет неразрешимой, если неразрешима исследованная проблема. Те проблемы, которые уже исследовались, считаются базовыми для доказательства других проблем. Одной из базовых проблем является проблема тождества слов Поста.

Пусть X ={α₁, α₂, … , α_n}, Y={β₁, β₂, …, β_n}, X и Y называем системой Поста. Здесь α_i и β_i – символы алфавита V. Непустую конечную последовательность индексов i₁, i₂ ,…, i_k (1≤j≤k) называют решением системы Поста, если .

Проблема Поста состоит в следующем - существует ли алгоритм для решения этой проблемы. Проблема не разрешима, если алфавит содержит более одного символа, но она является частично разрешимой.

Проблема зацикливания.

Существует ли алгоритм, хотя бы частичный, который выясняет заранее, для произвольной МТ и произвольной начальной цепочки α, будет ли МТ работать бесконечно долго. Это означает, что необходимо установить, будет ли разрешимо или перечислимо множество всех пар цепочек таких, что первая цепочка – это словарное представление некоторой МТ, а вторая цепочка – та, на которой данная машина зацикливается.

Теорема о зацикливании:

Проблема зацикливания МТ не является частично разрешимой.

Доказательство.

Из теоремы Поста и перечислимости множества M_S из теоремы об остановке следует, что дополнение до множества всех пар цепочек в алфавите V не является перечислимым (т.к. в противном случае множествоM_S было бы разрешимо, что противоречит теореме об остановке).

Можно представить

M_c – множество, свойство которого мы доказываем.

M_d – это множество всех пар цепочек, первая цепочка которых есть словарное представление некоторой МТ.

Множества M_d и разрешимы, поскольку множествоM_T словарных представлений МТ является разрешимым.

Предположим, что проблема зацикливания частично разрешима. Это значит, что множество M_c перечислимо, тогда перечислимо окажется множество , что противоречит доказанному выше.

Вывод: проблема отладки программ не разрешима.