"ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ" - читать интересную книгу автора (Соловьев Александр)

Лекция 11. ТЕОРИЯ АЛГОРИТМОВ

Теория алгоритмов не учит «составлять» алгоритмы. Она занимается более важным вопросом. Основная задача классической теории алгоритмов – это ответ на вопрос: «Можно ли (вообще) для задач данного типа построить алгоритм?». Говоря более наукообразно: «Являются ли задачи данного типа алгоритмически разрешимыми»?

Это связано с тем, что, во-первых, не для всех задач возможно создать алгоритмы их решения. А, во-вторых, чтобы сделать математически строгий вывод о невозможности построить алгоритм, надо иметь строгое (формальное) определение самого алгоритма. Но понятие АЛГОРИТМА относится к фундаментальным неопределяемым понятиям. В вопросе об алгоритме у нас собачья позиция. Понимать понимаем, а сказать не можем. Если где-то встречаете «определение» алгоритма, то там, что ни слово – то аллегория…

Из этого тупика был найден нетривиальный выход. Понятие алгоритма заменили строго формализованными математическими моделями. Среди самых известных рекурсивные функции, машины Тьюринга и нормальные алгорифмы Маркова.

Эти математические модели выступают в роли «конкретизаций понятия алгоритма». То есть длительная практика подтверждает так называемый тезис Черча, который можно пересказать так:

Для любой алгоритмически разрешимой задачи можно построить рекурсивную функцию (машину Тьюринга, нормальный алгорифм Маркова). И наоборот, для задач, для которых нельзя построить перечисленные конкретизации, не существует алгоритма решения.

РЕКУРСИВНЫЕ ФУНКЦИИ основаны на той идее, что исходные данные и возможные результаты решения любой задачи можно пронумеровать. Для чего, естественно, достаточно множества натуральных чисел (целых положительных чисел, начиная с нуля). А далее базовыми об'являются функции, возможность выполнить (вычислить) которые не вызывает сомнений.

НУЛЬ– ФУНКЦИЯ – это функция, которая дает значение ноль для любого значения аргумента. Реализовать эту функцию может не только ребенок. Можно посадить попугая и подучить его на любой вопрос о значении функции кричать «Ноль!».

ФУНКЦИЯ СЛЕДОВАНИЯ дает следующее, по сравнению с аргументом, значение. Для пяти это шесть, для миллиона – миллион один. Можно бы было сказать, что здесь надо просто прибавлять 1.

Но операции сложения у нас пока нет!

ФУНКЦИЯ ВЫБОРА АРГУМЕНТА. Это вообще забавная даже для первоклассника функция, содержащая в своем имени номер аргумента. Если у вас есть несколько аргументов, то эта функция в качестве значения возьмет значение указанного в ней аргумента. Например, функция выбора третьего из Иванова, Петрова и Сидорова, которых мы ранее пронумеровали, например, как 22, 13 и 49, даст значение 49.

Эти три базовых функции могут использоваться далее в качестве исходного материала для создания более сложных функций с помощью трех операторов: суперпозиции, примитивной рекурсии и наименьшего корня.

Известный хорошо еще со школы ОПЕРАТОР СУПЕРПОЗИЦИИ позволяет вместо аргумента подставлять функцию… «Игла в яйце, а яйцо в ларце»…

Дольше словами описывать ОПЕРАТОР ПРИМИТИВНОЙ РЕКУРСИИ. Но если поднатужиться, то можно понять. Этот оператор позволяет построить новую функцию из двух функций, одна из которых имеет на один аргумент меньше, а другая на один аргумент больше.

Значение создаваемой функции для нулевого значения выбранного аргумента приравнивается к функции, не имеющей как раз этого аргумента. Значение же создаваемой функции для всех прочих

(ненулевых) значений выбранного аргумента приравнивается другой функции, зависящей (напрягитесь!) от тех же аргументов, кроме выбранного; от ПРЕДЫДУЩЕГО значения выбранного аргумента и от создаваемой функции от предыдущего значения выбранного аргумента.

Ну как тут не пожалеть о формулах.

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

Функцию умножения икс на ноль можно выразить через нуль-функцию от икс, которая обеспечит нам желанное значение – ноль.

Функцию умножения икс на игрек (отличный от нуля) можно выразить через функцию сложения икса со значением функции умножения икса на предыдущее значение игрека… То есть мы выразили умножение через сложение.

Здесь следует сделать два замечания. Считаем, что к этому моменту доказана рекурсивность используемой здесь функция сложения. И второе, при умножении икс на игрек в нашем распоряжении функция от трех аргументов. Но, применив проектирующую функцию мы избавимся от среднего аргумента, коль скоро он нам здесь не нужен. Нам ведь дозволено заниматься подбором из возможного!

Последний оператор – ОПЕРАТОР НАИМЕНЬШЕГО КОРНЯ. Его необходимость просто об'яснить хотя бы тем, что рекурсивные функции, призванные решать любые алгоритмически разрешимые задачи, сами используют лишь целые положительные числа. А это не позволяет решить даже детскую задачку: 5 – 8 =? (Нет для рекурсивных функций отрицательных чисел). На самом-то деле эти детские задачки можно решить по-детски. Договориться, что 1000 это (сдвинутый) ноль, а вычитание – есть сложение с «отрицательным» числом! Тогда

