< Предыдущая		Оглавление		Следующая >

4.3. Вычислимая функция и тезис Чёрча - Тьюринга. Проблема гипервычислений

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

Исторический экскурс

Готфрид Лейбниц в XVII в. поставил задачу выработки универсального формализованного языка, который можно было бы использовать при машинных вычислениях. Однако для актуализации его идеи понадобилось два века. Во многом это произошло благодаря необходимости справиться с парадоксами теории множеств, считавшейся в начале XX в. самой универсальной математической наукой. Парадоксы вызвали к жизни несколько проектов их преодоления, в частности логицизм Б. Рассела, интуиционизм Л. Брауэра и формализм Д. Гильберта. Англичанин Бертран Рассел развил теорию типов, оказавшуюся весьма актуальной для информатики. Голландец Лёйтзен Брауэр заложил краеугольный камень в основание здания конструктивной логики и математики, без которой также невозможно представить современную информатику. Но особенно значимыми оказались для нее воззрения Давида Гильберта. Немецкий ученый полагал, что любая математическая и логическая система должна быть представлена в виде формального языка с заданием соответствующих аксиом и правил вывода. Правомерность такой системы обосновывается в метаматематике, для чего доказывается полнота системы аксиом и непротиворечивость процесса вывода теорем.

Таковы были исходные интуиции Гильберта. Размышляя над ними, он пришел к выводу, что требование полноты системы аксиом и непротиворечивости доказательств следует дополнить концептами разрешимости и вычислимости. Формула разрешима, если в данной формальной системе доказуемы либо она сама, либо ее отрицание. Функция вычислима, если существует алгоритм (т.е. конечная последовательность операций), перерабатывающий всякий объект х, для которого задана функция/в объект/(х) и не применимый ни к какому х, для которого/ не определена. Считается, что проблема разрешимости была в четкой форме представлена Давидом Гильбертом и Вильгельмом Аккерманом в 1928 г.1 Последующие открытия имели для судеб информатики исключительную значимость. В 1931 г. австриец Курт Гёдель доказал неполноту любой формальной системы, содержащей значительную часть формальной арифметики, при этом он использовал понятие рекурсивной функции2. В1936 г. американец Алонзо Чёрч разработал теорию лямбда-исчисления, а также подтвердил существование неразрешимых задач. В том же году англичанин Алан Тьюринг предложил алгоритм осуществления эффективной вычислимости, сопрягаемый с концептом абстрактной математической машины. Подобно Геделю и Черчу Тьюринг подтвердил наличие не только разрешимых, но и неразрешимых функций. Работы американского ученого Стивена Клини имели важнейшее значение для теории формальных языков, а Эмиль Пост усовершенствовал концепт абстрактной математической машины.

Исследования Гёделя, Чёрча, Тьюринга, Клини и Поста, дополненные в конце 1947 г. теорией нормальных алгоритмов А А Маркова, составили основание информатики. Самое главное заключалось в том, что в значительной степени был прояснен механизм вычисления, которое стало пониматься как осуществление операций с символами, заканчивающееся получением эффективного результата. В полной мере было осознано существование как разрешимых, так и неразрешимых задач. Но даже последние, как показало осмысление теоремы Гёделя о неполноте, неразрешимы лишь при определенных условиях: при их соответствующем изменении задачи могут стать разрешимыми. Например, как свидетельствуют работы Герхарда Генцена, формализованная арифметика непротиворечива и полна в случае опоры на индукцию до некоторого счетного трансфинитного числа. Таким образом, проблема неразрешимости всегда является незавершенной историей.

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

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

Любопытно проследить за процессом осмысления концепта вычислимости.

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

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

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

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

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

Намного более критично к тезису Чёрча - Тьюринга относился Э. Пост, который энергично возражал против идентификации эффективно вычислимой функции с рекурсиями или с лямбда-исчислением.

"В действительности работа, проделанная Чёрчем и другими исследователями, выводит эту идентификацию далеко за границы рабочей гипотезы. Но, маскировка этой идентификации определением... затмевает необходимость ее непрерывной верификации".

Однако и критики тезиса Чёрча - Тьюринга встретились с известными затруднениями. Предлагались все новые варианты эффективно вычислимых функций, в частности в теориях Э. Поста (канонические системы) и А. А. Маркова (нормальные алгоритмы), использовалась также комбинаторная логика X. Карри. Тем не менее всегда выяснялось, что указанные методы совместимы с представлениями о рекурсивных функциях, лямбда-исчислении и машине Тьюринга. Предлагались различные варианты абстрактных машин, в частности, варьировались их воображаемые конструкты, например число лент и конфигурация считывающих головок. И вновь неизменно выяснялось, что эти усовершенствованные машины не отменяют те концепты, которые ввел Тьюринг. Наконец, обращалось внимание на ограничения, которые привносят с собой непосредственно те процессы, что совершаются в реальных компьютерах. Здесь, в частности, необходимо учитывать конечность скорости передачи сигналов и ограниченное число элементов памяти. Но и в этом случае оставалось в силе ставшее в информатике ортодоксальным представление об эффективно вычислимой функции, основанной на принятии тезиса Чёрча - Тьюринга.

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

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

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

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

Теоретическая разработка

1. Процесс может быть использован в математических целях, если и только если его поведение на входе/выходе:

а) либо детерминистично, либо приблизительно детерминистично и вызываемая им ошибка может быть сведена к произвольно малой величине;

б) определяется за конечное число шагов.

2. Процесс Р может быть использован в его физических качествах, если и только если его поведение на входе/выходе в соответствии с научными данными может быть использовано для моделирования других специфических процессов.

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

Междисциплинарные связи информатики с физикой

Квантовая физика, как известно, во многих отношениях принципиально отличается от своей классической предшественницы. Это обстоятельство имеет для идеи вычислений посредством квантовых компьютеров решающее значение. Допустим, что квантовая система состоит из Ь двухуровневых квантовых элементов, называемых квантовыми битами, или кубитами. В таком случае она обладает 21 состояниями, которые изменяются в соответствии с уравнением Шрёдингера. Принимается, что эволюция квантового состояния является процессом, выполняющим вычисления. Следовательно, параллельно выполняются 21 операций. В классическом же случае компьютер выполняет одну операцию за другой. При росте числа I преимущество квантового компьютера перед его классическим собратом выявляется особенно отчетливо.

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

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

Подводя итоги анализа проблемы гипервычислений, необходимо отметить, что данная область исследований находится в стадии становления. М. Стэннет, рассмотревший два десятка вариантов гиперкомпьютеров, уверен, что новой области исследований принадлежит будущее. Не существует никаких ограничений, которые свидетельствовали бы в пользу ложности идеи. Гипервычисления относятся к обычным вычислениям приблизительно так же, как неевклидова геометрия к евклидовой2. Принципиально иную позицию занимает американский математик М. Дэвис. Он полагает, что сторонники гипервычислений некритически воспринимают незамысловатый тезис о том, что если существует физический процесс, генерирующий невычислимую посредством машины Тьюринга функцию или числа, то он может быть использован для гипервычислений3. По мнению Дэвиса, вопрос о невычислимости некритически подменен проблемой гипервычислимости. Впрочем, несомненно, что исследования в области гипервычислений набирают темп. Со своей стороны отметим существование потребности в углубленной концептуальной проработке концепции гипервычислений. Констатируем, что пока еще парадигма вычисления, представленная блоком рекурсивных функций, машиной Тьюринга и лямбда-исчислением, не получила достойного соперника.

Выводы

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

2. Остро ощущается потребность в углубленной концептуальной проработке концепта гипервычислений.

< Предыдущая		Оглавление		Следующая >