Рассмотрим машину Тьюринга U, которая обладает следующим свойством: если записать на ее ленте программу произвольной машины Тьюринга М и произвольное слово во внешнем алфавите этой машины, она переработает это слово так же, как переработала бы его машина М. Такую машину называют универсальной. Доказано, что машина U существует.
§ 2. Функция, вычислимая по Тьюрингу
Пусть f - функция, отображающая множество векторов Vисх над Аисх в множество векторов Vрез над Арез. Машина Тьюринга правильно вычисляет функцию f, если:
1. для любых v и w, таких, что f(v)=w, выполняется: q1 v 
w q0 ;
2. для любого v, такого, что f(v) не определена, машина Т, запущенная в начальной конфигурации q1 v, работает бесконечно.
Если для f существует машина Т, которая ее правильно вычисляет, функция f называется правильно вычислимой по Тьюрингу.
С другой стороны, всякой правильно вычисляющей МТ, т. е. машине, которая, начав со стандартной начальной конфигурации q1 a, может остановиться только в стандартной заключительной ситуации bq0, можно поставить в соответствие вычисляемую ею функцию.
Определения, связанные с вычислением функций, заданных на словарных векторах, даны с явным “запасом общности” и имеют в виду переработку нечисловых объектов. В дальнейшем будут рассматриваться числовые функции: f: Nk ® N или f: Nk ® B = {0, 1} (k Î N).
§ 3. Тезис Чёрча — Тьюринга
Построение машин Тьюринга для вычисления конкретных функций - это, в сущности, программирование. Правда, в отличие от программы для ЭВМ программа МТ считается частью самой машины. Главное же отличие МТ от реальных ЭВМ (если отвлечься от ограниченности объема памяти и времени работы последних) - крайняя простота элементарных шагов; эта простота позволяет легко строить “трансляторы” с языков реальных машин на язык машины Тьюринга. Хотя Тьюринг придумал свои машины за несколько лет до появления первых ЭВМ, машины Тьюринга вполне можно считать общей абстрактной схемой вычислительной машины с программным управлением.
Справедливо утверждение, называемое обычно тезисом Чёрча-Тьюринга: для всякой функции, которую можно каким-либо способом вычислить, можно построить вычисляющую ее машину Тьюринга.
Тезис Чёрча - Тьюринга не является математической теоремой или аксиомой, потому что участвующее в его формулировке понятие “каким-либо способом вычислить” не есть точное математическое понятие. По своему статусу этот тезис похож скорее на законы физики, представляющие собой обычно утверждения о том, что или иное явление природы описывается некоторой математической конструкцией (например, ДУ) - с той разницей, что речь идет не о явлении природы, а об одном из видов человеческой деятельности - вычислении.
Тезисом Чёрча - Тьюринга часто пользуются для сокращения доказательств теорем теории алгоритмов: если по ходу рассуждения нужно установить, что некоторая функция вычислима по Тьюрингу, довольствуются указанием “неформальной” вычислительной процедуры и построение машины Тьюринга опускают.
§ 4. Неразрешимые алгоритмические проблемы
Задачи о нахождении алгоритмов для вычисления функций (в частности, предикатов) называются алгоритмическими проблемами; если алгоритма для вычисления той или иной функции не существует, то соответствующая алгоритмическая проблема неразрешима.
Пример. Задача решения диофантовых уравнений: найти алгоритм, позволяющий для любого уравнения вида f(x1, x2, ..., xn)=0, где f(x1, x2, ..., xn) - многочлен с целыми коэффициентами от неизвестных x1, x2, ..., xn (n Î N), узнать, имеет ли оно целочисленные решения.
Для многих частных типов диофантовых уравнений были найдены алгоритмы, позволяющие их решать.
Познакомимся с примерами невычислимых предикатов, или, иначе, нераспознаваемых свойств и отношений - т. е. таких свойств и отношений, для которых не существует распознающих их алгоритмов.
В числе требований, предъявляемых к алгоритмам, упоминалось требование результативности. Наиболее радикальной формулировкой здесь было бы требование, чтобы по любому алгоритму А и данным a можно было определить, приведет ли работа А при исходных данных a к результату или нет. Иначе говоря, нужно построить предикат В, такой, что В(А, a)=И, если А(a) дает результат, и В(А, a)=Л в противном случае.
В силу Тезиса Тьюринга эту задачу можно сформулировать как задачу о построении машины Тьюринга: построить машину М0, такую, что для любой машины Тьюринга М и любых исходных данных a для машины М выполняются условия:
М0 возвращает «И», если машина М(a) останавливается, и
М0 возвращает «Л», если машина М(a) не останавливается.
Эта задача называется проблемой остановки.
Теорема 1. Не существует машины Тьюринга М0, решающей проблему остановки для произвольной машины
Допустим, что машина М0 существует. С помощью этой машины построим другую машину М1, которая действует следующим образом:
М1 работает вечно, если машина М(a) останавливается, и (*)
М1 возвращает «Л», если машина М(a) не останавливается (как и М0). (**)
Пусть q0 - заключительное состояние машины М0,
q’ и q” не являются состоянием машины М0,
q” - заключительное состояние машины М1.
Чтобы получить машину М1, просто добавим к М0 еще три команды:
(1) q0 ...® ... Е q’ %перейти в сост. q’
(2) q’И ® И E q’ %если И, то попадаем в бесконечный цикл:
(3) q’Л ® Л L q” %если Л, то сдвинуться влево и перейти в заключительное сост.
Попробуем применить М1 к себе самой. Для этого подставим М1 в (*) и (**) вместо М:
М1 работает вечно, если машина М1(a) останавливается, и
М1 возвращает «Л», если машина М1(a) не останавливается.
Таким образом, мы получили, что машина М1 одновременно и останавливается, и работает вечно, чего быть не может.
Неразрешимость проблемы остановки можно интерпретировать как отсутствие общего алгоритма для отладки программ, т. е. алгоритма, который по тексту любой программы и данным для нее определял бы, зациклится ли программа на этих данных или нет. Такая интерпретация не противоречит тому эмпирическому факту, что большинство программ, в конце концов, удается отладить, т. е. установить наличие зацикливания, найти его причину и устранить ее.
Две машины Тьюринга с одинаковым алфавитом Аисх называются эквивалентными, если они вычисляют одну и ту же функцию.
Пример 1*. Эквивалентными являются все машины МÆ с одинаковым алфавитом Аисх, бесконечно работающие на любом векторе Vисх над Аисх, т. к. все они вычисляют одну и ту же нигде не определенную (пустую) функцию.
Пример 2. Если машина Тьюринга М содержит команды qi aj ® aj’ E qi’, qi’ aj’ ® aj’’D qi’’, то, заменив эти две команды командой qi aj ® aj’’D qi’’, получим машину М’, эквивалентную машине М. Путем таких преобразований можно в машине М убрать все команды, содержащие Е, для случая, когда qi’ - не заключительное состояние; при этом может сократиться число состояний (некоторые qi’ не войдут в правые части новых команд и станут недостижимыми из q1). Если qi’ - заключительное состояние, то, введя новое заключительное состояние qn+1 и заменив команду qi aj ® aj’ E qi’ на m+1 команду
qi aj ® aj’ R qi’, qi’a1 ® a1 L qn+1 ,..., qi’am ® am L qn+1,...,
(m - число букв в А), получим машину, также эквивалентную М.
Значит, для любой машины Тьюринга существует ~-ая ей машина, не содержащая в командах Е; поэтому можно рассматривать машины, головки которых на каждом шаге движутся.
Свойство машин Тьюринга называется инвариантным, если любые две эквивалентные машины либо обе обладают этим свойством, либо обе не обладают.
Свойство машин Тьюринга называется нетривиальным, если существуют как машины, обладающие этим свойством, так и не обладающие.
Теорема 2 (теорема Райса [Rice 1953]). Ни для какого нетривиального инвариантного свойства машин Тьюринга не существует алгоритма, позволяющего для любой машины Тьюринга узнать, обладает ли она этим свойством.
Пусть a - произвольное нетривиальное инвариантное свойство машин Тьюринга. Рассмотрим машины МÆ, не применимые ни к какому слову; все они, очевидно, эквивалентны между собой (см. пример*). Ввиду инвариантности свойства a оно либо выполняется для всех таких машин, либо не выполняется ни для одной из них. Пусть для определенности имеет место второй факт (в противном случае вместо свойства a следует взять его отрицание).
Пусть, кроме того, Мa - некоторая машина, обладающая свойством a (такая машина существует ввиду нетривиальности a).
Рассмотрим теперь произвольную машину Тьюринга М. По ней без труда можно построить другую машину М’, работающую следующим образом:
... x ... |
... x*y ... |
... x*M(y) ... |
I этап. Если в начальной ситуации на ее ленте записано слово х, она ставит справа от него разделительный знак, за ним записывает слово y=Vисх (компоненты Vисх принадлежат алфавиту Аисх машины М), и далее, “не трогая” х, перерабатывает y по программе машины М.
Этот этап вычислений успешно закончится Û, когда М останавливается.
... x*M(y) ... |
... x... |
... Ma(x) ... |
II этап. Все, что правее разделительного знака, а также он сам, стирается, а затем оставшееся слово х перерабатывается по программе машины Мa.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 |
Основные порталы (построено редакторами)