Игошин Математическая логика и теория алгоритмов (1019110), страница 89

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 89)

Таким образом, нормальные алгоритмы примеров 34.6 и 34.7 показывают, что функции Ях) = х+ 1 и дз(х) нормально вычислимы. Причем соответствующие нормальные алгоритмы удалось построить в том же самом алфавите А, на словах которого были заданы рассматривавшиеся функции, т.е. расширять алфавит не потребовалось (В = А). Следующий пример демонстрирует нормальный алгоритм в расширенном алфавите, вычисляющий дан.- ную функцию. Пример 34.9. Построим нормальный алгоритм лля вычисления функции 3(х) = х+ 1 не в одноичной системе (как сделано в при- 357 мере 34.6), а в десятичной. В качестве алфавита возьмем перечень арабских цифр А = (О, 1, 2, 3, 4, 5, 6, 7, 8, 9), а нормальный алгоритм будем строить в его расширении В = А () (а, Ь).

Вот схема этого нормального алгоритма (читается по столбцам): ОЬ-+. 1 !Ь-». 2 2Ь-». 3 ЗЬ вЂ” ». 4 4Ь-+. 5 5Ь-». 6 6Ь-+. 7 7Ь-+. 8 ЗЬ-». 9 9Ь-» ЬО Ь-». 1 аО-+ Оа а1-+ 1а а2-+ 2а аЗ » За а4-+ 4а а5 — > 5а аб-» ба а7 — » 7а а8 — > За а9-+ 9а Оа-+ОЬ !а-+!Ь 2а-+ 2Ь За-+ ЗЬ 4а-+4Ь 5а » 5Ь ба»6Ь 7а — > 7Ь 8а — » ЗЬ 9а — > 9Ь Л -» а. Попытаемся применить алгоритм к пустому слову Л.

Нетрудно понять, что на каждом шаге должна будет применяться самая последняя формула данной схемы. Получается бесконечный процесс: 358 Л =» а =» аа =» ааа ~ аааа ~... Это означает, что к пустому слову данный алгоритм не применим. Если применить теперь алгоритм к слову 499, получим следующую последовательность слов: 499 =» а499 (применена последняя формула) ~ 4а99 (формула из середины второго столбца) ~ =» 49а9 =» 499Ь (дважды применена формула из конца второго столбца) ~ 499Ь (предпоследняя формула) =» 49ЬО =» 4ЬОО (дважды применена предпоследняя формула первого столбца) =» 500 (применена формула из середины первого столбца). Таким образом, слово 499 перерабатывается данным нормальным алгоритмом в слово 500. Предлагается проверить, что 328 =» =» 329, 789 =» 790. В рассмотренном примере нормальный алгоритм построен в алфавите В, являющемся существенным расширением алфавита А (т.е.

А ~ В и А и В), но данный алгоритм слова в алфавите А перерабатывает снова в слова в алфавите А. В таком случае говорят, что алгоритм задан над алфавитом А. Создатель теории нормальных алгоритмов советский математик А.А. Марков выдвинул гипотезу, получившую название «Принция нормализации Маркова». Согласно этому принципу, для нахозкдения значений функции, заданной в некотором алфавите, тогда и только тогда существует какой-нибудь алгоритм, когда функция нормально вычиелима. Сформулированный принцип, как и тезисы Тьюринга и Черча, носит внематематический характер и не может быть строго доказан.

Он вьивинут на основании математического и практического опыта. Все, что в предыдущих параграфах было сказано о тезисах Тьюринга и Черча, можно с полным правом отнести к принципу нормализации Маркова. Косвенным подтверждением этого принципа служат теоремы следующего пункта, устанавливающие эквивалентность и этой теории алгоритмов теориям машин Тьюринга и рекурсивных функций. Совпадение класса всех нормально вычислимых функщ1й с классом всех функций, вычислимых по Тьюриигу. Это совпадение будет означать, что понятие нормально вычислимой функции равносильно понятию функции, вычислимой по Тьюрингу, а вместе с ним и понятию частично рекурсивной функции. Теорелеа 34.10. Всякая функция, вычислимая по Тьюрингу, будет также и нормально вычислимой.

