Лекции - Теория алгоритмов
Подождите немного. Документ загружается.
Заключение.
► Как следствие трех полученных выше теорем имеем.
► Теорема 4. Всякая частично рекурсивная функция
вычислима на некоторой МНР.
► Учитывая тезис Черча о совпадении класса вычислимых
функций с классом частично рекурсивных функций,
получаем утверждение.
► Теорема 5. Функция f является вычислимой функцией
тогда и только тогда, когда функция f вычислима на
некоторой МНР.
Лекция 8. Нормальные
алгорифмы
• Третий вариант формали-
зации понятия алгоритма
предложен российским ма-
тематиком А.А.Марковым.
• В этом определении
считается, что алгорит-
мический процесс - это
процесс переработки слов
некоторого алфавита.
Следуя А.А.Маркову, наряду со словом алгоритм будем
употреблять также слово алгорифм. Алгоритмы,
которые являются процессами переработки слов,
назовем вербальными алгорифмами. Поскольку речь
идет о произвольных, а не строго заданных правилах
действий со словами, то понятие вербального
алгорифма является интуитивным понятием. Среди
вербальных алгорифмов выделим некоторые
алгорифмы --- нормальные алгорифмы со строго
заданными правилами переработки слов. Поэтому
понятие нормального алгорифма является строгим
математическим понятием. Введем это понятие.
Вербальные алгорифмы
Алфавит нормального алгорифма A ---
это некоторая конечная совокупность
символов A = {a
1
, ... , a
m
}. Элементы из A
мы будем называть буквами. Из букв
алфавита A составляются слова ---
конструктивные объекты, которые
поступают на вход и перерабатываются в
алгорифме A. При этом говорят, что A ---
алгорифм в алфавите A.
Алфавит нормального алгорифма
Рассмотрим две буквы и , которые не входят в алфавит A.
Формулой подстановки назовем выражение
u v
или выражение
u v,
где u и v - произвольные слова в алфавите A.
Формула без точки называется простой формулой, а формула с
точкой называется заключительной формулой. В обоих случаях
формула имеет левую часть u и правую часть v, которые
должны быть словами в алфавите A. Знаки и могут быть
любыми буквами вне алфавита A. Мы могли вместо них
использовать, например, греческие буквы и .
Схема нормального алгорифма
Схема нормального алгорифма
(продолжение)
Схема Z нормального алгорифма A --- это
конечная упорядоченная последователь-
ность формул подстановок
u
1
v
1
u
2
v
2
………….
u
k
v
k
,
где вместо некоторых формул u
i
v
i
могут
быть формулы с точкой u
i
v
i
.
Работа нормального алгорифма
Пусть на вход нормального алгорифма A со
схемой Z поступило слово P. Начинаем
процесс, направленный на получение из
исходного слова P некоторого слова Q -
результата переработки слова P. Совер-
шаем проход по схеме Z, двигаясь сверху
вниз
u
1
() v
1
u
2
() v
2
………….
u
k
() v
k
,
Работа нормального алгорифма
(продолжение)
Наше намерение - осуществить следующие действия 1) - 5).
1) Среди левых частей u
1
, u
2
, … , u
K
в Z нужно отыскать первое по
порядку слово u
i
, которое входит в слово P.
2) Заменить найденное слово u
i
в слове P на слово v
i
, и получить
некоторое слово P
1
. Возможно несколько вхождений u
i
в слово P. Тогда
заменяется на v
i
первое вхождение u
i
в слове P.
3) Если при замене применялась заключительная формула u
i
v
i
,
то переработка слова P завершена и алгоритм останавливается.
Полученное слово P
1
- результат переработки слова P.
4) Если при замене применялась незаключительная формула
u
i
v
i
, то слово P
1
заново обрабатывается схемой Z и алгоритм
продолжает работу.
5) Возможно, что при проходе по схеме Z вообще не обнаружено ни
одного вхождения u
1
, u
2
, … , u
K
в слово P. Тогда результат переработки
- само слово P и алгоритм останавливается.
Условие остановки и результат работы
Проанализируем протекание алгоритмического процесса и его
результат.
Обозначим дополнительно исходное слово P=P
0
.
Рассмотрим первый проход по схеме (аналогично для других
проходов).
Имеем две возможности а) и б).
а) Нет ни одного вхождения u
1
, u
2
, … , u
K
в слово P=P
0
. Алгорифм
останавливается (1 случай остановки). P
0
. - результат переработки.
б) Существуют вхождения u
1
, u
2
, … , u
K
в слово P=P
0
. Выполнена
замена u
i
на v
i
и получено слово P
1
. Если при замене применялась
заключительная формула, то переработка слова P завершена.
Алгорифм останавливается (2 случай остановки). Если при замене
применялась незаключительная формула, то полученное слово P
1
заново обрабатывается схемой. При втором проходе по схеме из P
1
получаем слово P
2
, а затем возможно P
3
и т.д.
Условие остановки и результат работы
(продолжение)
В результате получаем ровно один из двух случаев I или II.
I. Процесс переработки слов обрывается и получено слово
Q=A(P), т.е. получен результат применения нормального A к
слову P.
II. Процесс переработки слов бесконечен. Тогда нет
результата Q = A(P) и алгорифм A неприменим к слову P.
Очевидно, что описанный выше нормальный алгорифм A
удовлетворяет всем требованиям, предъявляемым к понятию
алгоритма, и является точным математическим понятием.