Лекции - Теория алгоритмов
Подождите немного. Документ загружается.
Алгорифм сложения натуральных
чисел
Построим нормальный алгорифм, вычисляющий сумму двух
натуральных чисел x и y. Для этого рассмотрим алфавит из трех
символов A={0,|,+ }. Число n N изображаем словом
0||...|
в алфавите A. В этом слове n палочек, перед которыми
поставлен символ 0.
Искомый нормальный алгорифм A имеет схему из одной
заключительной формулы подстановки u
1
v
1
, где u
1
= +0 - слово из
двух букв, а v
1
= - пустое слово. Тем самым схема алгорифма
имеет вид
+0
Если нужно вычислить сумму x+y, то подаем на вход алгорифма A ее
изображение, т.е. слово
P=0||...|+0||...|
Алгорифм сложения натуральных
чисел (продолжение)
Алгоритм A удалит из P подслово +0 и в один шаг
переработает входное слово P в выходное слово Q.
При этом
Q=0||...|||...|
Принцип нормализации Маркова
Сделаем несколько предварительных замечаний. Не все
вербальные алгорифмы являются нормальными алгорифмами,
такткак вербальные алгорифмы реализуют произвольные
преобразования слов, а нормальные алгорифмы ограничены
преобразованиями слов по заданной схеме. Поэтому
определение алгоритма по Маркову не будет утверждать о
совпадении класса
нормальных алгорифмов и класса вербальных алгорифмов, а
будет иметь другую формулировку. Рассмотрим эту
формулировку.
Пусть задан алфавит A. Добавим к алфавиту A новые буквы.
Получим алфавит A
1
с условием AA
1
. Алфавит A
1
называется
расширением алфавита A.
Нормальный алгорифм в каком-либо расширении A
1
алфавита A
называется нормальным алгорифмом над алфавитом A.
Принцип нормализации Маркова
(продолжение)
А.А.Марков предложил следующий тезис.
Принцип нормализации.
Пусть задан произвольный вербальный алгорифм A
в алфавите A. Тогда существует расширение A
1
алфавита A и нормальный алгорифм A
1
в алфавите
A
1
с условием: произвольное слово P в алфавите A
перерабатывается нормальным алгорифмом A
1
в тот
же самый результат, в который слово P
перерабатывается исходным вербальным алгориф-
мом A.
Принцип нормализации Маркова
(продолжение)
Если мы не используем принцип нормализации, то всякий раз, имея
произвольный вербальный алгорифм, мы не в состоянии обозреть все
возможные действия A,B,… , которые производятся над
перерабатываемыми объектами. Если мы не в состоянии обозреть все
возможные действия A,B,…, то не сможем подобным
образом доказать несуществование алгорифма A.
Напротив, если мы используем принцип нормализации, то
действия в произвольном вербальном алгорифме A обозримы и четко
перечислены. Действительно, у нас есть нормальный алгорифм A
1
в
алфавите A
1
и его действия на словах из A
1
жестко заданы и обозримы
схемой алгорифма A
1
. Тем более обозримы ограничения этих действий
на словах алфавита A, а это и есть действия вербального алгорифма
A.
Принцип нормализации Маркова
(продолжение)
Поэтому принцип нормализации можно рассматривать как способ
обозрения всевозможных действий в вербальных алгоритмах.
Поскольку эти действия строго заданы, то мы имеем третий вариант
определения алгоритма. В результате принятия принципа
нормализации мы получили инструмент для доказательства
неосуществимости задачи нахождения определенного алгоритма.
Доказано, что данная формулировка понятия алгоритма (принцип
нормализации) эквивалентна другим формулировкам понятия
алгоритма: тезису Черча, использующему частично рекурсивные
функции, и тезису Тьюринга, использующему понятие
вычислительной машины. Поэтому еще раз подкрепляется уверенность
в том, что мы нашли и выразили в трех формах фундаментальное
понятие математики, логики и информатики - понятие алгоритма. При
этом частичная рекурсивность, машина Тьюринга, МНР и нормальный
алгорифм - лишь различные формы выражения этого самостоятельного
понятия.