Нормальные алгоритмы Маркова

↑

▷ Содержание

⇐ ПредыдущаяСтр 3 из 3

Теория нормальных алгоритмов (или алгорифмов, как называл их создатель теории) была разработана советским математиком А.А. Марковым (1903-1979) в конце 1940-х – начале 1950-х гг XX в. Эти алгоритмы представляют собой некоторые правила по переработке слов в каком-либо алфавите, так что исходные данные и искомые результаты для алгоритмов являются словами в некотором алфавите.

Марковские подстановки.Алфавитом (как и прежде) называется любое непустое множество. Его элементы называются буквами, а любые последовательности букв – словами в данном алфавите. Для удобства рассуждений допускаются пустые слова (они не имеют в своем составе ни одной буквы). Пустое слово будем обозначать L. Если А и В – два алфавита, причем А Ì В, то алфавит В называется расширением алфавита А.

Слова будем обозначать латинскими буквами: Р, Q, R (или этими же буквами с индексами). Одно слово может быть составной частью другого слова. Тогда первое называется подсловом второго или вхождением во второе. Например, если А – алфавит русских букв, то можем рассмотреть такие слова: Р₁ = параграф, Р₂ = граф, Р₃  = ра. Слово Р₂ является подсловом слова Р₁, а Р₃ — подсловом Р₁ и Р₂, причем в Р₁ оно входит дважды. Особый интерес представляет первое вхождение.

