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

Пусть 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)не определено. Это означает, что машина TK не останавливается начав работу над цепочкойβ_K. В этом случае. Следовательно,G(β_K)=0, поэтомуK(β_K), т.е. значение функцииK(β_K)– определено, что противоречит сделанному предположению. Аналогично получается противоречие в предположении, чтоK(β_K)определено, что в итоге завершает доказательство теоремы Тьюринга.

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

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

Теорема:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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