Игошин Математическая логика и теория алгоритмов (1019110), страница 88
Текст из файла (страница 88)
Отсюда непосредственно видно, что функция ор(х), представляющая собой результат работы машины Тьюринга, построена из примитивно рекурсивных функций с помощью оператора минимизации Р и, следовательно, является частично рекурсивной. Этим и завершается доказательство того, что всякая вычислимая по Тьюрингу функция частично рекурсивна. П Соединив вместе следствие 33.20 и теорему 33.21, приходим к следующей теореме. Теорема 33.лл.
Функция вычислима по Тьюрингу тогда и только тогда, когда она частично рекурсивна. СЗ Итог рассмотрений настоящего параграфа состоит в том, что мы дали некую альтернативную характеристику вычислимым по ТьюРингу функциям: это те и только те функции, которые частично Рекурсивны. Другими словами, класс функций, вычислимых по ТьюРингу, совпадает с классом частично рекурсивных функций. Со~падение этих двух классов вычислимых функций, в основе построения которых лежали совершенно разные подходы к формализации гг иош 353 понятия вычислимости функции, говорит о том, что эти подходы оказались весьма состоятельными, и служит косвенным подтверж дением того, что как тезис Тьюринга, так и тезис Черча не только не безосновательны, но и имеют все права на признание.
ф 34. Нормальные алгоритмы Маркова Теория нормальных алгоритмов (или алгорифмов, как называл их создатель теории) была разработана советским математиком А.А. Марковым (1903 — 1979) в конце ! 940-х — начале ! 950-х гг, ХХ в. Эти алгоритмы представляют собой некоторые правила по переработке слов в каком-либо алфавите, так что исходные данные и искомые результаты для алгоритмов являются словами в некотором алфавите. Марковские подстановки. Ал(бавитом (как и прежде) называется любое непустое множество. Его элементы называются буквами, а любые последовательности букв — словами в данном алфавите. Для удобства рассуждений допускаются пустые слова (они не имеют в своем составе ни одной буквы).
Пустое слово будем обозначать Л. Если А и  — два алфавита, причем А ~ В, то алфавит В называется расширением алфавита А. Слова будем обозначать латинскими буквами: Р, Д„А (или этими же буквами с индексами). Одно слово может быть составной частью другого слова. Тогда первое называется подсловом второго или вхождением во второе. Например, если А — алфавит русских букв, то можем рассмотреть такие слова: Р, = параграф, Р, = граф, Р, = ра.
Слово Р, является подсловом слова Рь а Р, — подсловом Р, и Р,, причем в Р, оно входит дважды. Особый интерес представляет первое вхождение. Определение 34.1. Марковской подстановкой называется операция над словами, задаваемая с помощью упорядоченной пары слов (Р, Д), состоящая в следующем. В заданном слове А находят первое вхождение слова Р (если таковое имеется) и, не изменяя остальных частей слова А, заменяют в нем это вхождение словом 0. Полученное слово называется результатом применения марковской подстановки (Р, 0) к слову А.
Если же первого вхождения Р в слово А нет (и, следовательно, вообще нет ни одного вхождения Р в А), то считается, что марковская подстановка (Р, О) неприменима к слову А. Частными случаями марковских подстановок являются подстановки с пустыми словами: (Л, 0), (Р, Л), (Л, Л). Пример 34.2. Примеры марковских подстановок рассмотрены в таблице, в каждой строке которой сначала дается преобразуемое слово, затем применяемая к нему марковская подстановка и„наконец, получающееся в результате слово: 354 Для обозначения марковской подстановки (Р, Д) используется запись Р— ь 9 Она называется формулой подстановки (Р, (г). Некоторые подстановки (Р, Д) будем называть заключительными (смысл названия станет ясен чуть позже).
Для обозначения таких подстановок будем использовать запись Р— ь . Д, называя ее формулой заключительной подстановки. Слово Р называется левой частью, а Д вЂ” правой частью в формуле подстановки. Нормальные алгоритмы и их применение к словам. Упорядоченный конечный список формул подстановок Р, -+(.)Я, Рз -+(.)9, Є— ь (.)О, в алфавите А называется схемой (или записью) нормального алгоритма в А. (Запись точки в скобках означает, что она может стоять в этом месте, а может отсутствовать.) Данная схема определяет (детерминирует) алгоритм преобразования слов, называемый нормальным алгоритмом Маркова.
Дадим его точное определение. Определение 34.3. Нормальным алгоритмом (Маркова) в алфавите А называется следующее правило построения последовательности е'; слов в алфавите А, исходя из данного слова Р'в этом алфавите. В качестве начального слова )гь последовательности беРется слово К Пусть для некоторого ( > 0 слово )г построено и процесс построения рассматриваемой последовательности еще не завершился.
Если при этом в схеме нормального алгоритма нет Формул, левые части которых входили бы в Рп то К,, полагают Равным еь и процесс построения последовательности считается завершившимся. Если же в схеме имеются формулы с левыми частЯми, входЯщими в )гп то в качестве К,, беРетсЯ РезУльтат маР- ховской подстановки правой части первой из таких формул вместо первого вхождения ее левой части в слово К; процесс построения последовательности считается завершившимся, если на дан"ом шаге была применена формула заключительной подстановки, и продолжающимся — в противном случае.
Если процесс пост- 355 роения упомянутой последовательности обрывается, то говорят, что рассматриваемый нормальный алгоритм применим к слову К Последний член И" последовательности называется резулыпатом применения нормального алгоритма к слову К Говорят, что нормальный алгоритм перерабатывает Ив Иг Последовательность )г будем записывать следующим образом: где )гь = е'и И = Иг. Мы определили понятие нормального алгоритма в алфавите А. Если же алгоритм задан в некотором расширении алфавита А, то говорят, что он есть нормальный алгоритм над А. Рассмотрим примеры нормальных алгоритмов. Пример 34.4. Пусть А = (а, Ь) — алфавит. Рассмотрим следующую схему нормального алгоритма в А: ( .л, Нетрудно понять, как работает определяемый этой схемой нормальный алгоритм. Всякое слово )гв алфавите А, содержащее хотя бы одно вхождение буквы а, он перерабатывает в слово, получающееся из )гвычеркиванием в нем самого левого (первого) вхождения буквы а.
Пустое слово он перерабатывает в пустое. (Алгоритм не применйм к таким словам, которые содержат только букву Ь.) Например, ааЬаЬ =ь аЬаЬ, аЬ =ь Ь„аа =ь а, ЬЬаЬ =ь ЬЬЬ, ЬаЬа ~ ЬЬа. Пример 34.5. Пусть А = (аы аь ..., а„) — алфавит. Рассмотрим схему аь — з Л, а, — ьЛ, а„-+ Л, Л -+. Л. Она определяет нормальный алгоритм, перерабатывающий всякое слово (в алфавите А) в пустое слово. Например, а,аза,а,аь =ь ~ а,аза,аз --ь ага|аз =ь азаз ~ аз ~ Л; аоазазяазаз ~ азагагазаз ~ =ь азазазаз =ь азазаз ~ агаз ~ аз =ь Л.
Нормально вычислимые функции и принцип нормализации Маркова. Как и машины Тьюринга, нормальные алгоритмы не производят собственно вычислений: они лишь производят преобразования слов, заменяя в них одни буквы другими по предписанным им правилам.
В свою очередь, мы предписываем им такие правила, результаты применения которых мы можем интерпретировать как вычисления. Рассмотрим два примера. 35б Пример 34.б. В алфавите А = (1) схема Л вЂ” ~ . ! определяет нормальный алгоритм, который к каждому слову в алфавите А = (1) (все такие слова суть следующие: Л, 1, 11„111, 1111, 11111 и т.д.) приписывает слева !.
Следовательно, алгоритм реализует (вычисляет) функцию 7(х) = х+ 1. Пример 34.7. Дана функция /1, если и делится на 3, '(Л, если и не делится на 3, где п — число единиц в слове 11...1. Рассмотрим нормальный алгоритм в алфавите А = (1) со следующей схемой: 111 — > Л, 11-+.Л, 1 — >.Л„ Л вЂ” >.1.
Этот алгоритм работаег по такому принципу: пока число букв 1 в слове не меньше 3, алгоритм последовательно стирает по три буквы. Если число букв меньше 3, но больше О, то оставшиеся буквы 1 или 11 стираются заключительно; если слово пусто, оно заключительно переводится в слово 1. Например: 1111111 ~ 1111 ~ 1 =ь Л; 111111111 =э 111111 =ь !11 =ь Л =ь 1. Таким образом, рассмотренный алгоритм реализует (или вычисляет) данную функцию. Сформулируем теперь точное определение такой вычислимости функций. Определение 34.8. Функциями; заданная на некотором множестве слов алфавита А, называется нормально вычислимой, если найлется такое расширение В ланного алфавита (А ~ В) и такой нормальный алгоритм в В, что каждое слово К (в алфавите А) из области определения функции 7" этот алгоритм перерабатывает в слово 7( !l).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
