T-o-t-e

Оно не претендует на математическую строгость, но и не отказывается от неё. До тридцатых годов нашего века математики довольствовались этим несколько расплывчатым понятием алгоритма.

В тридцатых годах были разработаны теории, ведущие к уточнению понятия алгоритма. Мы имеем ввиду работы Клини, Чёрча, Тьюринга и Поста. Построенные этими авторами теории алгоритмов, были различными, но в естественном (процессуальном) смысле эквивалентными, что свидетельствовало в пользу этих теорий.

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

Здесь мы вкратце изложим элементы одной из этих теорий — теории нормальных алгоритмов.

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

Пусть А - какой-нибудь алфавит, не содержащий стрелку «→» и точку «.» в качестве букв. Будем называть простыми формулами подстановок [ПФП] в алфавите А слова вида

. А→В

где А и В — слова в алфавите А; будем называть заключительными формулами подстановок [ЗФП] в алфавите А слова вида

А→.В

где А и В — слова в алфавите А. ПФП и ЗФП в алфавите А мы будем называть формулами подстановок [ФП] в алфавите А. Слово А мы будем называть левой частью ФП; слово В — правой частью этой ФП.

Будем говорить, что ФП F действует на слово Р в алфавите А, если левая часть F входит в Р. В случае, когда F действует на Р, будем считать результатом действия F на Р результат подстановки правой части F вместо первого вхождения левой части F в Р. Таким образом, результат действия F на Р определен тогда и только тогда, когда F действует на Р. В этом случае результат действия F на Р есть слово в алфавите А.

Схемой в алфавите А будем называть объект вида

где все F_i суть ФП в алфавите А. ФП F_i,- будем называть i-й строкой схемы .

Будем говорить, что схема действует на слово Р в алфавите А, если хотя бы одна из строк схемы у действует на Р. В этом случае результатом действия схемы у на слово Р будем называть результат действия на Р первой (по порядку) из строк схемы , действующих на Р; будем при этом говорить, что схема просто действует на Р, если первой из строк схемы действующих на Р, является ПФП; будем говорить, что схема заключительно действует на Р, если первой из строк схемы , действующих на Р, является ЗПФ.

Таким образом, результат действия схемы на слово Р в алфавите А определен тогда и только тогда, когда схема действует на слово Р. В этом случае результат действия схемы на слово Р есть слово в алфавите, А. Схема у действует на Р либо просто, либо заключительно.

Пусть — схема в алфавите А, Р • — слово в А. Определим следующий, разбитый на шаги, конструктивный процесс.

Первый шаг процесса делается тогда и только тогда, когда схема действует на слово Р. В. этом случае шаг состоит в построении результата действия схемы на слово Р. Если же схема не действует на слово Р, то Р считается результатом всего процесса.

(k+1)-й шаг процесса делается, если сделан k-й шаг процесса, схема на k-м шагу действовала просто, и схема действует на результат k-ro шага. В этом случае (k+1)-й шаг состоит в построении результата действия схемы на результат k-го шага.

Если же схема действовала на k-м шагу заключительно или схема не действует на результат k-го шага, то (k+1)-й шаг не делается, процесс обрывается и результатом всего процесс а считается результат его k-го шага.

Только что сформулированное предписание определяет некоторый конструктивный процесс и тем самым является алгоритмом. Однако это алгоритм некоторого стандартного вида: шаги процесса, определяемого алгоритмом, начало и конец этого процесс а определены стандартным образом, благодаря чему расплывчатость предписания исчезла.

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

Пусть U - - нормальный алгоритм в алфавите А, определяемый схемой в А. Мы говорим, что слово Р в А не поддается алгоритму U

U: P

и пишем если схема не действует на Р;

Мы говорим, что U просто переводит Р в Q, и пишем

U: P Q

если схема просто действует на Р и Q есть результат действия схемы на Р; мы говорим, что алгоритм U заключительно переводит Р в Q, и пишем

U: P . Q

если схема заключительно действует на Р и Q есть результат действия схемы на Р.

Описанный выше процесс, определяемый алгоритмом U и словом Р, мы будем называть процесс ом применения алгоритма U к слову Р. Мы будем говорить, что алгоритм U применим к слову Р, если этот процесс обрывается. В этом случае имеется результат этого процесса — некоторое слово в алфавите А. Мы будем говорить, что алгоритм U перерабатывает слово Р в слово Q, если Q является результатом процесс а применения алгоритма U к слову Р.

В дальнейшем запись

U:P!

будет означать, что алгоритм U применим к слову Р, а запись

U: P Q

будет означать, что алгоритм U перерабатывает Р в Q.

Ясно, что алгоритм U тогда и только тогда применим к слову Р, когда имеется слово Q, в которое U перерабатывает Р.

Говорить о применимости алгоритма U к слову в алфавите А и о переработке этим алгоритмом одного слова в алфавите А в другое слово в алфавите А можно, очевидно, и в случае, когда алгоритм U не нормален, когда это есть какой-то алгоритм, оперирующий со словами в алфавите А. Среди таких: алгоритмов в алфавите А - нормальные алгоритмы хороши прежде всего тем, что они имеют точное определение.

Будем говорить об алгоритме U, что он есть алгоритм, над алфавитом А, если он есть алгоритм в некотором алфавите, содержащем А. Пусть U и B - - алгоритмы над алфавитом А. Будем говорить, что они эквивалентны относительно А, если соблюдаются следующие условия.

1°. Всякий раз, когда U перерабатывает какое-нибудь слово Р в алфавите А в слово Q в этом же алфавите, B также перерабатывает Р в Q.

2°. Всякий раз, когда B перерабатывает Слово Р в алфавите А в слово Q в этом же алфавите, U также перерабатывает Р в Q.

Принцип - нормализации утверждает, что всякий алгоритм, в алфавите А эквивалентен относительно А некоторому нормальному алгоритму над А.

Принцип нормализации не есть математическая теорема ввиду нечеткости общего понятия алгоритма. Поэтому его нельзя доказывать, а можно лишь приводить доводы в его пользу.

Главным таким доводом является тот факт, что все, до сих пор рассмотренные с этой точки зрения алгоритмы оказались нормализуемыми, т. е. эквивалентными нормальным алгоритмам. Следует также принять во внимание, что все построенные до сих пор уточнения понятия алгоритма привели к типам алгоритмов, для которых удалось доказать нормализуемость. Наконец, в пользу принципа нормализации свидетельствует и то, что

различные способы комбинирования алгоритмов - способы построения новых алгоритмов по исходному набору данных алгоритмов - ведут от нормализуемых алгоритмов снова к нормализуемым.

Дата добавления: 2015-08-03