Тезис Черча—Тьюринга

После ознакомления с принципами по­строения простых машин Тьюринга легко убедиться, что все основные математичес­кие операции, такие как сложение двух чи­сел, их перемножение или возведение одно­го из них в степень другого, могут на самом деле быть выполнены соответствующими машинами Тьюринга. Построение таких ма­шин в явном виде не представляет боль­ших затруднений, но я не собираюсь сейчас этим заниматься. Машины Тьюринга могут выполнять операции, результат которых вы­ражается парой натуральных чисел, напри­мер, деление с остатком, или сколь угодно большим, но конечным множеством чисел. Более того, можно сконструировать такие машины Тьюринга, для которых арифме­тические операции не предопределены за­ранее, а могут задаваться инструкциями, вводимыми с ленты. При этом возможно, что та конкретная операция, которая долж­на быть выполнена, будет зависеть в тот или иной момент от результатов вычислений, которые машина должна была выполнить на предыдущих этапах. («Если результат вы­числений больше, чем то-то, надо сделать то-то, в противном случае выполнить то-то».) Убедившись, что можно построить ма­шины Тьюринга, выполняющие арифмети­ческие или простые логические операции, уже не так трудно представить себе, каки­ми должны быть машины, выполняющие более сложные задачи алгоритмического ха­рактера. «Повозившись» немного с подоб­ными задачами, легко приходишь к убе­ждению в том, что машина этого типа мо­жет выполнять вообще любые механические операции*. Тогда с точки зрений математики приобретает смысл определение механичес­кой операции как такой операции, которую может выполнить подобная машина. Суще­ствительное «алгоритм» и прилагательные «вычислимый», «рекурсивный» и «эффек­тивный» используются математиками для обозначения механических операций, кото­рые могут быть выполнены теоретически­ми устройствами такого рода, т. е. маши­нами Тьюринга. Если некоторая процеду­ра четко определена и по природе своей механистична, то можно вполне обосно­ванно предположить, что найдется маши­на Тьюринга, способная ее выполнить. Это, в конце концов, и есть основной момент на­ших (то есть Тьюринга) рассуждений, лежа­щий и в основе самой концепции машины Тьюринга.

С другой стороны, остается ощущение, что принципы построения этих машин со­держат излишние ограничения. Разрешение устройству считывать за один раз только одну двоичную цифру (0 или 1) и передви­гаться каждый раз только на один шаг да еще вдоль единственной одномерной ленты, на первый взгляд, ограничивает возможно­сти машины. Почему бы не разрешить од­новременное использование четырех, пяти или, возможно, тысячи разных лент, по ко­торым одновременно двигалось бы большое количество взаимосвязанных считывающих устройств? Почему бы не ввести целую плос­кость с нулями и единицами (или, напри­мер, трехмерное пространство), вместо того чтобы настаивать на использовании одно­мерной ленты? Почему бы не использо­вать другие системы счисления или сим­волы из каких-нибудь более сложных алфа­витов? По сути, ни одно из этих изменений ни в малейшей степени не влияет на то, что в принципе может быть достигнуто с по­мощью машины Тьюринга, хотя некоторые из них отразились бы на экономичности производимых операций (как это наверня­ка произошло бы, разреши мы использо­вание нескольких лент). Класс осуществля­емых операций, попадающих, таким обра­зом, под определение «алгоритма» (или «вы­числения», или «выполнимой процедуры», или «рекурсивной операции»), остался бы в точности тем же самым, если мы расши­рим определение наших машин и включим в него даже все предлагавшиеся выше мо­дификации одновременно!

Мы можем видеть, что нет необходи­мости в дополнительных лентах, коль ско­ро устройство может по мере надобности находить свободное место на одной лен­те. При этом может потребоваться посто­янная перезапись данных с одного места ленты на другое. Это, может быть, «неэф­фективно», но в принципе не ограничивает возможности машин Тьюринга I⁴'. Сходным образом, использование более чем одного устройства Тьюринга для параллельных вы­числений — идея, ставшая очень популярной в последние годы в связи с попытками бо­лее точного моделирования человеческого мозга, — не дает никаких принципиальных преимуществ (хотя при определенных обсто­ятельствах может увеличиться быстродей­ствие). Использование двух непосредствен­но не связанных друг с другом устройств не даст выигрыша по сравнению с двумя взаимосвязанными устройствами. Но если два устройства связаны друг с другом, то, в сущности, это уже одно устройство!

А что можно сказать об ограничении Тьюринга, касающегося одномерности лен­ты? Если мы считаем, что эта лента пред­ставляет собой «окружение», то, возмож­но, мы бы предпочли в качестве таково­го иметь плоскую поверхность, или, допу­стим, трехмерное пространство. Может по­казаться, что плоскость лучше подошла бы для изображения «блок-схемы» вычислений (как в вышеприведенном описании после­довательности действий алгоритма Евкли­да), чем одномерная лента³'. Однако запись блок-схемы в «одномерной» форме не пред­ставляет принципиальных трудностей (на­пример, можно использовать обычное сло­весное описание). Двумерное плоское изо­бражение дает только удобство и простоту восприятия, но, по сути, ничего не меняет. Всегда есть возможность преобразовать ко­ординаты отметки или объекта на двумерной плоскости или в трехмерном пространстве и явным образом отобразить их на одномер­ной ленте. (Фактически, использование дву­мерной плоскости полностью эквивалентно использованию двух лент. Две ленты да­ют две «координаты», которые нужны для определения местоположения точки на дву­мерной плоскости; аналогично, три ленты могут выполнять ту же роль для точки в трех­мерном пространстве.) И хотя эта одномер­ная запись может вновь оказаться «неэф­фективной», принципиальные возможности устройства это никак не ограничивает.

Несмотря на все это, по-прежнему оста­ется вопрос о том, действительно ли понятие машины Тьюринга охватывает все логичес­кие или математические операции, которые мы могли бы назвать «механическими». В то время, когда Тьюринг написал свою осново­полагающую работу, ситуация была гораздо менее ясной, чем сегодня, поэтому Тью­ринг справедливо посчитал необходимым предоставить развернутое изложение это­го вопроса. Детально рассмотренная Тью­рингом проблема получила дополнительное обоснование благодаря тому, что совершен­но независимо от Тьюринга (и на самом деле несколько ранее) американский ло­гик Алонзо Черч (совместно со Стивеном Клини), стремясь найти решение проблемы алгоритмической разрешимости Гильберта, предложил свою схему лямбда-исчисления. Хотя то, что это была всеобъемлющая пол­ностью механическая схема, было не так очевидно, как в случае с подходом Тью­ринга, ее несомненным преимуществом бы­ла удивительная компактность математиче­ской структуры. (Я буду рассматривать за­мечательный анализ Черча в конце главы.) Независимо от Тьюринга были предложе­ны и другие подходы к решению задачи Гильберта (см. Ганди [1988]), среди которых можно выделить работу американского ло­гика польского происхождения Эмиля По­ста (опубликованную несколько позже ра­боты Тьюринга, но содержащую идеи, более близкие идеям Тьюринга, нежели Черча). В скором времени было доказано, что все эти схемы совершенно эквивалентны.

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