[ Алгоритмическая полнота.
Алгорифмы Маркова.
(Семинар №6 22.03.2006)
А. П. Немытых1, *
1 Институт программных систем РАН
алгоритмический.
Язык рефАЛ Естественно встаёт вопрос об
алгоритмической полноте РЕФАЛа. Оказывается даже базисное подмножество РЕФАЛа, которое мы до сих пор только и рассматривали, является алгоритмически полным языком. То есть, любой алгоритм может быть запрограммирован на базисном РЕФАЛе.
1. АЛГОРИТМИЧЕСКАЯ ПОЛНОТА
Задача 1 Воспользовавшись тезисом Чёрча, докажите что базисный РЕФАЛ является алгоритмически полным языком.Большая часть языков программирования обладают свойством алгоритмической полноты. Следовательно, любую программу, написанную на одном из таких языков программирования, можно перевести на другой язык.
Разнообразие языков программирования объясняется их ориентацией на конкретные классы задач. Вопрос не в том можно или нельзя решить какую-то задачу на данном языке программировании L, а в том удобно или нет решать эту задачу на языке L.
Язык есть инструмент для решения задачи: хотя и можно гвозди забивать сковородкой (и даже лбом), но очень не удобно, – предпочитают использовать молоток.
РЕФАЛ ориентирован на преобразование текстов (символьной информации).
* Electronic address: [email protected]
2. АЛГОРИФМЫ МАРКОВА
Операционная семантика языка РЕФАЛ основана на теоретической модели вычислений, называемой нормальными алгорифмами А.А. Маркова.Пусть дан некоторый алфавит A. Рассмотрим свободную алфавитную полугруппу G над A. В качестве элементарной операции, на базе которой строятся алгорифмы Маркова, используется подстановка одного элемента G вместо другого. Если x, y G, то выражения x y и x • y будем называть формулами подстановки. При этом предполагается, что стрелка и точка • не являются буквами алфавита A.
Формула подстановки x y называется простой. Формула подстановки x • y называется заключительной. Пусть P Q обозначает любую из формул подстановки (простую или заключительную). Конечная последовательность формул подстановки P1 Q P2 Q.........
P Q r r называется схемой алгорифма.
Скажем, что последовательность (как элемент) x G входит в последовательность y G, если существуют такие (возможно пустые) u, v G, что y = u x v.
Задача 2 Пусть дано y G. Скажем, что существует два перекрывающихся вхождения x G в y, если v G такое, что v входит в y, v = x и v0 некоторое вхождение v в y такое, что p G q G. v0 = x p = q x.
Написать на РЕФАЛе программу, проверяющую, что для данной последовательности y ¬ последовательности x, которая имеет перекрывающееся вхождение в y.
Работа алгоритма, порождённого схемой алгорифма, может быть описана следующим образом. Пусть дано p G.
• Находим первую в схеме алгорифма формулу подстановки Pm Qm такую, что Pm входит в p.
• Подставляем Qm вместо самого левого вхождения Pm в p. Пусть r1 – результат такой подстановки.
• Если Pm Qm – заключительная формула подстановки, то работа алгоритма заканчивается и его значением является r1.
• Если Pm Qm – простая, то применим к r1 тот же поиск, который только что применяли к p, и так далее.
• Если мы на i-ом шаге получим такое ri, что ни одна из P1,..., Pr не входит в ri, то работа алгоритма заканчивается и ri будет его значением.
• При этом возможно, что описанный процесс никогда не закончится. В таком случае мы скажем, что алгоритм не применим к p.
Алгоритм, определённый таким образом, называется нормальным алгорифмом Маркова в алфавите A.
Задача 3 Объясните в чём сходство и различие, описанной выше, машины Маркова и РЕФАЛ-машины. Что в машине Маркова является аналогом:
1. начальных данных?
2. вызова функции?
3. поля зрения?
4. активного вызова функции?
5. аварийной остановки отождествление невозможно ?
Что в РЕФАЛ-машине является аналогом заключительной формулы подстановки?
Пример: Пусть A = {b, c}. Пусть G – свободная алфавитная полугруппу над A.
Определяемый этой схемой нормальный алгорифм перерабатывает всякое p G, содержащее хотя бы одно вхождение буквы b, в элемент G, который получается вычёркиванием в p0 самого левого вхождения буквы b. Пустая последовательность перерабатывается в саму себя. Алгорифм неприменим к непустым последовательностям, не содержащим буквы b.
Задача 4 Приведите конструктивное доказательство следующего утверждения.
Если некоторый алгоритм A может быть описан схемой Маркова, то программа U, написанная на базисном РЕФАЛе такая, что x из множества определения функции F, соответствующей алгоритму A, значение F (x) может быть вычислено посредством программы U, то есть F (x) = U (x). Под конструктивностью здесь мы понимаем явное предъявление программы U.
Задача 5 Реализуйте машину Маркова посредством РЕФАЛ-машины. Как связана данная задача с предыдущей? Проверьте работу построенной вами программы на всех алгорифмах Маркова, схемы которых рассматриваются в задачах или схемы которых требуется построить в задачах (данного семинара и домашнего задания).
Задача 6 Пусть A – произвольный алфавит. Пусть G – свободная алфавитная полугруппа над A. Рассмотрим (сокращённо записанную) схему алгорифма в алфавите Эта схема определяет некоторый нормальный алгорифм Rev в алфавите B.
Докажите, что p G. Rev(p) = p. Где последовательность p получена из p обращением: если p = a1... an, то p = an... a1.
Задача 7 Пусть алфавит A не содержит букву, и пусть B = A {}. Пусть G – свободная алфавитная полугруппу над A. Построить нормальный алгорифм Маркова в B, стирающий первую букву во всякой непустой последовательности p G.
Задача 8 Пусть алфавит A не содержит букв,,, и пусть C = A {,, }.
Пусть G – свободная алфавитная полугруппу над A. Построить нормальный алгорифм Маркова F в С такой, что p G было бы выполнено равенство F (p) = p p.
y1,..., yk. Требуется построить последовательность термов z1,..., zm, состоящую из совпадающих и имеющих равные порядковые номера термов двух исходных последовательностей; порядок термов zi друг относительно друга не изменять.
Задача 10 Длина Ln(d) РЕФАЛ-выражения d определяется индуктивно:
1. длина пустого выражения равна нулю;
2. Ln(t.x e.d) = 1 + Ln(e.d).
Определить на РЕФАЛе функцию, значение которой есть длина данного выражения.
Задача 11 Размер Size(d) РЕФАЛ-выражения d определяется индуктивно:
1. размер пустого выражения равен нулю;
2. Size(s.x e.d) = 1 + Size(e.d);
3. Size((e.x) e.d) = 2 + Size(e.x) + Size(e.d).
Определить на РЕФАЛе функцию, значение которой есть размер данного выражения.
«