Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 36
Текст из файла (страница 36)
Доказать тезис Тьюринга нельзя, поскольку само поня- тие алгоритма (или эффективной процедуры) является неточным. Это не теорема и не постулат математической теории, а утверждение, которое связывает теорию с теми объектами, для описания которых она создана.
По своему характеру тезис Тьюринга напоминает гипотезы физики об адекватности математических моделей физическим явлениям и процессам. Подтверждением тезиса Тьюринга является, во-первых, математическая практика, а во-вторых, то обстоятельство (уже отмечавшееся в конце $ 5.1), что описание алгоритма в терминах любой другой известной алгоритмической модели может быть сведено к его описанию в виде машины Тьюринга. Тезис Тьюринга позволяет, с одной стороны, заменить неточные утверждения о существовании эффективных процедур (алгоритмов) точными утверждениями о существовании машин Тьюринга, а с другой стороны, утверждении о несуществовании машин Тьюринга истолковывать как утверждения о несуществовании алгоритмов вообще. Однако не следует понимать тезис Тьюринга в том смысле, что вся теория алгоритмов может быть сведена к теории машин Тьюринга.
Например, в быстро развивающейся сейчас теории сложности алгоритмов (которая рассматривает сравнительную сложность алгоритмов по памяти, числу действий и т. д.) результаты, верные в рамках одной алгоритмической модели (скажем, о числе действий, необходимых для вычисления данной функции), могут оказаться неверными в другой модели. Проблема остановки. В числе общих требований, предьявляемых к алгоритмам (см.
$ б.1), упоминалось требование результативности. Наиболее радикальной формулировкой здесь было бы требование, чтобы по любому алгоритму А и данным а можно было определить, приведет ли работа А при исходных данных а к результату илн нет. Иначе гово. ря, нужно построить алгоритм В, такой, что В (А, м) =И, если А (и) дает результат, и В (А, м) =Л, если А (а) не дает результата. В силу тезиса Тьюринга эту задачу можно сформулировать как задачу о построении машины Тьюринга: построить машину Тм такую, что для любой машины Тьюринга Т и любых исходных данных а для машины Т Тэ (Е,, а) =И, если машина Т (и) останавливается, и Тэ (Хг, а) =Л, если машина Т (сс) не останавливается. Эта задача называется проблемой остановки, Ее форму лировка несколько напоминает задачу о построении универсальной машины и, в частности, также предполагает 176 выбор подходящего кодирования Хт и а в алфавите машины Т,.
Однако в данном случае никакое кодирование не приводит к успеху. Теорема 5.4. Не существует машины Тьюринга Т„решающей проблему остановки для произвольной машины Тьюринга Т. Предположим, что машина Т, существует. Для определенности будем считать, что маркером между Хт и и на ленте машины Т, служит . Построим машину Т>(Хт) = = То (Т„,„(Ет) ). Исходными данными машины Т, являются системы команд (точнее, их коды) любой машины Т, Запись Хт на ленте машина Т, преобразует в Хт Хт (машина Т,,„для чисел описана в примере 5.4, б), а затем работает как машина Т,.
Таким образом, Т, также решает проблему остановки для любой машины Т, но только в том случае, когда на ленте Т в качестве данных ат написана ее соботвенная система команд Ет. Иначе говоря, Т~(Ет) = =И, если машина Т(Хт) останавливается, и Т,(Хт) =Л, если машина Т(Е>) не останавливается. Пусть д„— заключительное состояние Ть Добавим к системе команд Т, одно состояние дь„+ь объявив его заключительным, и е> команд (т — число символов Т~) дыЛ- дь,+>Е, д .а>. дий для любого а; (в том числе И), кроме Л. Получим машину Т, (Хт), которая останавливается, если Т не останавливается, и не останавливается, если Т останавливается. Запишем теперь на ленте машины Т; ее собственную систему команд Х . Тогда Т; остановится, если она не останавлнвается, и не остановится, если опа останавливается. Очевидно, такая машина Т; невозможна.
Нопосколькуона получена из Т, вполне конструктивными, не вызыва>ощими сомнений средствами и при этом никак не связана с конкретной структурой машины Т,, остается заключить, что никакая машина Т„решающая проблему остановки, невозможна. П В силу тезиса Тьюринга невозможность построения ма. шины Тьюринга означает отсутствие алгоритма решения данной проблемы. Поэтому полученная теорема дает пер. вый пример алгоритмичееки неразрешимой проблемой а именно, алгоритмически неразрешимой оказывается проблема остановки для машин Тьюринга, т. е. проблема определения результативности алгоритмов. При истолковании утверждений, связанных с алгоритмической неразрешимостью, следует иметь в виду следующее важное обстоятельство. В таких утверждениях речь идет об отсутствии единого алгоритма, решающего данную проблему; при этом вовсе не исключается возможность решения этой проблемы в частных случаях, но различными средст.
вами для каждого случая, В частности, теорема 5.4 не исключает того, что для отдельных классов машин Тьюринга проблема остановки может быть решена'. Например, она решается для всех машин, приведенных в примерах 5.2— 5.8. Поэтому неразрешимость общей проблемы остановки вовсе не снимает необходимости доказывать оходимость предлагаемых алгоритмов, а лишь показывает, что поиск таких доказательств нельзя полностью автоматизировать. Неразрешимость проблемы остановки можно интерпретировать как несуществование общего алгоритма для отладки программ, точнее, алгоритма, который по тексту любой программы и данным для нее определял бы, зациклится ли программа на этих данных или нет.
Если учесть сделанное ранее замечание, такая интерпретация не противоречит тому эмпирическому факту, что большинство программ в конце концов удается отладить, т. е. установить наличие зацикливания, найти его прнчину и устранить ее. При этом решающую роль играют опыт и искусство про. граммиста. 6.3. РЕКУРСИВНЫЕ ФУНКЦИИ Введение. Всякий алгоритм однозначно ставит в соответствие исходным данным (в случае, если он определен на них) результат. Поэтому с каждым алгоритмом однозначно связана функция, которую он вычисляет.
Верно ли обратное: для всякой лн функции'существует вычисляющий ее алгоритм? Исследование проблемы остановка для машин Тью. ринга показывает, что нет: для предиката Р (Т, се), истинного, если и только если машина Тьюринга Т останавливается при исходных данных сс, алгоритма его вычисления не существует. Возникает вопрос: для каких функций алгоритмы существуют? Как описать такие алгоритмические, эффективно вычислимые функции? Исследование этих вопросов привело к созданию в ЗО-х годах нашего века теории рекурсивных функций. В.этой теории, как и вообще в теории алгоритмов, принят конструктивный, финитный подход (см.
э 5,1), основной чертой кото- ' Однако существуют конкретные машнны Тьюринга (например, любая уннверсальная машнна) с нераарешнмой проблемой остановян. 178 рого является то, что все множество исследуемых объектов (в данном случае функций) строится из конечного числа исходных объектов — базиса — с помощью простых операций, эффективная выполнимость которых достаточно очевидна. Операции над функциями в дальнейшем будем называть операторами. Примитивно-рекурсивные функции.
Определение и примеры. Займемся теперь конкретным выбором средств, с помощью которых будут строиться вычислимые функции. Очевидно, что к вычислимым функциям следует отнести все константы, т. е, О и все натуральные числа 1, 2... Однако в прямом включении бесконечного множества констант в базис нет необходимости. Достаточно одной константы 0 и функции следования 7(х) =х+1, которую иногда обозначают х', чтобы получить весь натуральнь1й ряд.
Кроме того, в базис включим семейство (1" ) функций тождества (нлн введенйя фиктивных переменных): 7" (х„..., х„) = х (т (а), Весьма мощным средством получения новых функций из уже имеющихся является суперпозиция, знакомая нам по гл 1 и 3, В ннх суперпозицией называлась любая подстановка функций в функции. Здесь ей для большей обозримости удобно придать стандартный вид. Оператором супераозиции 5" называется подстановка в функцию от т переменных т функций от а одних и тех же переменных.
Она дает новую функцию от а переменных. Например, для функций Ь(хь ..., хт), я~ (хо ..., хл), ..., Дта(хь ..., хл) 5"„(й,дм ...,у )=Ь(д,(х,...,х„),...,д (х,, ...,х„))= =)(х» ..., х„). Это определение порождает семейство операторов суперпозиции (5"), Благодаря функциям тождества стандартизация суперпозиции не уменьшает ее возможностей: любую подстановку функций в функции можно выразить че. рез 5'„' и 1" . Например, 1(хь хз) =И(д1(хь хт), у,(х,)) в стандартном виде запишется как 1(хь хз)=5т (Ь(хь хт), у~(хь хз), 52 (11 (хь х2), дз (х~), уз(х~))), где уз — любая функция от хь В свою очередь, используя подстановку и функции тождества, можно переставлять и отождествлять 179 аргументы в функции: 1(х„х„х„..., х„) =-1 (( (х„х,), 1, (х„х,), х„, ..., х„); 2 2 ~ (х„хм х,...,, х„) = ) (7, (хп х,), 11 (х„х,), х„..., х„). Таким образом, если заданы функции Р' н операторы Я", то можно считать заданными всевозможные операторы подстановки функций в функции, а также переименования, перестановки и отождествления переменных.
Еще одно семейство операторов, которое здесь понадобится, — это операторы примитивной рекурсии. Оператор примитивной рекурсии )1 определяет (и+ 1)-местную функцию 1 через и-местную функцию д и (и+2) -местную функцию й следующим образом: 1(х„..., х„, у + 1) = Ь (х„, х„, у, 1(х„..., . „, у)),) Пара равенств (5.2) называется схемой примитивной рекурсии. Тот факт, что функция 1 определена схемой (5.2), выражается равенством 1(хь ..., х„, у) =Р,(д, й).
В случае, когда п=О, т. е. определяемая функция 1 является одноместной, схема (5.2) принимает более простой вид: ) (0) = с; ) (у + 1) = й (у, ~ (у)), (5.3) где с — константа. Схемы (5.2) и (5.3) определяют 1 рекурсивно не только через другие функции д н й, но и через значения 1 в предшествующих точках: значение 1 в точке у+1 зависит от значениЯ 1 в точке У. ДлЯ вычислениЯ 1(хп ..., х„й) понадобится к+1 вычислений по схеме (5.2) — для у=О, 1,.„, й, Пример такого определения функции приводился в гл, 1 (для фуякцин и1); здесь оно будет рассь(отрено более подробно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
