Необходимость содержательной теории алгоритмов. Какой она должна быть

Мы уделили целую главу этой небольшой книги обсуж­дению ЭВМ потому, что хотели выяснить, какие требова­ния предъявляет практика к теории алгоритмов. И обнаружили то, что и ожидали. Ни одна из традиционных тео­рий алгоритмов не может обслуживать такую область тех­ники и науки как ЭВМ и программирование. Правда, зна­ние традиционных теорий алгоритмов нам в определенной степени «открывает глаза», позволяет понимать, что про­граммирование — это прикладная область теории алгорит­мов.

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

Практика ставит задачу создания науки об алгорит­мах, а не аппарата для обоснования математики и реше­ния некоторых проблем математической логики. Мы с вами интересуемся не только практикой, но и теорией и логи­кой, уважаем логику, но хотим иметь свою теорию. Эта тео­рия алгоритмов должна изучать алгоритмы как таковые. Она должна дать практически осуществимые методы по­строения алгоритмов. Конечно, убедиться, что та или иная задача не является алгоритмически неразрешимой пробле­мой, очень полезно. Но в большинстве случаев это сделать не очень трудно. Хотя бы потому, что наши массовые проб­лемы, как правило, содержат, может быть, и чрезвычайно большое, но конечное число одиночных проблем. Правда, и такие проблемы могут быть неразрешимыми (например, проблема оценки каталога всех каталогов библиотеки, со­стоящей из 1000 книг, см. § 4 гл. 3). Но все же иметь дело с конечной массовой проблемой куда легче, чем с беско­нечной. Итак, не будем отказываться от традиционных теорий алгоритмов, но скажем: этого мало!

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

Поскольку мы должны применять ЭВМ в самых раз­личных областях науки и техники, то должны с помощью теории алгоритмов обнаруживать алгоритмы, действующие в этих областях, и уметь строить программы, реализую­щие их.

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

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

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

Вот эта «дьявольская» массовая проблема: найти общий метод определения количества символов, из которых об­разовано непустое буквенное «кольцо» (замкнутая цепочка букв) в алфавите, состоящем из одной буквы | (палоч­ки).

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

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

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

Содержательная теория алгоритмов подготовлена уси­лиями многих программистов — практиков и теоретиков, но стала она возможной благодаря основополагающим ра­ботам математиков, создавших традиционные теории алго­ритмов. Многие математики уже трудятся над проблемами содержательной теории алгоритмов. В добрый час!