Страница 20 из 160
Несколько отступая в сторону, я укажу операцию, для которой машина Тьюринга проще в расширенной двоичной, нежели в унарной форме — это умножение на два. Действительно, машина Тьюринга XN х 2, заданная в виде
00 → 00R
01 → 10R
10 → 01R
11 → 100R
100 → 111R
110 → 01.STOP
запросто выполнит эту операцию в расширенной двоичной форме, тогда как соответствующая унарная машина UN х 2, описанная ранее, гораздо сложнее!
Этот раздел дает определенное представление о том, на что способны в простейших случаях машины Тьюринга. Как и следовало ожидать, при выполнении более или менее сложных операций эти машины могут становиться, и действительно становятся, несравненно более сложными. Каковы же принципиальные возможности таких устройств? Мы рассмотрим этот вопрос в следующем параграфе.
Тезис Черча — Тьюринга
После ознакомления с принципами построения простых машин Тьюринга легко убедиться, что все основные математические операции, такие как сложение двух чисел, их перемножение или возведение одного из них в степень другого, могут на самом деле быть выполнены соответствующими машинами Тьюринга. Построение таких машин в явном виде не представляет больших затруднений, но я не собираюсь сейчас этим заниматься. Машины Тьюринга могут выполнять операции, результат которых выражается парой натуральных чисел, например, деление с остатком, или сколь угодно большим, но конечным множеством чисел. Более того, можно сконструировать такие машины Тьюринга, для которых арифметические операции не предопределены заранее, а могут задаваться инструкциями, вводимыми с ленты. При этом возможно, что та конкретная операция, которая должна быть выполнена, будет зависеть в тот или иной момент от результатов вычислений, которые машина должна была выполнить на предыдущих этапах. («Если результат вычислений больше, чем то-то, надо сделать то-то, в противном случае выполнить то-то».) Убедившись, что можно построить машины Тьюринга, выполняющие арифметические или простые логические операции, уже не так трудно представить себе, какими должны быть машины, выполняющие более сложные задачи алгоритмического характера. «Повозившись» немного с подобными задачами, легко приходишь к убеждению в том, что машина этого типа может выполнять вообще любые механические операции! Тогда с точки зрений математики приобретает смысл определение механической операции как такой операции, которую может выполнить подобная машина. Существительное «алгоритм» и прилагательные «вычислимый», «рекурсивный» и «эффективный» используются математиками для обозначения механических операций, которые могут быть выполнены теоретическими устройствами такого рода, т. е. машинами Тьюринга. Если некоторая процедура четко определена и по природе своей механистична, то можно вполне обоснованно предположить, что найдется машина Тьюринга, способная ее выполнить. Это, в конце концов, и есть основной момент наших (то есть Тьюринга) рассуждений, лежащий и в основе самой концепции машины Тьюринга.
С другой стороны, остается ощущение, что принципы построения этих машин содержат излишние ограничения. Разрешение устройству считывать за один раз только одну двоичную цифру (0 или 1) и передвигаться каждый раз только на один шаг да еще вдоль единственной одномерной ленты, на первый взгляд, ограничивает возможности машины. Почему бы не разрешить одновременное использование четырех, пяти или, возможно, тысячи разных лент, по которым одновременно двигалось бы большое количество взаимосвязанных считывающих устройств? Почему бы не ввести целую плоскость с нулями и единицами (или, например, трехмерное пространство), вместо того чтобы настаивать на использовании одномерной ленты? Почему бы не использовать другие системы счисления или символы из каких-нибудь более сложных алфавитов? По сути, ни одно из этих изменений ни в малейшей степени не влияет на то, что в принципе может быть достигнуто с помощью машины Тьюринга, хотя некоторые из них отразились бы на экономичности производимых операций (как это наверняка произошло бы, разреши мы использование нескольких лент). Класс осуществляемых операций, попадающих, таким образом, под определение «алгоритма» (или «вычисления», или «выполнимой процедуры», или «рекурсивной операции»), остался бы в точности тем же самым, если мы расширим определение наших машин и включим в него даже все предлагавшиеся выше модификации одновременно!
Мы можем видеть, что нет необходимости в дополнительных лентах, коль скоро устройство может по мере надобности находить свободное место на одной ленте. При этом может потребоваться постоянная перезапись данных с одного места ленты на другое. Это, может быть, «неэффективно», но в принципе не ограничивает возможности машин Тьюринга[44]. Сходным образом, использование более чем одного устройства Тьюринга для параллельных вычислений — идея, ставшая очень популярной в последние годы в связи с попытками более точного моделирования человеческого мозга, — не дает никаких принципиальных преимуществ (хотя при определенных обстоятельствах может увеличиться быстродействие). Использование двух непосредственно не связанных друг с другом устройств не даст выигрыша по сравнению с двумя взаимосвязанными устройствами. Но если два устройства связаны друг с другом, то, в сущности, это уже одно устройство!
А что можно сказать об ограничении Тьюринга, касающегося одномерности ленты? Если мы считаем, что эта лента представляет собой «окружение», то, возможно, мы бы предпочли в качестве такового иметь плоскую поверхность, или, допустим, трехмерное пространство. Может показаться, что плоскость лучше подошла бы для изображения «блок-схемы» вычислений (как в вышеприведенном описании последовательности действий алгоритма Евклида), чем одномерная лента[45]. Однако запись блок-схемы в «одномерной» форме не представляет принципиальных трудностей (например, можно использовать обычное словесное описание). Двумерное плоское изображение дает только удобство и простоту восприятия, но, по сути, ничего не меняет. Всегда есть возможность преобразовать координаты отметки или объекта на двумерной плоскости или в трехмерном пространстве и явным образом отобразить их на одномерной ленте. (Фактически, использование двумерной плоскости полностью эквивалентно использованию двух лент. Две ленты дают две «координаты», которые нужны для определения местоположения точки на двумерной плоскости; аналогично, три ленты могут выполнять ту же роль для точки в трехмерном пространстве.) И хотя эта одномерная запись может вновь оказаться «неэффективной», принципиальные возможности устройства это никак не ограничивает.
Несмотря на все это, по-прежнему остается вопрос о том, действительно ли понятие машины Тьюринга охватывает все логические или математические операции, которые мы могли бы назвать «механическими». В то время, когда Тьюринг написал свою основополагающую работу, ситуация была гораздо менее ясной, чем сегодня, поэтому Тьюринг справедливо посчитал необходимым предоставить развернутое изложение этого вопроса. Детально рассмотренная Тьюрингом проблема получила дополнительное обоснование благодаря тому, что совершенно независимо от Тьюринга (и на самом деле несколько ранее) американский логик Алонзо Черч (совместно со Стивеном Клини), стремясь найти решение проблемы алгоритмической разрешимости Гильберта, предложил свою схему лямбда-исчисления. Хотя то, что это была всеобъемлющая полностью механическая схема, было не так очевидно, как в случае с подходом Тьюринга, ее несомненным преимуществом была удивительная компактность математической структуры. (Я буду рассматривать замечательный анализ Черча в конце главы.) Независимо от Тьюринга были предложены и другие подходы к решению задачи Гильберта (см. Ганди [1988]), среди которых можно выделить работу американского логика польского происхождения Эмиля Поста (опубликованную несколько позже работы Тьюринга, но содержащую идеи, более близкие идеям Тьюринга, нежели Черча). В скором времени было доказано, что все эти схемы совершенно эквивалентны.
44
Один из способов записи информации с двух лент на одну — вставить записи одной из них между записями другой. При этом нечетные отметки на новой ленте могут соответствовать отметкам первой ленты, тогда как четные — отметкам второй. Аналогичная схема работает и для четырех, и для большего числа лент. «Неэффективность» этой процедуры обусловлена тем, что считывающему устройству пришлось бы «прыгать» взад-вперед по ленте, оставляя на ней маркеры как на четных местах, так и на нечетных, с тем чтобы фиксировать свое положение в каждый момент.
45
В согласии с предложенным здесь описанием, эта блок-схема была бы скорее частью «устройства», нежели внешнего окружения — «ленты». На ленте мы до сих пор отображали только числа А, В, А — В, и т. п Однако в дальнейшем нам потребуется также возможность описания и самого устройства в линейной одномерной форме. Как мы увидим далее в связи с универсальной машиной Тьюринга, есть тесная взаимосвязь между свойствами конкретного «устройства» и свойствами возможных «данных» (или «программы») для него. Поэтому удобно в обоих случаях придерживаться одномерной формы записи.