Далеко не все задачи решаются алгоритмически или, как принято говорить в математике, конструктивно.
Обсудим теперь проблему разрешимости и неразрешимости с точки зрения машин Тьюринга, т. е. точного понятия алгоритма. Машина Тьюринга вычисляет значение некоторой функции натуральных аргументов, иначе говоря, каждая машина представляет некоторую функцию. Верно ли обратное: каждая функция может быть представлена некоторой машиной? Ответить на этот вопрос очень легко. Поскольку каждая машина однозначно задается своей программой, а программу можно записать как последовательность команд — строку конечной длины в конечном алфавите то имеем счетное количество строк, т. е. множество всех машин Тьюринга счетно. В то же время множество всех функций натуральных аргументов, дающих в качестве результата натуральные числа — несчетно!
Следовательно, существуют функции, не вычисляемые никакой машиной Тьюринга. Такие функции называются невычислимыми. Если теперь сказать, что вычисление функции — это решение задачи, а программа машины Тьюринга — алгоритм, то мы делаем вывод о существовании алгоритмически неразрешимых задач.
В теории алгоритмов известно много таких задач. Перечислим наиболее важные из них.
1. Проблема остановки. При обсуждении машин Тьюринга
было сказано, что на некоторых исходных данных машина может не останавливаться, т. е. не давать результата. Любая машина Тьюринга может быть представлена некоторым кодом (номером), отличающимся от всех других. Например, каждое состояние можно закодировать числом, символы движения за кодировать различными числами. Тогда каждая команда пред ставляет собой строку чисел, которую можно интерпретировать как одно большое число, а последовательность всех команд — как еще большее число N. Эта или какая-либо другая процедура устанавливает однозначное соответствие между множеством
натуральных чисел и множеством алгоритмов. Функция j : Natur —> Algorithmus, называется нумерацией алгоритмов, а ее аргумент N — номером алгоритма при нумерации j. Функция j по номеру N восстанавливает описание алгоритма, j (N) = а. Обратная функция по описанию алгоритма определяет его номер. Введение нумераций позволяет работать с алгоритмами как с натуральными числами, что особенно удобно при исследовании алгоритмов над алгоритмами: алгоритм, закодированный числом, может рассматриваться как входные данные другого алгоритма. Проблема остановки состоит в построении машины Тьюринга М, которая получая на входе код (номер) N произвольной машины Т и входные данные этой машины X, определяет, остановится ли машина Т на данных X. Иначе говоря,
M(N,X) = 1, если Т останавливается на X,
M(N,X) = О, если Т не останавливается на X.
Доказано, что машину М построить нельзя, т. е. проблема остановки алгоритмически неразрешима.
2. Проблема эквивалентности. Для вычисления одной и той
же функции можно построить две различные машины Тьюринга,
отличающиеся набором команд, а значит, и последовательностью действий. Тем не менее для любых исходных данных обе машины будут вычислять одинаковые результаты. Такие машины естественно считать эквивалентными. Проблема эквивалентности состоит в построении машины Тьюринга, получающей на входе описания (коды) двух машин Т1 и Т2 и определяющей, эквивалентны ли Т1 и Т2. С практической точки зрения можно поставить аналогичный вопрос: можно ли написать программу, которая по текстам двух программ на Паскале определяет, закончатся ли они одинаковыми результатами.
Ответ отрицательный — проблема эквивалентности алгоритмически неразрешима. Это не означает, что для двух конкретных программ нельзя выяснить, эквивалентны ли они. Просто не существует общего метода. Для каждой пары программ придется применять собственные методы, зависящие от существа этих программ.
Понятие вычислимой функции (т. е. той, для которой существует вычисляющая ее машина Тьюринга — алгоритм) и собственно алгоритма не следует смешивать. Различие между вычислимой функцией и алгоритмом — это различие между функцией и способом ее задания. Для одной и той же функции может существовать бесконечное число способов задания — текстов алгоритмов. Тривиальный пример: к тексту алгоритма, вычисляющего функцию, припишем текст тождественного алгоритма (результат которого всегда равен его входным данным); новый алгоритм представляет ту же самую функцию; теперь припишем текст тождественного алгоритма еще раз, затем еще раз; получим бесконечную последовательность различающихся алгоритмов, представляющих одну функцию. Подобные факты и порождают множество проблем в теории алгоритмов, связанных с разрешимостью. Существует даже теорема Раиса, утверждающая, что «никакое нетривиальное свойство вычислимых функций не является алгоритмически разрешимым».
Тривиальное свойство означает принадлежность функции либо множеству всех функций, либо пустому множеству. Нетривиальное свойство — «функция f принадлежит классу C», где С— такой непустой класс, что существуют функции, не принадлежащие ему. Нумерация всех алгоритмов является одновременно и нумерацией всех вычислимых функций: функции можно приписать номер одного из вычисляющих ее алгоритмов. Теперь теорему Раиса можно сформулировать иначе: «Не существует алгоритма, который по номеру функции f определял бы, принадлежит эта функция заданному классу С или нет».
Из изложенного видно, что проблема алгоритмической неразрешимости достаточно серьезна. На практике это означает, что если ставится проблема построения алгоритма, имеющего общий (универсальный) характер, например, автоматического синтеза программ по описанию произвольной задачи, то скорее всего такая проблема не может быть решена. Но если проблему ограничить, не ориентируясь на синтез программ для произвольных задач, а очертить более узкий круг задач и задать простые правила описания таких задач, то, вероятно, проблема может быть решена.