Установить нижнюю оценку – значит доказать, что никакой алгоритм вычисления не имеет сложности меньшей, чем заданная граница. Для получения результатов такого типа необходима точная фиксация рассматриваемой алгоритмической модели, и такие результаты получены только в очень жестких вычислительных моделях. В связи с этим получила развитие проблематика получения «относительных» нижних оценок, так называемая теория NP-полноты, связанная с трудной решаемостью переборных задач.
В результате продолжительных теоретических и практических изысканий были сформулированы основные требования к алгоритмам:
1. Каждый алгоритм имеет дело с данными – входными, промежуточными, выходными. Для того чтобы уточнить понятие данных, фиксируется конечный алфавит исходных символов (цифры, буквы и т.п.) и указываются правила построения алгоритмических объектов. Типичным используемым средством является индуктивное построение. Например, определение идентификатора во многих алгоритмических языках: идентификатор – это либо буква, либо идентификатор, к которому приписана справа либо буква, либо цифра. Слова конечной длины в конечных алфавитах – наиболее обычный тип алгоритмических данных, а число символов в слове – естественная мера объема данных. Другой случай алгоритмических объектов – формулы. Примером могут служить формулы алгебры предикатов и алгебры высказываний.
2. Алгоритм для размещения данных требует памяти. Память обычно считается однородной и дискретной, т.е. она состоит из одинаковых ячеек, причем каждая ячейка может содержать один символ данных, что позволяет согласовать единицы измерения объема данных и памяти.
3. Алгоритм состоит из отдельных элементарных шагов, причем множество различных шагов, из которых составлен алгоритм, конечно. Типичный пример множества элементарных шагов – система команд ЭВМ.
4. Последовательность шагов алгоритма детерминирована, то есть после каждого шага указывается, какой шаг следует выполнять дальше, либо указывается, когда следует работу алгоритма считать законченной.
5. Алгоритм должен обладать результативностью, то есть останавливаться после конечного числа шагов (зависящего от исходных данных) с выдачей результата. Данное свойство иногда называют сходимостью алгоритма.
6. Алгоритм предполагает наличие механизма реализации, который по описанию алгоритма порождает процесс вычисления на основе исходных данных. Предполагается, что описание алгоритма и механизм его реализации конечны.
Можно заметить аналогию с вычислительными машинами. Требование 1 соответствует цифровой природе ЭВМ, требование 2 – памяти ЭВМ, требование 3 – программе машины, требование 4 – её логической природе, требования 5, 6 – вычислительному устройству и его возможностям.
Имеются также некоторые черты неформального понятия алгоритма, относительно которых не достигнуто окончательного соглашения. Эти черты можно сформулировать в виде вопросов и ответов.
1. Следует ли фиксировать конечную границу для размера входных данных?
2. Следует ли фиксировать конечную границу для числа элементарных шагов?
3. Следует ли фиксировать конечную границу для размера памяти?
4. Следует ли ограничить число шагов вычисления?
На все эти вопросы далее принимается ответ «НЕТ», хотя возможны и другие варианты ответов, поскольку у физически существующих ЭВМ соответствующие размеры ограничены. Однако теория, изучающая алгоритмические вычисления, осуществимые в принципе, не должна считаться с такого рода ограничениями, поскольку они преодолимы, по крайней мере, в принципе (например, любой фиксированный размер памяти всегда можно увеличить на одну ячейку).
Таким образом, уточнение понятия алгоритма связано с уточнением алфавита данных и формы их представления, памяти и размещения в ней данных, элементарных шагов алгоритма и механизма реализации алгоритма. Однако эти понятия сами нуждаются в уточнении. Ясно, что их словесные определения потребуют введения новых понятий, для которых, в свою очередь, снова потребуются уточнения и т.д. Поэтому в теории алгоритмов принят другой подход, основанный на конкретной алгоритмической модели, в которой все сформулированные требования выполняются очевидным образом. При этом используемые алгоритмические модели универсальны, то есть моделируют любые другие разумные алгоритмические модели, что позволяет снять возможное возражение против такого подхода: не приводит ли жесткая фиксация алгоритмической модели к потере общности формализации алгоритма? Поэтому данные алгоритмические модели отождествляются с формальным понятием алгоритма.
Всякому алгоритму соответствует задача, для решения которой он был построен. Обратное утверждение в общем случае является неверным по двум причинам: во-первых, одна и та же задача может решаться различными алгоритмами; во-вторых, можно предположить (пока), что имеются задачи, для которых алгоритм вообще не может быть построен.
Как уже отмечалось, термин «алгоритм» появился в математике достаточно давно и использовался долго – под ним понималась процедура, позволявшая путем выполнения последовательности определенных элементарных шагов получать однозначный результат, не зависящий от того, кто эти шаги выполнял. Таким образом, само проведенное решение служило доказательством существования алгоритма. Однако был известен целый ряд математических задач, разрешить которые в общем виде не удавалось. Примерами могут послужить три древние геометрические задачи: о трисекции угла, о квадратуре круга и об удвоении куба – ни одна из них не имеет общего способа решения с помощью циркуля и линейки без делений.
Интерес математиков к задачам подобного рода привел к постановке вопроса: возможно ли, не решая задачи, доказать, что она алгоритмически неразрешима, т.е. что нельзя построить алгоритм, который обеспечил бы ее общее решение? Ответ на этот вопрос важен, в том числе и с практической точки зрения, например, бессмысленно пытаться решать задачу на компьютере и разрабатывать для нее программу, если доказано, что она алгоритмически неразрешима. Именно для ответа на данный вопрос и понадобилось сначала дать строгое определение алгоритма, без чего обсуждение его существования просто не имело смысла. Построение такого определения, как мы знаем, привело к появлению формальных алгоритмических систем, что дало возможность математического доказательства неразрешимости ряда проблем. Оно сводится к доказательству невозможности построения рекурсивной функции, решающей задачу, либо к невозможности построения машины Тьюринга для нее, либо несостоятельности любой другой модели. То есть задача считается алгоритмически неразрешимой, если не существует машины Тьюринга (или рекурсивной функции, или нормального алгоритма Маркова), которая ее решает.
Первые доказательства алгоритмической неразрешимости касались некоторых вопросов логики и самой теории алгоритмов. Оказалось, например, что неразрешима задача установления истинности произвольной формулы исчисления предикатов – эта теорема была доказана в 1936 г. Чёрчем.
В 1946-47 гг. А.А. Марков и Э. Пост независимо друг от друга доказали отсутствие алгоритма для распознавания эквивалентности слов в любом ассоциативном исчислении.
В теории алгоритмов к алгоритмически неразрешимой относится «проблема остановки»: можно ли по описанию алгоритма (Q) и входным данным (x) установить, завершится ли выполнение алгоритма результативной остановкой? Эта проблема имеет прозрачную программистскую интерпретацию. Часто ошибки разработки программы приводят к зацикливанию – ситуации, когда цикл не завершается и не происходит завершения работы программы и остановки. Неразрешимость проблемы остановки означает, что нельзя создать общий, пригодный для любой программы алгоритм отладки программ. Неразрешимой оказывается и проблема распознавания эквивалентности алгоритмов: нельзя построить алгоритм, который для любых двух алгоритмов выяснял бы, всегда ли они приводят к одному и тому же результату или нет.
Важность доказательства алгоритмической неразрешимости в том, что если такое доказательство получено, оно имеет смысл закона-запрета, позволяющего не тратить усилия на поиск решения, подобно тому, как законы сохранения в физике делают бессмысленными попытки построения вечного двигателя. Вместе с этим необходимо сознавать, что алгоритмическая неразрешимость какой-либо задачи в общей постановке не исключает возможности того, что разрешимы какие-то её частные случаи. Справедливо и обратное утверждение: решение частного случая задачи еще не дает повода считать возможным её решения в самом общем случае, т.е. не свидетельствует об ее общей алгоритмической разрешимости.
Роль абстрактных алгоритмических систем в том, что именно они позволяют оценить возможность нахождения общего решения некоторого класса задач. Для специалиста в области информатики важно сознавать, что наличие алгоритмически неразрешимых проблем приводит к тому, что оказывается невозможным построить универсальный алгоритм, пригодный для решения любой задачи. К подобным проблемам приводят и попытки алгоритмизировать сложную интеллектуальную деятельность человека, например, обучение других людей, сочинение стихов и пр.
Понятие, в особенности частично рекурсивной функции, является одним из главных понятий теории алгоритмов. Значение его состоит в следующем. С одной стороны, каждая стандартно заданная частично рекурсивная функция вычислима путем некоторой процедуры механического характера, отвечающей интуитивному представлению об алгоритмах. С другой стороны, какие бы классы точно очерченных алгоритмов ни строились, во всех случаях неизменно оказывалось, что вычислимые посредством них числовые функции являлись частично рекурсивными. Поэтому общепринятой является научная гипотеза, формулируемая как тезис Чёрча: «Класс осуществляемых операций, попадающих, таким образом, под определение «алгоритма» (или «вычисления», или «выполнимой процедуры», или «рекурсивной операции»), остался бы в точности тем же самым, если мы расширим определение наших машин...».