Машина Тьюринга. Пример 10.4

Машина Тьюринга — это формальная система, порождающая огромное количество собственных конфигураций. Начальным объектом является исходная конфигурация; правилами — многофункциональная таблица. Но ранее была подтверждена эквивалентность представления алгоритмов в разных алгоритмических моделях. Как следует, если метод в представлении машины Тьюринга является формальной системой, то и метод в любом другом представлении также оказывается формальной системой. Совместно с тем, оборотное утверждение («любая формальная система является алгоритмом») будет неправильным — причина данного происшествия прояснится при обсуждении параметров формальных систем.

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

1) Дискретность. Это свойство формальных систем проявляется, во-1-х, в том, что составляющие системы состоят из неразделимых частей (объектов); во-2-х, в том, что число правил построения новых объектов из имеющихся естественно.

2) Формальность. Сущность формального подхода состоит в выполнении (соблюдении) ряда принципов:

• принцип педантизма: все, что делается — делается строго по правилам формальной системы. Если формальная система не позволяет выстроить желаемые объекты в рамках имеющихся правил, то вести построение, нарушая правила, нельзя. Можно поменять имеющиеся правила либо ввести новые, но это эквивалентно построению другой формальной системы;
• принцип очевидного описания: все условия внедрения правил и деяния, которые необходимо совершить при их применении, формулируются очевидно. В формулировках и описаниях действий не должны употребляться познания и опыт исполнителя либо «действия по умолчанию», т.е. что-то не описанное очевидно, но подразумевающееся. На практике выстроить такое серьезное описание если и удается, то оно оказывается очень массивным. Но вести его строго и поочередно оказывается необязательным: если исполнителем является человек, можно нужные познания поначалу ему передать, а потом на их опираться; если исполнитель — устройство, детальность описания определяется имеющейся системой команд.
• принцип синтаксичности: условия внедрения правил формулируются только при помощи чисто наружных и верно различимых признаков тех объектов, к которым эти правила используются (вот поэтому принципиальна дискретность — различия не должны быть малыми до неразличимости). По другому говоря, чтоб использовать правила, довольно уметь различать только наружные характеристики объектов: их элементный состав (знаки, фигуры и пр.) и их обоюдное размещение. Такие характеристики в теории формальных систем именуются синтаксическими. Потому принципу можно дать иную формулировку: объекты числятся разными, если и только если они различны синтаксически, т.е. имеют разный внешний облик. При таком подходе отпадает необходимость в понятиях «существенные различия» и «несущественные различия» — они или есть — тогда и это различные объекты, или их нет — тогда объекты схожи. Отсутствует и понятие внутренних различий, не имеющих очевидных наружных проявлений «злой — добрый», «полый — сплошной», «со сложным внутренним строением — с обычным строением». Конкретно принцип синтаксичности позволяет производить синтаксический анализа предъявленного текста. Синтаксически верный текст — это текст, выводимый в данной формальной грамматике, а хоть какой текст, содержащий синтаксические ошибки, не выводим. Таковой анализ осуществляется при трансляции компьютерной программки с языка программирования в машинные коды.

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

• подмена пустого элемента (т.е. места, где согласно правилам элемент может быть, но отсутствует) непустым элементом, что эквивалентно возникновению элемента рядом с имеющимися;
• подмена 1-го элемента другим (либо группой других);
• удаление элемента (т.е. подмена его пустым элементом).

Любые деяния из системы команд исполнителя в конечном счете могут быть сведены к обозначенным простым, что было показано в теории алгоритмов.

4) Необязательность детерминизма. Это свойство заключается в том, что на каждом шаге процесса построения новых объектов в общем случае применимо не одно правило, а несколько, и, как следует, последующий шаг выбирается из нескольких вероятных. В этом и состоит отличие формальных систем от алгоритмов, в каких хоть какому порождаемому объекту применимо только одно правило (это свойство детерминированности метода), что обеспечивает однозначность работы и результата метода. Будет справедливым утверждение, что формальная система с единственным правилом на каждом шаге функционирования является методом, и, как следует, формальная система является более общим понятием, чем метод, а метод можно считать личным случаем формальной системы. В формальной системе на каждом шаге либо неких шагах оказывается вероятным применение разных правил (это видно из рассмотренных выше примеров — шахматной игры либо построения формул), что обеспечивает порождение ни 1-го результата (как в методе), а огромного количества результатов (к примеру, огромное количество вариантов игры в шахматы либо огромное количество арифметических формул).

Относительно рассмотренных общих параметров формальных систем нужно сделать еще ряд замечаний.

Формальная система работает строго по своим правилам и различает свои объекты только по синтаксическим признакам. С этой точки зрения она совершенно точно задает некую математическую модель. Но при использовании этой модели для решения какой-нибудь задачки, элементам формальной системы присваиваются определенные характеристики и признаки, т.е. происходит интерпретация системы. Схожий механизм обширно применяется в программировании: разрабатывается процедура, обеспечивающая выполнение некой последовательности действий по обработке данных с формальными параметрами (т.е. задается схема, последовательность обработки), а потом при вызове процедуры заместо формальных делается подстановка фактических значений. Одна и та же формальная система может иметь разные интерпретации, зависящие от предметной области, в какой употребляется модель, или от целей, для которых она создавалась. К примеру, для формальной системы, описывающей законы математической логики, имеется другая интерпретация — правила функционирования логических схем, о чем шла речь ранее.

Интерпретация является наружной процедурой по отношению к формальной системе и в рамках самой системы не дискуссируется. Уровень интерпретации — его именуют метауровнем — может быть как формализованным, так и неформальным. На метауровне система становится уже не средством решения задачки, а объектом исследования. К примеру, формальная система, описывающая правила игры в шахматы, позволяет отличить правильные шахматные ходы от некорректных, но в ее рамках нереально отличить отличные ходы от нехороших. Вопрос об оценке свойства хода решается не в системе, а на метауровне. При этом, может быть неформальное решение — на базе опыта и мастерства игрока, также шахматной теории (которая является обобщением опыта многих шахматистов); вероятна и формальная интерпретация оценки свойства хода, которую делают и потом закладывают в шахматные компьютерные программки их разработчики. Точно также при компиляции компьютерных программ осуществляется их синтаксический контроль, т.е. проверка соответствия правилам формальной грамматики, но, компилятор не может отличить неплохую (в смысле эффективности выполнения) программку от нехороший.