Определение. Марковской подстановкой называется операция над словами, задаваемая с помощью упорядоченной пары слов (Р, Q), состоящая в следующем. В заданном слове R находят первое вхождение слова Р (если таковое имеется) и, не изменяя остальных частей слова R, заменяют в нем это вхождение словом Q. Полученное слово называется результатом применения марковской подстановки (Р, Q) к слову R. Если же первого вхождения Р в слово R нет (и, следовательно, вообще нет ни одного вхождения Р в R, то считается, что марковская подстановка (Р, Q) неприменима к слову R.

Частными случаями марковских подстановок являются подстановки с пустыми словами: (L,Q), (Р, L), (L,L).

Пример 1. Примеры марковских подстановок рассмотрены в таблице, в каждой строке которой сначала дается преобразуемое слово, затем применяемая к нему марковская подстановка и, наконец, получающееся в результате слово:

Преобразуемое слово

Марковская подстановка

Результат

(85789,00)

Тарарам

(ара, L)

трам

Шрам

(ра, ар)

шарм

Функция

(L, С-)

С-функция

Логика

(ика, L)

лог

Книга

(L, L)

книга

Поляна

(пор, т)

[неприменима]

Для обозначения марковской подстановки (Р, Q) используется запись Р→Q. Она называется формулой подстановки (Р, Q). Некоторые подстановки (Р, Q) будем называть заключительными (смысл названия станет ясен чуть позже). Для обозначения таких подстановок будем использовать запись Р→.Q, называя ее формулой заключительной подстановки. Слово Р называется левой частью, а Q – правой частью в формуле подстановки.

Нормальные алгоритмы и их применение к словам.Упорядоченный конечный список формул подстановок  в алфавите А называется схемой (или записью) нормального алгоритма в А. (Запись точки в скобках означает, что она может стоять в этом месте, а может отсутствовать.) Данная схема определяет (детерминирует) алгоритм преобразования слов, называемый нормальным алгоритмом Маркова. Дадим его точное определение.

Определение. Нормальным алгоритмом (Маркова) в алфавите А называется следующее правило построения последовательности V_i слов в алфавите А, исходя из данного слова V в этом алфавите. В качестве начального слова V₀ последовательности берется слово V. Пусть для некоторого i ³ 0 слово V_i построено и процесс построения рассматриваемой последовательности еще не завершился. Если при этом в схеме нормального алгоритма нет формул, левые части которых входили бы в V_i, то V_i+1 полагают равным V_i и процесс построения последовательности считается завершившимся. Если же в схеме имеются формулы с левыми частями, входящими в V_i то в качестве V_i+1 берется результат марковской подстановки правой части первой из таких формул вместо первого вхождения ее левой части в слово V_i; процесс построения последовательности считается завершившимся, если на данном шаге была применена формула заключительной подстановки, и продолжающимся – в противном случае. Если процесс построения упомянутой последовательности обрывается, то говорят, что рассматриваемый нормальный алгоритм применим к слову V. Последний член последовательности называется результатом применения нормального алгоритма к слову V. Говорят, что нормальный алгоритм перерабатывает V в W.

Последовательность V_i будем записывать следующим образом:

.

Мы определили понятие нормального алгоритма в алфавите А. Если же алгоритм задан в некотором расширении алфавита А, то говорят, что он есть нормальный алгоритм над А.

Рассмотрим примеры нормальных алгоритмов.

Пример 2. Пусть А = {а, b} – алфавит. Рассмотрим следующую схему нормального алгоритма в А.

.

Нетрудно понять, как работает определяемый этой схемой нормальный алгоритм. Всякое слово V в алфавите А, содержащее хотя бы одно вхождение буквы а, он перерабатывает в слово, получающееся из V вычеркиванием в нем самого левого (первого) вхождения буквы а. Пустое слово он перерабатывает в пустое. (Алгоритм не применим к таким словам, которые содержат только букву b) Например, ааbаb => аbаb, аb => b, аа => а, bbаb => bbb, bаbа => bbа.

Пример 3. Пусть А = {а₀, а₁, ..., а_п} — алфавит. Рассмотрим схему:

Она определяет нормальный алгоритм, перерабатывающий всякое слово (в алфавите А) в пустое слово. Например, а₁а₂а₁а₃а₀ => а₁а₂а₁а₃ => а₂а₁а₃ => а₂а₃ => а₃ => L; а₀а₂а₂а₁а₃а₁ => а₂а₂а₁а₃а₁ => а₂а₂а₃а₁ => а₂а₂а₃ => а₂а₃ => а₃ => L.

Пример 4. А = {1, 0}. Введем дополнительный алфавит В = {с, +; *}. Рассмотрим схему (для удобства работы запишем команды схемы в столбик):

(1) 00+®0+0

(2) 01+®1+0

(3) 10+®0+1

(4) 11+®1+1

(5) с0®0+0с

(6) с1®1+1с

(7) +®*

(8) *®L

(9) с®.L

(10) L®с

Этот алгоритм любое слово Р в алфавите А переводит в слово РР. Рассмотрим подробно его работу для слова 101.

101 – начальная конфигурация. Поскольку все команды схемы, кроме (10) содержат символы, которых нет в данном слове, то первой выполняем команду (10):

с101 теперь в слове нет подслов, содержащих «+», но есть подслово «с1», значит, выполняем команду (6):

1+1с01 – нет подслов «00+», «01+», «10+», «11+», есть подслово «с0», выполняем команду (5):

1+10+0с1 – нет подслов «00+», «01+», есть подслово «10+»; выполняем команду (3):

1+0+10с1 – теперь снова нет подслов «00+», «01+», «10+», «11+», есть подслово «с1»; выполняем команду (6):

1+0+101+1с – есть подслово «01+»; выполняем команду (2):

1+0+11+01с – есть подслово «11+»; выполняем команду (4):

1+0+1+101с – снова неприменимы команды с (1) по (6), следующая команда – (7). Применяем ее последовательно 3 раза:

1*0*1*101c – теперь неприменимы команды с (1) по (7); следующая по порядку команда – (8). Применяя ее последовательно, получим:

101101с – и, наконец, применяем (9) команду и получаем заключительную конфигурацию:

101101.

Предлагаем самостоятельно переработать слово 1001 и получить слово 10011001.

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

Пример 5. В алфавите А = {1} схема L®.1 определяет нормальный алгоритм, который к каждому слову в алфавите А = {1} (все такие слова суть следующие: L, 1, 11, 111, 1111, 11111 и т. д.) приписывает слева 1. Следовательно, алгоритм реализует (вычисляет) функцию f(х) = х + 1.

Пример 6. Дана функция , где п – число единиц в слове 11...1. Рассмотрим нормальный алгоритм в алфавите А = {1} со следующей схемой:

(1) 111®L

(2) 11®.L

(3) 1®.L

(4) L®.1

Этот алгоритм работает по такому принципу: пока число букв 1 в слове не меньше 3, алгоритм последовательно стирает по три буквы. Если число букв меньше 3, но больше 0, то оставшиеся буквы 1 или 11 стираются заключительно; если слово пусто, оно заключительно переводится в слово 1. Например:

1111111 => 1111 => 1 => L; 111111111 => 111111 => 111 => L => 1.

Таким образом, рассмотренный алгоритм реализует (или вычисляет) данную функцию.

Сформулируем теперь точное определение такой вычислимости функций.

Определение. Функция f, заданная на некотором множестве слов алфавита А, называется нормально вычислимой, если найдется такое расширение В данного алфавита (А Í В) и такой нормальный алгоритм в В, что каждое слово V (в алфавите А) из области определения функции f этот алгоритм перерабатывает в слово f(V).

Таким образом, нормальные алгоритмы примеров 5 и 6 показывают, что функции f (х) = х + 1 и f₃(х) нормально вычислимы. Причем соответствующие нормальные алгоритмы удалось построить в том же самом алфавите А, на словах которого были заданы рассматривавшиеся функции, т. е. расширять алфавит не потребовалось (В = А). Следующий пример демонстрирует нормальный алгоритм в расширенном алфавите, вычисляющий данную функцию.

Пример 7. Построим нормальный алгоритм для вычисления функции f(х) = х + 1 не в одноичной системе (как сделано в примере 5), а в десятичной. В качестве алфавита возьмем перечень арабских цифр А = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, а нормальный алгоритм будем строить в его расширении В = А È {а, b}. Вот схема этого нормального алгоритма (читается по столбцам):

0b®.1          а0®0а                  0а®0b

1b®.2          а1®1а                  1а®1b

2b®.3          а2®2а                  2а®2b

3b®.4          а3®3а                  3а®3b

4b®.5          а4®4а                  4а®4b

5b®.6          а5®5а                  5а®5b

6b®.7          а6®6а                  6а®6b

7b®.8          а7®7а                  7а®7b

8b®.9          а8®8а                  8а®8b

9b®b0         а9®9а                  9а®9b

b®.1                                               L®а

Попытаемся применить алгоритм к пустому слову L. Нетрудно понять, что на каждом шаге должна будет применяться самая последняя формула данной схемы. Получается бесконечный процесс:

L => а => аа => ааа => аааа =>...

Это означает, что к пустому слову данный алгоритм не применим.

Если применить теперь алгоритм к слову 499, получим следующую последовательность слов: 499 => а499 (применена последняя формула) => 4а99 (формула из середины второго столбца) => 49а9 => 499а (дважды применена формула из конца второго столбца) => 499b (предпоследняя формула) => 49b0 => 4b00 (дважды применена предпоследняя формула первого столбца) => 500 (применена формула из середины первого столбца).

Таким образом, слово 499 перерабатывается данным нормальным алгоритмом в слово 500. Предлагается проверить, что 328 => 329, 789 => 790.

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

Сформулированный принцип, как и тезис Тьюринга, носит внематематический характер и не может быть строго доказан. Он выдвинут на основании математического и практического опыта.

Все, что ранее было сказано о тезисе Тьюринга, можно с полным правом отнести к принципу нормализации Маркова.

Познавательные статьи:



Коммуникативные барьеры и пути их преодоления

Рынок недвижимости. Сущность недвижимости

Решение задач с использованием генеалогического метода

История происхождения и развития детской игры