Пример 10.4
Машина Тьюринга - это формальная система, порождающая множество своих конфигураций. Исходным объектом является начальная конфигурация; правилами - функциональная таблица. Однако ранее (гл. 7) была доказана эквивалентность представления алгоритмов в различных алгоритмических моделях. Следовательно, если алгоритм в представлении машины Тьюринга является формальной системой, то и алгоритм в любом другом представлении также оказывается формальной системой. Вместе с тем, обратное утверждение («любая формальная система является алгоритмом») будет неверным - причина данного обстоятельства прояснится при обсуждении свойств формальных систем. Приведенные примеры показывают, что формальные системы весьма разнообразны. Однако, как и в случае алгоритмов, можно выделить ряд общих свойств, которыми обладают все формальные системы. 1) Дискретность. Это свойство формальных систем проявляется, во-первых, в том, что компоненты системы состоят из неделимых элементов (объектов); во-вторых, в том, что число правил построения новых объектов из имеющихся конечно. 2) Формальность. Суть формального подхода состоит в выполнении (соблюдении) ряда принципов: · принцип педантизма: все, что делается - делается строго по правилам формальной системы. Если формальная система не позволяет построить желаемые объекты в рамках имеющихся правил, то вести построение, нарушая правила, нельзя. Можно изменить имеющиеся правила или ввести новые, но это эквивалентно построению другой формальной системы; · принцип явного описания: все условия применения правил и действия, которые нужно совершить при их применении, формулируются явно. В формулировках и описаниях действий не должны использоваться знания и опыт исполнителя или «действия по умолчанию», т.е. что-то не описанное явно, но подразумевающееся. На практике построить такое строгое описание если и удается, то оно оказывается весьма громоздким. Однако вести его строго и последовательно оказывается необязательным: если исполнителем является человек, можно необходимые знания сначала ему передать, а затем на них опираться; если исполнитель - устройство, детальность описания определяется имеющейся системой команд. · принцип синтаксичности: условия применения правил формулируются только с помощью чисто внешних и четко различимых признаков тех объектов, к которым эти правила применяются (именно поэтому важна дискретность - различия не должны быть малыми до неразличимости). Иначе говоря, чтобы применять правила, достаточно уметь различать только внешние свойства объектов: их элементный состав (символы, фигуры и пр.) и их взаимное расположение. Такие свойства в теории формальных систем называются синтаксическими. Поэтому принципу можно дать иную формулировку: объекты считаются различными, если и только если они различны синтаксически, т.е. имеют различный внешний вид. При таком подходе отпадает необходимость в понятиях «существенные различия» и «несущественные различия» - они либо есть - и тогда это разные объекты, либо их нет - тогда объекты идентичны. Отсутствует и понятие внутренних различий, не имеющих явных внешних проявлений «злой - добрый», «полый - сплошной», «со сложным внутренним строением - с простым строением». Именно принцип синтаксичности позволяет осуществлять синтаксический анализа предъявленного текста. Синтаксически правильный текст - это текст, выводимый в данной формальной грамматике, а любой текст, содержащий синтаксические ошибки, не выводим. Такой анализ осуществляется при трансляции компьютерной программы с языка программирования в машинные коды. 3) Элементарность действий. Речь идет о том, что хотя правила формальной системы могут иметь самый разнообразный вид, однако любое сложное правило может быть сведено к последовательности простых комбинаторных манипуляций с элементами системы, носящих число механический характер. В теории алгоритмов уже обсуждались эти манипуляции; в приложении к формальным системам это порождает следующий набор элементарных действий: · замена пустого элемента (т.е. места, где согласно правилам элемент может быть, но отсутствует) непустым элементом, что эквивалентно появлению элемента рядом с имеющимися; · замена одного элемента другим (или группой других); · удаление элемента (т.е. замена его пустым элементом). Любые действия из системы команд исполнителя в конечном счете могут быть сведены к указанным элементарным, что было показано в теории алгоритмов. 4) Необязательность детерминизма. Это свойство состоит в том, что на каждом шаге процесса построения новых объектов в общем случае применимо не одно правило, а несколько, и, следовательно, следующий шаг выбирается из нескольких возможных. В этом и состоит отличие формальных систем от алгоритмов, в которых любому порождаемому объекту применимо только одно правило (это свойство детерминированности алгоритма), что обеспечивает однозначность работы и результата алгоритма. Будет справедливым утверждение, что формальная система с единственным правилом на каждом шаге функционирования является алгоритмом, и, следовательно, формальная система является более общим понятием, чем алгоритм, а алгоритм можно считать частным случаем формальной системы. В формальной системе на каждом шаге или некоторых шагах оказывается возможным применение различных правил (это видно из рассмотренных выше примеров - шахматной игры или построения формул), что обеспечивает порождение ни одного результата (как в алгоритме), а множества результатов (например, множество вариантов игры в шахматы или множество арифметических формул). Относительно рассмотренных общих свойств формальных систем необходимо сделать еще ряд замечаний. Формальная система функционирует строго по своим правилам и различает свои объекты только по синтаксическим признакам. С этой точки зрения она однозначно задает некоторую математическую модель. Но при использовании этой модели для решения какой-либо задачи, элементам формальной системы присваиваются конкретные свойства и признаки, т.е. происходит интерпретация системы. Подобный механизм широко применяется в программировании: разрабатывается процедура, обеспечивающая выполнение некоторой последовательности действий по обработке данных с формальными параметрами (т.е. задается схема, последовательность обработки), а затем при вызове процедуры вместо формальных производится подстановка фактических значений. Одна и та же формальная система может иметь различные интерпретации, зависящие от предметной области, в которой используется модель, либо от целей, для которых она создавалась. Например, для формальной системы, описывающей законы математической логики, имеется иная интерпретация - правила функционирования логических схем, о чем шла речь ранее. Интерпретация является внешней процедурой по отношению к формальной системе и в рамках самой системы не обсуждается. Уровень интерпретации - его называют метауровнем - может быть как формализованным, так и неформальным. На метауровне система становится уже не средством решения задачи, а объектом изучения. Например, формальная система, описывающая правила игры в шахматы, позволяет отличить правильные шахматные ходы от неправильных, но в ее рамках невозможно отличить хорошие ходы от плохих. Вопрос об оценке качества хода решается не в системе, а на метауровне. Причем, возможно неформальное решение - на основе опыта и мастерства игрока, а также шахматной теории (которая является обобщением опыта многих шахматистов); возможна и формальная интерпретация оценки качества хода, которую создают и затем закладывают в шахматные компьютерные программы их разработчики. Точно также при компиляции компьютерных программ осуществляется их синтаксический контроль, т.е. проверка соответствия правилам формальной грамматики, однако, компилятор не может отличить хорошую (в смысле эффективности исполнения) программу от плохой. |
5822
5417