§ 10. ОСНОВНАЯ ГИПОТЕЗА ТЕОРИИ АЛГОРИТМОВ

Разбор предыдущих примеров создает впечатление о процессе, происходящем в тьюринговой машине, как о чрезвычайно замедленной киносъемке процесса вычисления, выполняемого человеком в соответствии с

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

На эти вопросы современная теория алгоритмов предлагает ответ в виде следующей гипотезы:

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

Мы рассмотрим здесь два вопроса, возникающих в связи с формулировкой гипотезы:

1. В чем заключается значение этой гипотезы для теории алгоритмов?

2. В чем заключается обоснование гипотезы?

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

Значение гипотезы как раз и заключается в том, что она уточняет общее, но расплывчатое понятие «всякого алгоритма» через более специальное, но уже совершенно точное математическое понятие тьюринговой функциональной схемы (и ее реализации в тьюринговой машине); таким образом, теория алгоритмов и объявляет в качестве объекта своего исследования всевозможные Тьюринговы функциональные схемы (Тьюринговы машины).

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

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

В чем же заключается обоснование этой столь важной гипотезы?

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

Уверенность в справедливости гипотезы основана главным образом на опыте. Все известные алгоритмы, которые были придуманы в течение многих тысячелетий истории математики, могут быть заданы посредством тьюринговых функциональных схем. Правда, содержание гипотезы не обращено только в прошлое и не ограничивается констатацией того, что для всех известных аглоритмов оказалось возможным задание функциональными схемами. Содержание гипотезы имеет и вполне отчетливый характер прогноза на будущие времена: всякий раз, когда в будущем какое-либо предписание будет признано алгоритмом, то независимо от того, в какой форме и какими средствами это предписание будет первоначально выражено, его можно будет задавать также в виде функциональной схемы машины Тьюринга.

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

опыт в прошлом признается достаточным основанием для подобных прогнозов.

Имеются и другие соображения, подтверждающие правильность основной гипотезы.

В предыдущем параграфе были указаны два приема построения из заданных исходных алгоритмов других более сложных алгоритмов: композиция алгоритмов и повторение алгоритма. Список таких приемов можно было бы еще продолжить. Однако все известные подобные приемы, а также все те, которые можно предвидеть при современном состоянии науки, оказываются таковыми, что, коль скоро для исходных алгоритмов возможно задание посредством функциональных схем, то оно возможно и для результирующих более сложных алгоритмов. В частности, для композиции алгоритмов было показано, как по заданным функциональным схемам строится новая схема. Кроме того, напомним еще следующее обстоятельство, которое уже было упомянуто вскользь в § 7. Когда в науке возникла острая потребность в выработке точного понятия алгоритм, многие математики предприняли исследование с целью выявить некоторую стандартную форму задания алгоритмов, достаточно точную, для того чтобы она могла стать объектом математических исследований, и достаточно общую, для того чтобы всем мыслимым алгоритмам можно было придавать такую форму. Кроме функциональных схем тьюринговых машин, были предложены и другие способы уточнения этого понятия. Так, например, А. А. Марков пришел к понятию нормального алгоритма (которое в этой книге было только бегло проиллюстрировано на алгоритме приведения для ассоциативного исчисления примера 4 § 4), а Гедель и Клини пришли к понятию рекурсивного алгоритма (рекурсивной функции) и т. д. Однако впоследствии все эти уточнения оказались равносильными. Этот факт нельзя считать случайным; он является дополнительным доводом в пользу сформулированной гипотезы.

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

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

Автор этих строк вполне разделяет уверенность в справедливости основной гипотезы и вытекающей отсюда оценки современной теории алгоритмов, как общей теории, описывающей саму природу вещей, а не просто теории искусственно выделенного класса специальных «тьюринговых алгоритмов».