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

Имеет место быть следующая теорема: не существует алгоритма (машины Тьюринга), позволяющего по описанию произвольного алгоритма и его исходных данных (и алгоритм и данные заданы символами на ленте машины Тьюринга) определить, останавливается ли этот алгоритм на этих данных или работает бесконечно. 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);

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

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

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

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

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