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

 

3.1.  Формулировка проблемы  остановки машины Тьюринга

Имеет место быть следующая теорема: не существует алгоритма (машины Тьюринга), позволяющего по описанию произвольного алгоритма и его исходных данных (и алгоритм и данные заданы символами на ленте машины Тьюринга) определить, останавливается ли этот алгоритм на этих данных или работает бесконечно.[6]

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

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

Проблема остановки машины Тьюринга формулируется следующим образом: дана машина Тьюринга в произвольной конфигурации со строкой непустых ленточных символов конечной длины. Остановиться ли она в конце концов? [4]

Говорят, что эта проблема рекурсивно не разрешима в том смысле, что не

существует алгоритма, который для каждой Tm и каждой конфигурации определял бы, остановится ли машина когда-нибудь. Это совсем не значит, что мы не можем определить, остановится ли конкретная Tm в конкретной ситуации.

При описании универсальной машины Тьюринга мы имели кодирование для любой Tm с ленточными символами 0, 1 и B.

 

Кодированием была цепочка из

{0, 1, c, L, R}*

Мы можем перенумеровать все такие цепочки, перечисляя их в порядке возрастания длины. Цепочки одинаковой длины упорядочиваются в соответствии со значением строки по основанию 5. Предполагается, что эти 5 символов играют роль целых 0, 1, 2, 3, 4 в каком-нибудь порядке. Аналогичным образом цепочки из множества {0, 1}* могут быть тоже упорядочены. Первыми цепочками являются ε, 0, 1, 00, 01, 10, 11, 000, 001, ... Таким образом, имеет смысл говорить об i-й цепочке в множестве {0, 1}* Если мы предположим, что каждая цепочка из множества {0, 1, c, L, R}* является машиной Тьюринга (некоторые цепочки будут образованы неправильно – они рассматриваются как Tm без каких-нибудь движений), то также имеет смысл говорить о j-й машине Тьюринга, т.е. о машине, представленной j-й цепочкой из множества {0, 1, c, L, R}*

Рассмотрим язык = { | не принимается }. Ясно, что язык не мог бы приниматься никакой . Если бы это не было так, то существовала бы некоторая машина Тьюринга, скажем , которая бы принимала язык . Возьмем, цепочку . Если ∈, то по определению языка не принимается машиной . С другой стороны, машина распознает язык , стало быть принимает ∈.

Наше допущение привело к противоречию. Если ∉, то не принимается машиной , но тогда по определению языка принимается машиной . Опять противоречие. Остается признать, что язык не принимается никакой Tm.

Предположим, что мы имели бы алгоритм (т.е. машину Тьюринга, которая всегда останавливается) для определения, остановится ли когда-нибудь машина Тьюринга в данной конфигурации. Обозначим этот алгоритм T0. Тогда мы могли бы построить машину Тьюринга T, которая принимает язык , а это противоречило бы только что установленному факту. Машина T действовала бы следующим образом:

1. Пусть x∈ на ее входе. Прежде всего, она перечисляет предложения x1, x2, ... до тех пор, пока не обнаружит, что некоторое . Таким образом определяет, что x является i-м предложением в этом перечислении.
2. Затем генерирует код машины Тьюринга .
3. Управление теперь передается машине T0, которая может определить, останавливается     с входной цепочкой или нет.
4. Если установлено, что не останавливается с входной цепочкой (т.е. не принимает ), то машина T останавливается и принимает.
5. Если же установлено, что останавливается с входной цепочкой , то управление передается универсальной машине Тьюринга, которая моделирует машину Ti с входной цепочкой .
6. Поскольку, как было выяснено на предыдущем шаге, останавливается с входной цепочкой , то универсальная машина Тьюринга остановится и определит, принимает машина цепочку или нет. В любом случае останавливается, принимая в случае, когда цепочку не принимает, и наоборот, отвергая ее, если TmTi ее принимает.

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

