Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 41
Текст из файла (страница 41)
в момент 1.= [о((К(г) =г). Поэтому р,=Ко(Г,), а,=Ко(1*) и [(т[3о-[-, + ао) =тКо(1п О, 1, ао, 5о) +К~(Г„О, 1 ао, [3о). Если придать 1 стандартный вид [(х), учитывая при этом, что [3о=[х/т), аог г(по, х), н выписать все аргументы функций К, получаем: 1(х) тК Ф (К 6, О, 1, г (т, х), [х(т[) = г), О ' '(т х) [х'т[)+ Ко(Ф(К а, О, 1 г(т х) [х/т[) =*г) О, 1, г (т, к), [х~т[) (5 И) (т, г — константы, зависящие от конкретной машины), откуда непосредственно видно, что функция ), описываю- щая результат работы машины Тьюринга, построена из примитивно-рекурсивных функций с помощью оператора [о и, следовательно, является частично-рекурсивной.
П Из теорем 5.6, 5.7 и соотношения (5.13) следует теоре- ма Клннн о нормальной форме — теорема 5.8. . Теорема 5.8. Любая частично-рекурсивная функция )(х) представима в виде 1(х) = Р (пу [б (х, у) = 0[), где Р и Π— примитивно-рекурсивные функции. П Таким образом, класс частично-рекурсивных функций оказался эквивалентным классу функций, вычисляемых машинами Тьюринга. Эквивалентность этих классов, в ос- нове построения которых лежали совершенно. различные подходы, косвенным образом подтверждает справедли- вость тезисов Черча н Тьюринга и позволяет объединить их в один тезис Черча — Тьюринга.
Кроме того, она дает возможность формулировать основные результаты теории алгоритмов в более общем виде. Об этом — в в 5А. 200 вм. ВЫЧИСЛИМОСТЬ И РАЗРЕШИМОСТЬ Итак, всякий алгоритм, описанный в терминах частично-рекурсивных функций, можно реализовать машиной Тьюринга, и наоборот. Отсюда следует, что любые утверждения о существовании или несуществовании алгоритмов, сделанные в одной из этих теорий, верны н в другой) В сочетании с тезисом Черча — Тьюринга это означает, что такие утверждения можно формулировать для алгоритмов вообще, не фиксируя конкретную модель и используя результаты обеих теорий, Таким образом, возможно изложение теории алгоритмов, инвариантное по отношению к способу формализации понятия «алгоритм», — при любой форма. лнзации основные свойства алгоритмов остаются теми же самыми'.
Основные понятия такой инвариантной теории (будем называть ее обшей теорией алгоритмов) — это алгоритм (рекурсивное описание функции, система команд машины Тьюринга или описание в какой-либо другой модели; считается, что выбрана какая-то модель, но какая именно —. неважно) и вычислимая функции Функция называ. ется вычислимой, если существует вычисляюшнй ее алгоритм. При этом несушественно, числовая функция это или нет, Термин «обшерекурсивная функция», употребленный в инварпантном смысле, является синонимом термина «всюду определенная вычислимая функция».
Эквивалентность утверждений «функция ) вычислима» и «сушествует алгоритм, вычисляющий функциго )» иногда приводит к смешению понятий алгоритма и вычислимой функции; в частности, говоря о рекурсивной функции, часто имеют в виду ее конкретное рекурсивное описание. В действительности же различие между вычнслимой функцией и алгоритмом — это различие между функцией и способом ее задания. Без соблюдения этих различий невозможна корректная интерпретация некоторых важных результатов теории алгоритмов. В то же время традиция изложения теории алгоритмов позволяет не различать понятия алгоритма и функции в тех случаях, когда это не приводит к путанице. В этом параграфе резюмируются уже прлученные и формулируются некоторые новые понятия и результаты теории алгоритмов именно в их инвариантном виде.
Они верны для ' Это верно, когда речь идет о существованнн нлн несуществовании алгорнтмов. Характеристики качестве алгоритмов (нх сложносгн в том нлн ином смысле), вообще говоря, ненквврнвнтны но отношению к выбранной формвлнзвцнн. 201 любой формализации понятия «алгоритм», что не мешает использовать в каждом конкретном рассуждении конкретную алгоритмическую модель, наиболее подходящую для данного случая. Отступление бд. Для читателя этой книги, который в конечном счете интересуется прикладной стороной излагаемых здесь теорий, важно отметить следующее.
Ввиду инвариантности основных результатов общей теории алгоритмов прикладное значение ее результатов никак не связано с тем, насколько близки к практике используемые в ней теоретические модели алгоритмов. Машины Тьюринга весьма далеки от современных ЭВМ, а рекурсивные функции — от языков программиро. ваняя прежде всего нз-за предельной скромности используемых средств. Однако именно скромность средств, во-первых, делает этн модели чрезвычайно удобным языком доказательств, а во-вторых, позволяет понять, без чего обойтись нельзя, а без чего можно и какой ценой, т, е, отличать удобства от принципиальных возможностей. Иначе говоря, прикладное значение рассматриваемых здесь моделей заключается в том, что с их помощью удобно строить теорию, верную для любых ' алгоритмических моделей, в том числе н для сколь угодно близких к практике. Нумерация алгоритмов. Множество всех алгоритмов счетно. Этот факт уже отмечался в 5 5.3, однако он ясен и без обращения к конкретным алгоритмическим моделям: ведь любой алгоритм можно задать конечным описанием (например, в алфавите знаков, используемых при наборе математических книг), а множество всех конечных слов в фиксированном алфавите счетно.
Счетность множества алгоритмов означает наличие взаимно однозначного соответствия между алгоритмами н числами натурального ряда, т.е. функции типа ~р: гу'-»АГ, взаимно однозначно отображающей в слова в алфавите А), выбранном для описания алгоритмов, числа натурального ряда. Такая функция гр(п) =А называется нумерацией алгоритмов, а ее аргумент п — номером алгоритма А прн нумерации гр. Из взаим- ' ной однозначности отображения ~р следует существование обратной функции ~р-г(А„) =и, восстанавливающей по опи' санию алгоритма А, его номер и. Более общие определения нумераций см. в [401. Фактически мы уже построили одну нумерацию: алфавит А( и способ представления алгоритмов в этом алфавите выбраны при построении универсальной машины У, а функ ция гр определяется методом числового кодирования конфигураций, использованным при доказательстве теоремы 202 5.7.
Правда, при таком определении нумерация у некоторые натуральные числа декодирует в слова, не являющиеся записью никакого алгоритма. Эти числа можно считать номерами нигде не определенных алгоритмов, а соответствующую универсальную машину определить так, чтобы на этих словах она зацикливалась.
Приведенный пример показывает, что существуют вычислимые нумерации. Очевидно, что различных нумераций много; мы не будем заниматься их особенностями, а договоримся, что зафиксирована какая-та вычислимая нумерация. Основной интерес для приложений теории алгоритмов представляют инвариантные свойства номеров алгоритмов, не зависящие от особенностей выбранной нумерации. Нумерация всех алгоритмов является одновременно и нумерацией всех вычислимых функций в следующем смысле: номер функции ) — это номер некоторого алгоритма, вычисляющего ~.
В любой нумерации всякая функция будет иметь бесконечное множество различных номеров. Это ясно из того, что к любой машине Тьюринга можно добавить любое количество недостижимых состояний (т, е. состояний, не встречающихся в правых частях команд); все полученные машины имеют различные номера, но вычисляют одну и ту же функцию. Говоря о нумерации, будем считать, что она выбрана так, что Аэ и вычисляемая им функция )0 нигде не определены. Существование нумераций позволяет работать с алто. ритмами как с числами. Это особенно удобно при исследовании алгоритмов над алгоритмами. Такие алгоритмы уже рассматривались при построении универсальной машины Тьюринга и в связи с проблемой остановки. Полученные результаты теперь можно сформулировать в ипвариантном виде. Теорема 5.9.
Существует универсальный алгоритм Б(х, у), такой, что для любого алгоритма А с номером ~р-'(А) Ь(~р '(Л), у) =Л (у); в других обозначениях 0(х, у) =А. (д). Для коикре1ной нумерации ~р* эта теорема доказана в В '5.2 построением универсальной машины Тьюринга. Для любой другой вычнслнмой нумерации ~р можно выбрать одни из двух путей: а) построить новый универсальный алгоритм, работающий непосредственно с номерами, порождаемыми ~р; б) построить алгоритм перевода (взаимно однозначного отображения) у в ~р~, П По существу вычислимая нумерация служит языком программирования для универсального алгоритма.
Путь «а» — это построение новой машины для каждого нового языка, путь «б» — построение нового транслятора для прежней машины. Теорема 5.4'. Не существует алгоритма, который по номеру х любого алгоритма и исходным данным у определял бы, остановится алгоритм при этих данных или нет; иначе говоря,(ие существует алгоритма В(х, у), такого, что для любого алгоритма А (с номером р '(А) =х) 11, если А„(у) определен; В(х,у)=~ ' (О, если А„(у) не определен, Эта теорема — переформулировка в инвариантном виде теоремы 5.4 о неразрешимости проблемы остановки.
(:) Один частный случай проблемы остановки имеет вполне самостоятельную интерпретацию. При доказательстве теоремы 5.4 была рассмотрена машина Ть которая решала проблему остановки для машины Т в случае, когда на ленте машины Т написана ее собственная система команд. Такая проблема называется проблемой самопримепимости машин Тьюринга, Было показано, что такая машина невозможна. Б инвариантном виде соответствующее утверждение формулируется так. Теорема 5АО. Проблема самоприменимости алгоритмов алгоритмически неразрешима: не существует алгоритма В1(х), такого, что для любого алгоритма А, В (х) 1 если 4 (х) определен; (5 14) (О, если А„(х) не определен.П Отметим, что самоприменимость — частный случай проблемы остановки, и именно поэтому теорему 5.10 нельзя получить из теоремы 5.4' простой подстановкой х вместо у в В(х, у): частный случай алгоритм и чески неразрешимой проблемы может оказаться и разрешимым.
Теоремы 5.4' и 5.10 являются мощным средством для доказательства различных неразрешимостей, Решение задачи перечисления всех алгоритмов (и, в частности, всех рекурсивных функций) достаточно ясно, по крайней мере в принципе. Могло бы показаться, что перечисление примитивно-рекурсивных или общерекур сивных функций окажется более легким делом. Однако это не так. 204 Теорема 5.11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