До казател ьств о. Пусть машина Тьюринга с внешним алфавитом А = (аы а„..., а ) и алфавитом внутренних состояний 0= (ды оь ..., а,) вычисляет некоторую функцию у, заданную и принимающую значения в множестве слов алфавита А (словарную функцию на А). Попытаемся представить программу этой машины Тьюринга в виде схемы некоторого нормального алгоритма. Для этого нужно каждую команду машины Тьюринга д,а; ь два;Х представить в виде совокупности марковских подстановок. Конфигурации, возникающие в машине Тьюринга в процессе ее работы, представляют собой слова в алфавите А 0 Ц.

Эти слова имеют вид: аь... аь9,аь г.. аь Нам понадобитсЯ Различать начало слова и его конец (или его левый и правый концы). Для этого к алфавиту А 0 Д добавим еще два символа (не входящие ни в А, ни в Ц): А 0 Д() (и, о). Эти символы будем ставить соответственно в начало и конец каждого машинного слова пк ии о. Пусть на данном шаге работы машины Тьюринга к машинному слову и~ предстоит применить команду д,а; ь дьатХ Это означает, что машинное слово и (а вместе с ним и слово иве) содержит подслово д,аь Посмотрим, какой совокупностью марковских подстановок можно заменить данную команду в каждом из следующих трех случаев: а) Х= С, т.е. команда имеет вид: д,а; — ь авар Ясно, что в этом случае следующее слово получается из слова иио с помощью подстановки д,а, — > дьан которую мы и будем считать соответствующей команде д,а; -+ дьа,; б) Х= Л, т.е.

команда имеет вид: д,а; — > 9~а,Л. Нетрудно понять, что в этом случае для получения из слова ии о следующего слова надо к слову иве применить ту подстановку из сово- купности 359 аоЧ~а; -+ аоаоа,; а,д,ао -+ ооа,а,; а,,а,„а; -о ооа„а,; ид,а; -о идоаоал которая применима к слову ии о. В частности, последняя подстановка применима только тогда, когда д, — самая левая буква в слове и, т.е. когда надо пристраивать ячейку слева; в) Х = П, т.е. команда имеет вид: о,а; — > аоа,П. В этом случае аналогично, чтобы получить из слова ийо следующее слово, нужно к слову иво применить ту из подстановок совокупности ,д,а;ао — > а,жоао' д аа, — > а,даа,; д„а;а -о а,доа; д,аоо -> атдоаоо которая применима к слову иво.

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

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

нормально вычислимая функция вычислима но Тьюрингу. Доказательство. В [8.6] (теорема 1, с. 246 — 249) фактически доказано, что всякая нормально вычислимая функция частично рекурсивна (см. также следствие 5.1! в 15.13], с. 248 — 249). Добавив сюда доказанное в предыдущем параграфе (следствие 33.20) утверждение о том, что всякая частично рекурсивная функция вычислима по Тьюрингу, мы и приходим к справедливости сформулированного утверждения о вычислимости по Тьюрингу всякой нормально вычислимой функции.

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

Другими словами, они описывают один и тот же класс функций, т.е. справедлива следующая теорема. Теорема 34.12. Следующие классы функций (заданных на натуральных числах и принимающих натуральные значение) совпадают: а) класс всех функций, вычислимых по Тьюрингу; б) класс всех частично рекурсивных функций; в) класс всех нормально вычислимых функций. Полезно уяснить смысл и значение этого важного результата.

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

В силу ее нормальной вычисли- мости она была бы алгоритмически вычислима в интуитивном понимании алгоритма, и предположение о ее нерекурсивности опровергало бы тезис Черча. Но классы Тьюринга, Черча и Маркова совпадают, и таких функций не существует.

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

Характеристики

Список файлов книги