1005 + 992 = 1997 (приведение к шкале: 1997 – 1000 = 997)

Поскольку мы при этом сдвиг нуля учли дважды, то окончательный результат (в системе с один раз сдвинутым на 1000 нулем) будет 997. Но это детское решение лишь говорит о том, что без отрицательных чисел и в школе можно обойтись. Как и в древнем Риме обходились. Правда там и без нуля обходились, а здесь он нам нужен позарез.

Именно оператор наименьшего корня и следит, при каком значении выбранного аргумента наблюдаемая им функция впервые опустится до нуля. Это значение выбранного аргумента и будет значением оператора наименьшего корня. Например, для функции икс минус игрек при иксе равном 5, значение оператора наименьшего корня также будет равно 5, поскольку двигаясь в значениях игрека от нуля получим нулевое значение функции именно при игрек равном 5.

Базовые функции и функции, которые могут быть построены из них с помощью операторов суперпозиции, примитивной рекурсии и наименьшего корня, образуют множество ЧАСТИЧНО-РЕКУРСИВНЫХ ФУНКЦИЙ. А множество частично-рекурсивных функций совпадает с множеством всех алгоритмически разрешимых задач (множеством всех вычислимых функций). Кстати, за слово «частичные» надо благодарить оператор наименьшего корня, из-за которого в множество построенных функций входят и не всюду определенные (частичные) функции.

Тьюринг не был автостроителем. Машина Тьюринга не предполагает двигателя внутреннего сгорания, поскольку все там перемещается исключительно силой мысли. Это математическая модель. Она чем-то может и напоминающая автомашину, но не более чем машину напоминает магнитофон, в котором лента (разделенная на ячейки) неподвижна, а считывающе-записывающая головка вдоль нее ездит. Хуже того, ездит головка рывками, от ячейки к ячейке. А в ячейках записаны символы. (Чтобы не было пустых ячеек, в пустые ячейки записывают специальный пустой символ).

В машине Тьюринга есть устройство управления, имеющее память «состояний» и работающее по задаваемой программе (алгоритму). Программа состоит из команд. Каждая «команда» состоит в следующем: Машина читает символ из ячейки, против которой стоит головка (находясь в каком-то состоянии [вначале – в начальном]), записывает в эту ячейку символ (может и тот же самый), меняет свое состояние (может сохранить прежнее) и делает шаг влево или вправо (может остаться на месте).

Так Машина ходит вдоль ленты до тех пор, пока не перейдет в специальное состояние, называемое заключительным. Это говорит об окончании работы Машины (алгоритма). А на ленте остается результат (решения).

Пример. Построим Машину, которая в сплошной последовательности единичек стирает последнюю.

Поскольку количество единичек в сплошной последовательности произвольное и неизвестное, последнюю определим как ту, которая стоит ПЕРЕД пустым символом. Это главная идея данного решения. Остальное – дело техники. Напишем программу – четыре команды.

Машина читает пустой символ, находясь в начальном состоянии пишет пустой символ и делает шаг вправо. (Значит машина находится ДО начала последовательности единичек)

Машина читает единичку, находясь в начальном состоянии, пишет единичку и делает шаг вправо, оставаясь в этом состоянии. (Значит машина «идет» по последовательности единичек)

Машина читает пустой символ, находясь в начальном состоянии, пишет пустой символ, делает шаг влево и переходит во второе состояние. (Значит найдена последняя единичка)

Машина читает единичку, находясь во втором состоянии, пишет пустой символ (стирает единичку), стоит на месте и переходит в заключительное состояние. (Задача решена)

Несмотря на внешнюю примитивность такой конструкции, для любой алгоритмически разрешимой задачи можно построить Машину Тьюринга! А поскольку машина строится в собственной голове, вопросы «технической эффективности» такой машины никакой роли не играют. Единственный вопрос. Доберется ли машина до заключительного состояния? Пусть и через (воображаемый) миллион лет. Тогда задача разрешима!

Не будет преувеличением сказать, что нормальные алгорифмы Маркова создал А.А.Марков, член-корреспондент Академии Наук СССР из Москвы. Для восстановления единообразия, по праву автора, он назвал алгориТмы алгориФмами, поскольку слово это арабо-греческое, как и слово ариФметика…

Смысл нормальных алгорифмов – принудительный обмен, порядок которого жестко задан.

Собственно алгоритм в нормальных алгорифмах задается НОРМАЛЬНОЙ СХЕМОЙ ПОДСТАНОВОК – очередностью правил «что на что менять». Лучше всего это показать на примере замены слов, тем более, что и сам Марков любую последовательность букв, какую ни в одном словаре не сыщешь, называл «словами». Так при наличии двух подстановок: меняющей «ха» на «ссон» и «мусс» на «сл» из «муха» можно сделать «слон».

Механизм нормальных алгоритмов настолько прост, что напоминает скорее детскую игру, чем математику. Но на самом деле это очень мощный механизм, поскольку через него можно выразить решение любой алгоритмически разрешимой задачи. И опять напомним, что это не следует воспринимать, как предложение решать любую задачу через подстановки (хотя на этих принципах работает замечательный язык программирования РЕФАЛ). Это лишь означает, что любую алгоритмически разрешимую задачу МОЖНО представить в виде такой системы подстановок. А если нельзя (и вы это смогли доказать), то такая задача вообще не имеет алгоритма решения.