- 629 -
любой алгоритм, если на ее ленту, кроме исходных данных, записана соответствующая программа. Таким образом, интуитивное понятие алгоритма получает точное определение как процесс, который может быть представлен функциональной схемой и реализован машиной Тьюринга.
9. Алгоритмическая разрешимость. После того как понятие алгоритма получило точное определение, вопрос об алгоритмической разрешимости того или иного класса задач ставится совершенно определенно: существует ли какая-либо стандартная форма алгоритма, решающая данный класс задач? В ряде случаев на этот вопрос теория алгоритмов дает отрицательный ответ.
В специальных разделах математики строго доказана неразрешимость ряда задач, например невозможность решения в радикалах алгебраических уравнений выше четвертой степени, невозможность трисекции угла с помощью циркуля и линейки и т.п. Отличительная особенность теории алгоритмов состоит в том, что она испытывает на разрешимость наиболее общие проблемы.
Пробным камнем теории алгоритмов явилась проблема распознавания выводимости: для любых двух формул R и S в логическим исчислении узнать, существует ли дедуктивная цепочка, ведущая от R к S, или же такой цепочки не существует. Оказалось, что эта проблема алгоритмически неразрешима. Отрицательный ответ получен и для проблемы распознавания эквивалентности слов в любом ассоциативном исчислении. Были построены конкретные примеры ассоциативных исчислений, в которых- не существует алгоритма, позволяющего для любой пары слов установить, эквиваленты они или нет. Простейший пример такого исчисления приведен в (5).
Алгоритмическую неразрешимость следует понимать в том смысле, что не существует единого алгоритма для решения проблемы в целом. Но это вовсе не означает неразрешимость более узких классов задач данной проблемы. Так, несмотря на алгоритмическую неразрешимость проблемы распознавания выводимости, по существу вся математика представляет собой дедуктивную науку, в которой в качестве основного метода доказательства используется выводимость теорем из некоторой совокупности аксиом.
Не следует смешивать алгоритмическую неразрешимость какой-либо проблемы с положением, в котором находятся еще нерешенные проблемы. Если для нерешенных проблем остается хоть какая-нибудь надежда найти разрешающий алгоритм, то алгоритмическая неразрешимость раз и навсегда ставит точку над всякими попытками поиска такого алгоритма, поскольку бессмысленно искать то, чего не существует.
- 630 -
С точки зрения инженерной практики проблема алгоритмической разрешимости выглядит совсем иначе, чем с позиций самой математики. В силу конечности реального времени, отводимого на решение задачи, и ограниченных возможностей средств вычислительной техники (производительность и память) даже простые алгоритмы могут оказаться практически не реализуемыми, если они требуют выполнения слишком большого числа операций. Типичными примерами являются задачи выбора оптимальных вариантов при проектировании, игровые задачи и алгоритмы, основанные на простом перебор и т.п. В то же время алгоритмическая неразрешимость проблемы в целом не является препятствием для решения частных задач, относящихся к этой проблеме. Так, среди алгебраических уравнений выше четвертой степени могут оказаться такие, которые решаются не только в радикалах, но и в целых числах. Более того, можно определить корни уравнения с достаточной для практики степенью приближения, вовсе отказавшись от стремления найти решение в радикалах.
Аналогичный подход выработала практика и к задачам, которые относятся к нерешенным проблемам. Например, до сих пор не найден общий алгоритм раскраски граней любого плоского графа не больше чем четырьмя различными цветами так, чтобы никакие соседние грани не были окрашены одинаковым цветом (в 1976 г. появилось сообщение о решении этой проблемы с помощью вычислительных машин, которое еще подлежит проверке). В то же время в реальных условиях еще не встречалось случаев, когда такая раскраска оказалась бы невозможной (эта задача возникает, например, при изготовлении географических карт). Можно предложить много различных способов, облегчающих решение конкретных задач этого типа. Однако ни один из них нельзя назвать алгоритмом, если он не гарантирует раскраску любого графа. В отличие от алгоритмов, практические способы, используемые для решения таких задач, относящихся к нерешенным проблемам, называют псевдоалгоритмами.
10. Прикладная теория алгоритмов. Стандартные формы представления алгоритмов, подобные нормальному алгоритму Маркова, в силу их чрезвычайно высокой степени детализации непригодны для инженерной практики. Машина Тьюринга является удобной абстрактной моделью реализации любого алгоритма человеком или вычислительной машиной, но в реальных условиях любой вид памяти и время функционирования жестко ограничены. В то же время при разработке и реализации конкретных алгоритмов в инженерной практике достаточно исходить из их общих свойств, сформулированных в (4).