Проблема остановки

Пусть 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) определено, что в итоге завершает доказательство теоремы Тьюринга.

Проблемы пустой ленты и метод сведения

Здесь решается частичная проблема остановки. Остановка Машины Тьюринга применяется к пустой ленте, т.е. проверяется, разрешимо ли множество 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 перечислимо, тогда перечислимо окажется множество , что противоречит доказанному выше.

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