Дискретная математика без формул

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

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

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

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

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

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

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

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

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

Собственно алгоритм в нормальных алгорифмах задается

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

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

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

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

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

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

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

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