lec16
.pdf
Исходное задание представляется некоторым словом P в алфавите A. P является входным для первой операции, если замена произошла, то снова выполняется первая операция, если нет, то выполняется следующая операция. После каждой операции выполняется следующая операция, если замена произошла, иначе переходят к выполнению первой операции.
P Q: x p y →
x q y
Уточнения:
1.Если левая часть p формулы подстановки входит в слово P, то говорят, что эта формула применима к P. Если p P, то формула считается неприменимой к Р, и подстановка не выполняется.
2.Если p входит в Р несколько раз, то на правую часть q, по определению, заменяется только первое вхождение p в Р:
P Q: x p y p z → x q y p z
3. В подстановках допустимо использование какого-либо специального знака(ов), (например, ξ A), при соблюдении справедливости отображения
– НАМ:A A. Т.е. ξ P1, ξ Qk (P1/Qk – входное/выходное слово). |
11 |
4. Если q=□, то подстановка p→ сводится к вычеркиванию части p из Р (! в формулах не обязательно как-либо обозначать пустое слово):
P Q: x p y →
x y
5. Если p=□, то подстановка →q сводится, к приписыванию q слева к слову P: P Q: x →
q x
6. В этих формулах могут использоваться два вида стрелок: обычная стрелка (→) и стрелка «с хвостиком» ( ). Формула c (→) – обычная формула, а формула с ( ) – заключительная формула: после её применения работа НАМ прекращается, а текущее слово Q и будет выходным словом, т.е. результатом применения НАМ к входному слову.
Записать алгоритм в виде НАМ – значит предъявить такой набор формул.
7. Если на очередном шаге к текущему слову неприменима ни одна формула, то и в этом случае работа НАМ прекращается, а выходным словом считается текущее слово.
12
Пример 16.3. НАМ: сложение в классическом представлении МТ. |
|
А={+, 1}. Решение: НАМ: 1+1 11 |
(1) |
|
|
1 1 |
(2) |
Дано входное слово P = ’11+11+1’. Итерации работы НАМ: |
|
1)применение к P подстановки (1): 11+11+1 1111+1;
2)применение к ‘1111+1’ подстановки (1): 1111+1 11111;
3)применение к ‘11111’ подстановки (2): 11111 11111 и останов.
Пример 16.4. НАМ, реализующий перестановку символов.
А={a,b}. Преобразовать слово Р так, чтобы в его начале оказались все символы a, а в конце – все символы b.
Решение: НАМ: { ba ab (1)
Дано входное слово P = ’babba’. Итерации работы НАМ: babba → abbba → abbab → ababb → aabbb.
!!! в НАМ, в отличие от машины Тьюринга, легко реализуются
перестановки, вставки и удаления символов.
13
Часть 3.
Определение алгоритма и его характерные свойства.
Различные нормальные алгоритмы отличаются друг от друга лишь алфавитами и системами допустимых подстановок. Чтобы задать какойлибо нормальный алгоритм достаточно задать алфавит и систему подстановок. Нормальный алгоритм определяет отображение F: A*→A* множеств слов в алфавите А.
Оказалось, что класс функций, вычислимых с помощью нормальных алгоритмов, совпадает с классом ЧРФ.
Пример 16.5. Эквивалентность НАМ и МТ (ЧРФ).
Построить НАМ и МТ (из примера 15.1а) для вычисления y=x+1.
А= 1,* |
|
|
|
|
|
|
|
□ |
1 |
||
НАМ: {1 11 |
МТ: { 1q1 1q1R; □q1 1q1S} |
|
|||
|
|
|
|||
q1 |
1qzS |
1q1R |
|||
|
|
Алгоритмом называется точное предписание, определяющее вычислительный процесс, который ведет от варьируемых исходных данных к искомому результату, то есть алгоритм – это совокупность правил, определяющих данный вычислительный процесс.
15
Свойства алгоритмов.
Анализ известных в математике алгоритмов дал возможность выявить его характерные свойства.
1. Дискретность: Выполнение алгоритма состоит из отдельных шагов. Каждый шаг обязательно завершается.
2. Элементарность шагов. Выполнение каждого шага работы алгоритма должно быть простым и не требовать какой-либо изобретательности от исполнителя.
3. Детерминированность. Результат выполнения каждого шага алгоритма однозначно определяется программой и результатами выполнения предыдущих шагов алгоритма.
4. Результативность: Должно быть указано, что надо считать результатом алгоритма.
5. Массовость: Исходные данные для алгоритма могут выбираться из заранее фиксированных множеств возможных исходных данных. Однако, это множество бесконечно. То есть алгоритм служит для
решения целого класса задач.
16
Часть 4.
Вычислимость по Тьюрингу частично-рекурсивных функций.
Машины Тьюринга дают возможность строить формальные алгоритмы.
Задача алгоритмически разрешима по Тьюрингу существует программа для машины Тьюринга позволяющая решать задачу.
То есть Тьюрингов подход к ответу на вопрос «Что такое алгоритм?» очень прост «Алгоритм – это машина Тьюринга».
Вычислимость по Тьюрингу частично-рекурсивных функций.
Утверждение 16.1 (тезисом Черча-Тьюринга). Любая ЧРФ вычислима по Тьюрингу. И обратно: функция, вычислимая по Тьюрингу, является частичнорекурсивной.
Другими словами, для всякой функции, которую можно каким-либо способом вычислить, можно построить вычисляющую ее машину Тьюринга.
!!! Какие бы классы алгоритмов до сих пор не строились, во всех случаях оказывается, что числовые функции, вычисляемые посредством этих алгоритмов, были частично-рекурсивными.
18
Утверждение 16.2. Класс функций, вычислимых по Маркову, совпадает с классом функций, вычислимых по Тьюрингу, и следовательно, совпадает с классом частично-рекурсивных функций.
Возникает естественный вопрос: «Существуют ли алгоритмически неразрешимые по Тьюрингу проблемы?». Имея точное определение вычислимости, удалось доказать, что некоторые проблемы неразрешимы.
1.Теорема Черча о неразрешимости логики предикатов: Не существует алгоритма, который для любой формулы логики предикатов устанавливает общезначима она или нет.
2.Проблема остановки неразрешима: Не существует никакого общего алгоритма, позволяющего установить, остановится ли некоторая конкретная программа (на любом языке программирования), запущенная после введения в нее некоторого конкретного набора данных.
!!! Смысл этого утверждения для теоретического программирования очевиден: не существует совершенно общего метода проверки программ на
наличие в них бесконечных циклов.
19