Дискретная математика без формул - Соловьев Александр. Страница 12

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лекция 12. ФОРМАЛЬНЫЕ ГРАММАТИКИ

Формальные грамматики – это хорошо развитый математический аппарат, позволяющий, кроме изучения «высоких материй», (математически) грамотно создавать языки программирования и писать компиляторы для этих языков.

Между естественными и формальными языками непреодолимая пропасть. Поэтому совпадение терминологии лучше считать случайным… Тем более, в рамках многогранного и разветвленного ЯЗЫКА МАТЕМАТИКИ раздел формальных грамматик и языков ориентирован прежде всего на проблемы построения компиляторов.

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

Словами данного языка может быть далеко не любая абракадабра, доступная клавиатуре. А только лексически и синтаксически (безупречно!) правильные программы. Безупречная с точки зрения грамматики программа может быть бесполезной, бессмысленной или даже вредной. Но за правильную работу программы формальная грамматика и компилятор не отвечают. (Повторим, математика обычно смыслом не занимается).

Поскольку и здесь, в формальных грамматиках и языках, математика за смысл не отвечает. Есть специальное направление в теоретическом программировании, когда на формальном языке (обычно на языке предикатов и его диалектах) описывается, что должна делать программа. На основании этого описания специальная система синтезирует программу. Однако, это тема совсем другого разговора. Тем более, что ошибок в описании того, что должна делать программа, человек допускает больше, чем при написании программы непосредственно.

Для того, чтобы задать грамматику, надо задать множества ТЕРМИНАЛЬНЫХ и НЕТЕРМИНАЛЬНЫХ символов. Терминальные символы это символы используемые в языке. Нетерминальные (промежуточные) символы – это символы, используемые в создании (порождении) слов языка. А создаются слова по грамматическим правилам. И каждое слово, напомним, это с точки зрения программиста – программа, записанная исключительно терминальными символами. Далее задаются ГРАММАТИЧЕСКИЕ ПРАВИЛА. Они очень напоминают подстановки в алгорифмах Маркова. Но в отличие от последних порядок применения грамматических правил произвольный. Применение правила заключается в замене в преобразуемой строке какой-то последовательности символов, совпадающей с левой частью какого-то правила, правой частью (последовательностью символов) этого правила.

Введем в оборот из чисто эстетических соображений еще один красивый термин – СЕНТЕНЦИАЛЬНАЯ ФОРМА. Дело в том, что при построении программ в формальных грамматиках всегда танцуют от одного начального нетерминального символа. Обозначим этот символ «программа». Вместо этого символа по одному из грамматических правил происходит подстановка соответствующей правой части, которая может содержать последовательность из каких-то нетерминальных и терминальных символов. Кстати, такой процесс называется НЕПОСРЕДСТВЕННЫМ ПОРОЖДЕНИЕМ. Любой их появившихся нетерминальных символов может быть заменен по подходящему грамматическому правилу какой-то цепочкой символов. То есть начальный нетерминальный символ «программа» последовательно превращается во все более длинную цепочку символов. И так вплоть до того момента, когда в последовательности символов останутся только терминальные символы. То есть будет получено слово данного языка (по иронии судьбы называемое ПРЕДЛОЖЕНИЕМ). Все последовательности символов, которые в процессе непосредственных порождений находятся между начальным нетерминальным символом и конечным предложением и называются сентенциальными формами. А нам остается радоваться, что английский язык нам неродной.