3.8. Прописные истины теории алгоритмов

По прочтении глав, касающихся анализа и проектирования программ, у читателя должно сложиться мнение, что программирование – скорее ремесло с набором известных рекомендаций и приемов, нежели точная наука. Формальные методы касаются только некоторых частностей, например, оценки производительности (трудоемкости), обоснования правильности программ. Тем не менее, существует такая отрасль математики как теория алгоритмов, которая возникла еще до появления компьютеров. Возникает резонный вопрос: какое отношение имеет теория алгоритмов к практике программирования?

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

«Если у Вас есть компьютер, займитесь прикладным программированием. Если же у Вас его нет, займитесь теоретическим. Почаще рассуждайте: если бы у меня был компьютер, то…» Перефразированная старая шутка из «Комсомольской правды».

Основные выводы теории алгоритмов для программистов-практиков лежат в области «само собой разумеющегося». Для начинающих, а тем более для неспециалистов, самоучек и дилетантов такое незнание может быть основой для заблуждений относительно возможностей компьютерных программ. В результате в лучшем случае мы имеем напрасно потраченное время на решение заведомо неразрешимых проблем, а в худшем случае – неосознанное введение в заблуждение общественного мнения. Итак, наши задачи - низвести основные выводы теории алгоритмов «с небес на грешную землю», а также дать «научную» интерпретацию с точки зрения теории алгоритмов очевидных фактов, известных программистам-практикам.

Алгоритмически неразрешимые проблемы

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

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

Теорема Райса

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

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

Анализ программ. Слово теории алгоритмов

Анализ программы состоит в определении того, что является ее результатом. Это может быть сформулировано как содержательно (например, программа «переворачивает» слова), так и формально, как свойства выходных данных (например, программа сортировки создает упорядоченный массив, свойство возрастания элементов в котором может быть определено формально). Опять же результат программы является нетривиальным ее свойством, поэтому такая задача является в общем виде алгоритмически неразрешимой.

Тем не менее, мы уже рассматривали способы анализа программ: «исторический» и логический, а также их комбинирование для анализа конкретных программ. Здесь, как и везде, не существует общего метода: программист каждый раз идет своим путем.

Кроме того, логический анализ (разложение программы на фрагменты с известным результатом) и «исторический» (временной) анализ, являются предварительной фазой, дающей «пищу для ума». Далее в дело вступают опыт, интуиция и тому подобные вещи:

• закономерности изменения данных, ведущих к результату можно непосредственно уловить или «увидеть» в процессе «исторического анализа» при непосредственном наблюдении за ходом выполнения программы (интуиция);

• подобные решения уже встречались в практике программирования, возможно, в другом контексте, в других условиях, других структурах данных (опыт, аналогия);

• возможно сделать предположение о результате работы программы, либо область приложения ее результатов заранее известна (знание предметной области, известных решений, опыт).

Очевидно, что все таким образом сделанные предположения носят гипотетический характер и нуждаются если не в доказательстве, то хотя бы в обосновании. Обычно это делается полуформально: полученные при логическом анализе фрагменты программы с известными результатами при их «историческом» взаимодействии во времени должны подтверждать или опровергать гипотезу.

Фазы анализа: 1. сбор данных: логический и «исторический» анализ 2. Гипотеза о результате 3. Обоснование или доказательство

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

Утверждение. Невозможно построить алгоритм, который по тексту программы определяет что она делает.

Следствие. По тексту программы нельзя ничего сказать о характере программиста, ее написавшего.

Проектирование программ. Слово теории алгоритмов

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

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

Отладка программы. Слово теории алгоритмов

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

С учетом предложенного деления на «правильные» и «неправильные» программы процесс отладки выглядит так: программист имеет в компьютере «неправильную» программу, а у себя в голове – идеальный «правильный» вариант. Отладка заключается в наблюдении за поведением программы (для этого существуют отладчики, в сущности, одинаковые во всех системах программирования: пошаговое или поэтапное выполнение программы со слежением за состоянием ее переменных). В месте обнаружения отклонения результатов выполнения от «идеальных» находится ошибка. Поэтому одним из основных этапов отладки является локализация ошибки. Некоторые рекомендации по этому поводу:

• сужение интервала поиска. Ошибка локализуется последовательным сужением интервала между двумя точками программы, где она «еще работает» и «уже не работает»;

• исходные данные для отладки следует выбирать настолько простыми и ограниченными по объему, чтобы их изменением ними можно было отследить вручную. Однако они не должны быть «вырожденными», то есть они должны содержать комбинации, существенные для логики работы программы;

• метод проб и ошибок предполагает проведение «экспериментов» над программой с различными входными данными с целью установления закономерности появления ошибки.

С точки зрения «приближения к идеалу» ошибки можно разделить на группы по степени их «влияния» на текст программы:

• «очепятки» исправляются заменой имени переменной (значения константы, операции) на правильную;

• «недоразумения» предполагают, что программист не учел некоторые нюансы или частные случаи (например, крайнюю ситуацию), что исправляется локальной коррекцией логики работы фрагмента программы;

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

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