Теорема 1.1. Не существует алгоритма (машины Тьюринга, которая гарантированно останавливается) для определения, остановится ли в конце концов произвольная машина Тьюринга, начиная в произвольно заданной конфигурации. [3]

Доказательство вытекает из подходящей формализации выше приведенного рассуждения. Для многих проблем не существует разрешающего алгоритма, в частности и для решения некоторых проблем, касающихся теории языков.

Если в машине Тьюринга T, которая кодируется, δ(i, a) = ( j, b, D), то подблок, соответствующий состоянию i и входному символу a, будет содержать j единиц, за которыми следует символ D ∈{L, R}, а за ним               b ∈    {0, 1}. Если δ(i, a) не определено, то соответствующий подблок будет содержать единственный нуль. Так же надо выделить состояния, при которых машина остановится: терминальные (допускающие) состояния. Иначе она будет вечно бегать по бесконечной ленте. Машина Тьюринга не решает проблему остановки. Даны описание алгоритма и его начальные входные данные, требуется определить, сможет ли выполнение алгоритма с этими данными завершиться когда-либо. Альтернативой этому является то, что он работает всё время без остановки. Назовем Анализатором гипотетический алгоритм, который получает на вход пару натуральных чисел(N,X), и

• останавливается и возвращает 1, если другой алгоритм с номером N не останавливается, получив на вход X;
• не останавливается в противном случае (если другой алгоритм с номером N останавливается, получив на вход X);

Если применить алгоритм к самому себе, то он не сможет работать, потому что должен будет остановиться тогда, когда он сам не останавливается, и не останавливаться в том случае, если он сам остановится.

 

3.2.  Проблема вычислимости машины  Тьюринга

 

Проблема вычислимости заключается в том, что есть такие алгоритмы, результат действия которых мы не можем вычислить. Примером такого алгоритма является бесконечная снежинка Коха:[5]

 

 

 

 

1. Мы рисуем треугольник;

2. На следующем шаге на каждой его стороне мы рисуем еще по треугольнику;

3. На следующем – на каждом из полученных треугольников еще по треугольнику;

4. И так на каждом последующем шаге мы рисуем по треугольнику на каждом из треугольников, полученных на предыдущем шаге (вот так, как это показано на картинке);

 

Проблема: если мы поставим рядом с такой снежинкой точку, то мы не можем определить, попадет ли эта точка в снежинку, когда та будет разрастаться, на определенном шаге реализации этого алгоритма. Если точка не попадет в снежинку на 55-м шаге, мы не знаем, случится ли это на 70-м или на 125-м шаге – алгоритм бесконечен.

 

4. Множество граничных конфигураций. Достаточные условия разрешимости проблемы остановки.

Пусть в момент t некоторого вычисления на машине Z головка вышла за конец слова или . Предположим также, что после t тактов работы головка находится в состоянии , а на участке ленты, посещенном ею до момента t, записано слово . Общий видконфигурации в момент tвычисления изображен на рис. 3: а) в случае выхода головки за левый конец, б) в случае выхода за правый конец слова. На заштрихованном участке ленты (рис. 3) записана часть входного слова, которая до момента tне просматривалась головкой. Заметим, что этот участок может быть и пуст. В случае а) конфигурацию , а в случае б) – назовем граничной.

Таким образом, любой выход головки за конец слова определяет некоторую граничную конфигурацию.

 

                                        рис. 3

Обозначим множество всех граничных конфигураций машины Z. Так же, т. е. , будем обозначать и множество вычислений, начинающихся с граничных конфигураций.

Замечание относительно . Из данного выше определения граничной конфигурации следует, что конфигурация если существует вычисление машиной Z на слове длины п со следующими свойствами: а) в некоторый момент t головка в состоянии выходит за левый (правый) конец слова, посетив до этого каждую из ячеек ни разу не посетив б) в момент t на участке записано слово Отсюда вытекает существование алгоритма, позволяющего для любой конфигурации вида решить вопрос о ее принадлежности . Для этого надо просмотреть всевозможные вычисления на словах длины я, отбросить те из них, в которых головка не выходит за конец слова, а затем проверить, существует ли среди остальных вычисление со свойствами а) и б). Таким образом, – разрешимое множество.

