Множество всех алгоритмов счетно. Это означает наличие взаимно-однозначного соответствия между алгоритмами и числами натурального ряда, т.е. функции типа
: Al N
Такая функция называется нумерацией алгоритмов, а ее значение (А) – номером алгоритма А при нумерации. Из взаимной однозначности отображения следует, что существует обратная функция -1(n)= Аn, восстанавливающая по номеру n описание алгоритма Аn.
Очевидно, что различных нумераций много. Существование нумераций позволяет работать с алгоритмами как с числами. Это удобно при исследовании алгоритмов над алгоритмами. Такие алгоритмы уже рассматривались при построении универсальной машины Тьюринга и в связи с проблемой остановки. По существу, вычислимая умерация служит языком программирования для универсального алгоритма.
Теорема 1. Не существует алгоритма В(x,y) такого, что для любого алгоритма Аx (с номером (А)=х)
Иначе говоря, не существует алгоритма, который по номеру х любого алгоритма и исходным данным y определял бы остановится алгоритм Ах при этих данных или нет.
Эта теорема - переформулировка в инвариантном виде теоремы о неразрешимости проблемы остановки.
Один частный случай проблемы остановки имеет вполне самостоятельную интерпретацию: рассмотрим машину Т, которая решает проблему остановки для машины Т в случае, когда на ленте машины Т написана ее собственная система команд. Такая проблема называется проблемой самоприменимости машин Тьюринга. Было показано, что такая машина невозможна. В инвариантном виде это формулируется следующей теоремой
Теорема 2. Проблема самоприменимости алгоритмов аналитически неразрешима.
Т.е. не существует алгоритма В1(х) такого, что для любого Ах
|
|
Эти две теоремы являются мощным средством для доказательства разных неразрешимостей.
Решение задачи перечисления всех алгоритмов (в частности, всех рекурсивных функций) в принципе ясно. Может показаться, что перечисление примитивно-рекурсивных или общерекурсивных функций окажется более легким делом.
Теорема 3. Для любого перечисления любого множества всюду определенных вычислимых (т.е. общерекурсивных) функций существует общерекурсивная функция не входящая в это перечисление.
Если в перечислении допускаются частичные функции, то определение В не приводит к противоречию, а лишь означает, что в точке Хв функция В(Хв) не определена.
Теорема 4. Проблема определения общерекурсивности алгоритмов неразрешима.
Не существует алгоритма В(х) такого, что для любого алгоритма Ах
Среди требований к алгоритмам говорилось о желательности такого требования, как результативность. Первым ударом по этому требованию была неразрешимость проблемы остановки, означающая, что если алгоритм может быть частичным, то по алгоритму А и данным х нельзя узнать, даст А результат на данных х или нет.
Возникает естественное желание либо вообще убрать частичные алгоритмы из общей теории алгоритмов (скажем, не считать их ал-горитмами), либо ввести стандартный метод доопределения частичных алгоритмов. Однако ни то, ни другое эффективными методами сделать нельзя. В силу последней теоремы нет эффективного способа распознавать частичные алгоритмы среди множества всех алгоритмов и следовательно, предполагаемый отбор невозможен. Что касается второй идеи, для нее существует не менее убедительное опровержение:
|
|
Теорема 5. Существует такая частично-рекурсивная функция f, что никакая общерекурсивная функция g не является ее доопределением.
Следовательно, существуют частичные алгоритмы, которые нельзя доопределить до всюду определенного алгоритма.
Еще одна идея: построить язык, описывающий все всюду определенные алгоритмы и только их. Осуществить ее нельзя потому, что описания в этом языке можно упорядочить и следовательно, наличие такого языка означало бы существование полного перечисления всех всюду определенных функций, что противоречит теореме 3.
Таким образом, возникает дилемма: либо определение алгоритма должно быть достаточно общим, чтобы в число объектов, удовлетворяющих этому определению заведомо вошли все объекты, которые естетственно считать алгоритмами, либо требование об обязательной результативности сохраняется.
В первом случае этому определению будут удовлетворять частичные алгоритмы и избавиться от них конструктивными методами нельзя. Во втором случае никакую процедуру нельзя называть алгоритмом до тех пор, пока для нее не решена проблема остановки, а единого метода решения этой проблемы не существует.
Впрочем, когда речь идет об алгоритме, решающем данную задачу, теория алгоритмов обязательно требует сходимости. И только в случае, когда алгоритм решения всюду определен, соответствующая задача считается разрешимой.
Просматривая весь запас алгоритмически неразрешимых проблем, можно заметить, что все они так или иначе связаны с самоприменимостью. Понятие самоприменимости весьма далеко от алгоритмической практики, следовательно, можно предположить, что и неразрешимость в этой практике никогда не встречается.
|
|
Теорема Райса. Никакое нетривиальное свойство вычислимых функций не является алгоритмически разрешимым.
Отсюда следует, что по номеру вычислимой функции нельзя узнать, является ли эта функция постоянной, периодической, ограниченной и т.д.
Чтобы разобраться в смысле теоремы Райса, следует вспомнить, что номер х функции f – это номер алгоритма Ах, вычисляющего f; по номеру алгоритма однозначно восстанавливается его описание, и разным номерам соответствуют разные алгоритмы.
Для функций это неверно: при xyfx и fy могут быть одной и той же функцией (в ее классическом смысле).
Можно ли по тексту сколько-нибудь сложной программы (не запуская ее в работу) понять, что она делает (не имея гипотез о том, что она должна делать)? В этом тексте алгоритмическим путем можно отыскать так называемые синтаксические ошибки – те или иные свойства описания алгоритма (и это делают трансляторы и компиляторы с алгоритмических языков программирования).
Хорошо известно, что в процессе отладки программ синтаксические ошибки обнаруживаются очень быстро; все неприятности связаны с анализом семантики программы, т.е. с попытками установить, что же собственно программа делает, вместо того, чтобы делать задуманное.
Мы говорили о неразрешимых проблемах внутри самой теории алгоритмов. Некоторые из них имеют вполне реальную интерпретацию в практике программирования. Неразрешимости возникают и в других областях – в теории автоматов, в синтаксическом анализе и других и с существованием их приходится считаться.
Если же важно иметь дело с разрешимой задачей, то следует четко представлять, что, во-первых отсутствие общего алгоритма, решающего данную проблему не означает, что в частном случае нельзя добиться успеха. Во-вторых, появление неразрешимости – как правило, результат черезмерной общности задачи. Задача в более общей постановке имеет больше шансов оказаться неразрешимой.