езюме: Перефразируя Евангелие: Итак, отдайте же Богу богово, а процессору – процессорово. Все этапы программирования: анализ, разработка и отладка программ сочетают в себе интуитивно-образный и формально-логический подходы. Отдельные частные проблемы могут быть алгоритмически разрешимы и программируемы. В общем же виде решение таких задач является прерогативой человека, а не компьютера.

Эквивалентность языков программирования

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

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

 Аналог проблемы «яйцо-курица». Если компилятор с языка Си написан на самом Си, то для получения его в машинном коде необходимо откомпилировать исходный текст Си-компилятора при помощи компилятора, уже имеющегося в машинном коде, для получения которого… необходим еще один компилятор и т.д. до бесконечности. Аналогично с операционной системой. Если ядро операционной системы написано на Си, то к замкнутому кругу Си-компиляторов добавляется условие работы этого компилятора в среде операционной системы, которая еще не оттранслирована, и, следовательно, не выполняется. К сожалению, объяснение проблем «раскрутки» и переноса операционных систем и систем программирования выходит за рамки этой книги.

Программа = алгоритм + данные

 Алгоритм и данные – это «Янь и Инь» программирования. Это утверждение не притянуто «за уши», как может показаться. Во многих философских системах в качестве одного из важнейших элементов устройства мироздания рассматривается единство и борьба противоположных начал (диалектическое единство):

• каждое начало является отдельной независимой сущностью, но каждое из них не существует без своей противоположности;

• их противоположность является причиной постоянного взаимопроникновения, противоречия и борьбы;

• тем не менее, в каждом из начал присутствует его противоположность;

• борьба противоположных начал обуславливает развитие, движение системы в целом.

Символ древнекитайской философии «Янь и Инь» несет в себе всё перечисленное (попробуйте найти самостоятельно). Попробуем найти

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

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

Что первично? В связке двух противоположных начал можно выделить ведущее (первичное) и ведомое (вторичное). Как уже отмечалось, алгоритмическая компонента программы первична уже в силу исторических причин: традиционная компьютерная архитектура базируется на идее исполнения последовательности команд, содержащих адреса данных (операндов). Аналогично в классическом (структурном) программировании единицей программного кода является функция, а сущность технологии программирования выражается фразой «программирование от функции к функции». При этом данные, передаваемые от функции к функции, являются вторичным (ведомым) элементом. Поэтому по тексту программы всегда легче отследить последовательность выполняемых операций, нежели взаимосвязь различных данных (переменных).

Технология объектно-ориентированного программирования частично уравняла алгоритм и данные, объединив их в рамках одного класса. Аналогично, процесс выполнения программы выглядит как «объект-метод-объект…», в которой обе противоположности чередуются.

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

Сокращение алгоритмической компоненты возможно не только в прикладном программировании. Универсальность алгоритмической компоненты, независимость ее от типов обрабатываемых данных (полиморфизм) и структур данных – это технологические компоненты, встроенные в современные системы программирования, которые обеспечивают тот же самый эффект за счет внутренней организации систем программирования. Например, виртуальные (полиморфные) методы, известные в технологии объектно-ориентированного программирования, можно промоделировать в обычной технологии с помощью операторов-переключаетелей (switch). Реальный же механизм базируется на массивах указателей на функции, т.е. на данных.

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

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

«Взаимозаменяемость» алгоритма и данных. Алгоритм и данные в какой-то степени аналогичны также категориям времени и пространства. Известное положение «выигрывая во времени, проигрываем в пространстве» применимо и в программировании. Производительность алгоритма может быть качественно увеличена при использовании дополнительных данных (дополнительной памяти) (см. например, 8.7. Динамическое программирование).

Аналитическое решение и моделирование. Программирование как имитация

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

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

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

• в формуле аналитического решения «заключен интеллект» математика, которой ее вывел;

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

Особенность программы – «воспроизводство» интеллекта программиста, заложенного в алгоритм.

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

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

Программы и их место в иерархии формальных систем

«Некоторые вещи нам непонятны не потому,
что понятия наши слабы, а потому что они 
не входят в круг наших понятий».

Козьма Прутков

Как мы видели, основное ограничение программ (на практике) и алгоритмов (в теории алгоритмов) состоит в самоприменимости: насколько возможны программы, анализирующие и производящие «программы вообще». На самом деле эта проблема не только теории алгоритмов и, как следствие, программ. Она касается ограниченности и замкнутости любой формальной системы: никакая формальная система не может содержать полное описание самой себя. Более точно это сформулировано в теоремах Гёделя о неполноте:

Теорема 1. В любой замкнутой формальной системе (теории) существует верная формула (утверждение), не доказуемая в этой теории.

Теорема 2. Формула (утверждение), выражающая непротиворечивость теории, не может быть доказана в этой теории: то есть любая теория не может содержать непротиворечивое (полное) описание самой себя.

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

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

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

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

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

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