Рассмотрим множество вычислений из на словах длины п. Отбросим те из бесконечных вычислений рассматриваемого множества, в которых головка ни разу не выходит левее ,если она начала работать в , или правее , если она начала работать в . Для остальных вычислений обозначим максимальное число тактов от начала работы до ближайшего из двух возможных событий: «вычисление закончилось» и «головка вышла за конец участка , отличный от того, на котором она начала работать».

Для всех конечных вычислений из на словах длины п обозначим через максимальное число выходов головки за левый конец слова, следующих сразу после выхода за правый, и наоборот. Примем такое соглашение. Будем считать, что на нулевом такте работы головка вышла за правый конец слова, если в момент она находится в ячейке , и за левый конец, если в момент она находится в ячейке .

Лемма 1. Если функция вычислима, то существует алгоритм, позволяющий для любой начальной конфигурации и любого определить, содержит ли соответствующее вычисление этап , а если вычисление содержит  этапов, то заканчивается ли оно.[7]

 

Доказательство. Пусть нам известно, что некоторое вычисление содержит . Тогда можно определить машинную конфигурацию в момент t первого посещения головкой ячейки . Для определенности положим, что на этапе головка уходит из налево. После этого оказывается возможным ответить на вопрос, существует ли , а если не существует, то конечный ли . После момента t должно произойти одно из четырех событий: 1 – 2) головка остается на и останавливается или работает бесконечно; 3 – 4) головка впервые покидает выходя правее или левее . В случаях 1) – 3) ответ очевиден. В четвертом случае для ответа на поставленный вопрос вычисляем длину участка и просматриваем еще тактов вычисления. Если за это время головка остановилась, то – последний этап, а если она вышла правее , то существует . Если же головка не остановилась и не вышла правее , этап Ет – бесконечный. В случае, когда на этапе Ет головка из уходит направо, рассуждение дословно повторяет предыдущее с той лишь разницей, что вместо рассматривается

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

Теорема 1. Если функции и вычислимы, то проблема остановки разрешима для Z.[7]

Доказательство. Сделаем одно предварительное замечание. По одному из свойств разбиений вычислений на этапы для просмотра входного слова длины п требуется не более 2п –1 этапов, а значит, участок ленты, ограниченный ячейками и , содержит , в себе или совпадает с ним. Таким образом, к моменту начала работы головки на концами слова являются ячейки и . На этапе головка уходит с участка, ограниченного и т.е. осуществляется граничная конфигурация. Перейдем непосредственно к доказательству теоремы. Рассмотрим произвольное вычисление на слове длины п. Из леммы 1 вытекает, что существует алгоритм, позволяющий определить, содержит ли это вычисление этап , а если оно содержит меньшее число этапов, то заканчивается ли оно. Для тех вычислений, которые содержат , определяем конфигурацию в момент t ухода головки с участка, ограниченного ячейками и . По сделанному выше замечанию, эта конфигурация принадлежит . Вычисляем длину участка ленты, просмотренного головкой за t тактов работы, и определяем, содержит ли вычисление еще хотя бы этапов, а в случае, когда оно после содержит не более этапов, заканчивается ли оно. Заметим следующее. Если конечное вычисление на слове длины начинается с граничной конфигурации, то число полных этапов после выхода головки за конец слова, противоположный тому, на котором она начала работать, не превосходит . Поэтому, если рассматриваемое вычисление после содержит более этапов, оно бесконечно. Теорема доказана.

 

5. Машины Тьюринга с двумя символами и не более чем 
   тремя состояниями

 

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

Чтобы Z была О-машиной, должны выполняться три условия: 1, 2 и За (3б).

1. Множество – выметаний 1 –1 – –регулярно.
2. Для любого входного символа х почти все  – выметания имеют на х продолжения одного типа.