ИНТЕЛРОС > №1, 2009 > Абстрактная недетерминированная вычислимость*

Абстрактная недетерминированная вычислимость*


13 марта 2009

Теории вычислимости и философия

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

Следуя идеям Марио Бунге[1], определим детерминизм как принцип, согласно которому всё существующее, во-первых, чем-то однозначно обусловлено, и, во-вторых, во всём полностью определённо. Отсюда недетерминизм означает либо неоднозначную обусловленность, либо неполную определённость, или и то, и другое вместе. Крайней формой недетерминизма является индетерминизм – допущение существования чего-либо ничем не обусловленного или полностью неопределённого.

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

Между тем, в ходе философского осмысления человеческого опыта и результатов наук накапливается всё больше проблем, обсуждение которых требует привлечения альтернативных теорий вычислимости. Возьмём старую философскую проблему причинности. Победоносное шествие юмовского подхода к причинности как функции, при котором проблема производительной причинности (в смысле «причина производит следствие») объявляется псевдо проблемой, обусловлено, помимо прочих обстоятельств, отсутствием надлежащего концептуального аппарата. В подходящей альтернативной теории вычислимости понятию «производительной причинности» можно придать точный смысл. Редуцирование проблемы времени к геометрическим вопросам, как это делается в современной физике, не позволяет даже поставить проблему течения времени. Это можно сделать, понимая течение времени как осуществление особого вычислительного процесса, однако средств традиционной теории вычислимости здесь недостаточно хотя бы в силу того, что их применение предрешает ответ на вопрос о начале времени[3]. Ещё одна важная проблема связана с моделированием интеллекта. Естественная идея трактовать интеллектуальные операции как вычисления наталкивается на обоснованные контраргументы именно в связи с тем, что исходная теория вычислимости оказывается слишком бедной для построения таких моделей. Наконец, множатся попытки весь мир представить в виде совокупности вычислительных процессов. Если при этом базироваться на имеющихся теориях вычислимости, полученные результаты останутся на уровне метафор или игровых моделей (типа игры Конвея «Жизнь»).

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

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

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

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

Абстрактные компьютеры, языки программирования и недетерминированные вычисления интересны не сами по себе, а в связи с возможностью точной постановки и обсуждения (в идеале – и решения, пусть не окончательного) допускающих вычислительный подход аспектов следующих философских проблем: детерминизма, причинности, движения, течения времени, креативности (проблемы появления нового и его «стыковки» со старым), искусственного интеллекта (ИИ), изменяющегося знания. Эти проблемы, повторим, должны браться не во всей сложности и глобальности, а лишь в аспекте их вычислительной трактовки в рамках дихотомии детерминизм – недетерминизм.

Проблема недетерминированной вычислимости главным образом исследуется в таком разделе математической теории вычислимости, как теория сложности. В ней разрабатываются методы оценки сложности алгоритмов (уровни труднорешаемости задач, степени неразрешимости и т.д.). Открытый на сегодняшний день вопрос о сравнении вычислительной мощности детерминированной и недетерминированной машин Тьюринга (знаменитая P – NP проблема) считается одним из главных в вычислительной математике.

Однако в философских исследованиях в нашей стране и за рубежом идея недетерминированной вычислимости не находит заметного применения. Причина, по-видимому, заключается в том, что философы либо довольствуются традиционной теорией детерминированной вычислимости, либо объявляют решаемые ими задачи принципиально невычислимыми. Так, в философии ИИ уже долгое время идёт дискуссия между сторонниками и противниками вычислительного подхода. Первые возлагают надежды на компьютеры нетрадиционной архитектуры (параллельные машины, клеточные автоматы, квантовые компьютеры и др.), вторые не без оснований указывают, что подобные компьютеры не выводят нас за границы классической вычислимости. Например, хотя квантовые вычисления в ряде случаев оказываются эффективнее вычислений по Тьюрингу, они не выходят за границы класса стандартных вычислимых функций. Согласно выдающемуся математику и физику Р.Пенроузу, «все, что в принципе можно получить с помощью квантового компьютера, можно в принципе получить и с помощью соответствующей машины Тьюринга, снабженной генератором случайных чисел»[4]. Отсюда Пенроуз делает вывод о невычислимости сознания.

Стандартная вычислимость: границы применимости

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

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

      I. Синтаксические ограничения;

     II. Ограничения по памяти;

    III. Ограничения на порядковые типы процессов.

Перейдем теперь к свойствам внутри каждой из перечисленных групп.

I.1. Синтаксическая сложность. Программирование как реальных, так и абстрактных компьютеров – это почти всегда нагромождение синтаксических конструкций для выражения самых простых вещей. Например, в Паскале вы не должны писать Х:=Y, если Х имеет тип INTEGER (целого числа), а Y – тип REAL (действительного числа). Вместо этого приходится писать Х:=TRUNC(Y), где "TRUNC" – функция преобразования типа REAL в тип INTEGER. Предметом особой гордости разработчиков системы "Турбо-Паскаль" служит наличие в этой системе не одного, как в стандартном Паскале, а нескольких целочисленных и вещественных типов, что тоже отнюдь не упрощает синтаксис. В других языках программирования дела обстоят не лучшим образом. Не лучше они и в случае программирования абстрактных вычислительных машин, программы для которых скорее напоминают программы на ассемблере, чем программы на языках высокого уровня. Возьмем в качестве примера программу для машины с неограниченными регистрами, складывающую два целых числа Х и Y: I1 J(3,2,5); I2 S(1); I3 S(3); I4 J(1,1,1). Излишне говорить, что программы, описывающие менее тривиальные процессы, чем процесс сложения, будут содержать более длинные и труднообозримые цепочки команд.

I.2. Непрозрачность синтаксиса. Данный вид ограничений свойственен только языкам программирования высокого уровня. Как правило, инструкции этих языков включают в себя последовательность зачастую разноплановых логических действий. Так, сплошь и рядом применяемая операция присваивания, например, в виде X:=0, содержит в себе две логически разных операции – уничтожение старого значения X и размещение в соответствующих регистрах нового значения (нуля). После этого прежнее значение X теряется. В то же время, операция копирования файлов (что-нибудь вроде СOPY А В) в приличных операционных системах в случае, если файл В уже существует, сообщит об этом и попросит подтвердить решение о выполнении операции копирования. Тем самым команда "COPY" разделяет акты уничтожения файла В и создания нового файла с тем же именем.

II.1. Количество регистров конечно. Это ограничение неизбежно для реальных ЭВМ. В то же время, идеальные компьютеры могут иметь бесконечное количество ячеек памяти. Однако при этом память таких машин, как машина Тьюринга и машина с неограниченными регистрами, является счетно бесконечной, что достаточно для уточнения понятия алгоритма. Таким образом, и реальным, и рассматриваемым абстрактным компьютерам присуще следующее ограничение:

II.2. Количество регистров не более чем счетно.

II.3. Каждый регистр конечен. Смысл II.3 в том, что в каждом регистре может содержаться объект из некоторого конечного множества объектов. Для реальных ЭВМ это всегда так. Однако абстрактные компьютеры свободны от данного ограничения: так, в ячейке машины с неограниченными регистрами может содержаться любое положительное целое число из бесконечного множества таких чисел N.

Рассматриваемое ограничение имеет интересное следствие. Если n, m Î N, n – количество регистров и m – количество объектов, которые могут быть размещены в каждом из регистров, то в процессе выполнения любого бесконечного цикла через самое большее k=mn шагов распределение объектов в памяти компьютера обязательно повторится. В дальнейшем ничего нового в памяти не появится. Все, что будет, уже было – бесконечный цикл на машине со свойством II.3 приводит к вечному возвращению[6], о котором с таким вдохновением писал Ф.Ницше. На машине с неограниченными регистрами, напротив, легко организовать бесконечный цикл без вечного возвращения (например, выполнять в цикле присваивание R0:=R0+1, где R0 – нулевой регистр; ввиду отсутствия ограничения типа II.3 результатом такого цикла будет появление в нулевом регистре все новых и новых натуральных чисел).

III.1. Каждый процесс имеет начало. Это верно как для реальных, так и для рассматривавшихся до сих пор абстрактных вычислительных машин. Между тем, a priori утверждать, что все процессы действительного мира имеют начало, нет оснований.

III.2. Актуальная конечность числа шагов. На каждом шаге вычислений количество уже проделанных шагов конечно. Даже бесконечный цикл в этом случае лишь потенциально бесконечен. Данное ограничение выполняется как для реальных, так и для упомянутых абстрактных компьютеров. Отметим, что III.2 влечет III.1.

Подведем итог. Реальным компьютерам свойственны все виды перечисленных выше ограничений, тогда как существующим эффективным абстрактным вычислительным машинам присущи все порядковые ограничения, одно ограничение синтаксического характера (I.1) и одно ограничение по памяти (II.2). Таким образом, абстрактные компьютеры менее ограничены в своих возможностях, чем реальные ЭВМ. Тем не менее, рассмотренный список свойств показывает, что и они мало пригодны для моделирования нетривиальных процессов, связанных с проблемами времени, движения и истории. Эти процессы требуют простых, но более мощных методов вычислений. Причем требование эффективности вычислений не только не является обязательным, но и в целом ряде случаев неуместно[7].

Обобщения понятия вычислимости, достигнутые за счет отказа от обычной эффективности, представлены в литературе несколькими подходами, из которых упомянем два. Первый связан с рекурсией в высших типах, а второй – с теорией a-рекурсии, где a – некоторый подходящий ординал[8]. Как признают А.Кекрис и Я.Московакис, рекурсия в высших типах трудна для понимания (отметим, что авторы обращаются к математикам, а не, скажем, к философам) и сложна технически[9]. Данное обстоятельство исключает плодотворные приложения обобщенной теории рекурсии к анализу философских проблем, если мы признаем стремление к ясности и (относительной) простоте решений обязательным в области философии. Кроме того (и это главное), эти обобщения исходят из стремления получить аналог обычной теории рекурсии, и в этой связи упор делается на обобщение идеи эффективности.

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

Хотелось бы, кроме того, иметь такую теорию неэффективной вычислимости, в которой любой процесс локально вел бы себя как обычный вычислительный процесс: процессы должны состоять из шагов, каждый из которых (если он не первый и не последний) выполняется при условии, что выполнен непосредственно предшествующий шаг, и что выполнение очередного шага вызывает осуществление непосредственно следующего шага. Между тем, в рамках рассматриваемых обобщений понятия вычислимости допустимы, например, процессы, содержащие w+1 число шагов. В качестве иллюстрации можно привести решение проблемы останова обычной машины на обобщенной машине, которое потребует как раз w+1 шагов[10]. Последний шаг при таком понимании налицо, однако нельзя указать тот конкретный шаг, осуществление которого непосредственно предшествовало выполнению последнего шага.

Абстрактная недетерминированная ABT-вычислимость

Дадим краткое описание[11] синтаксиса и семантики абстрактного языка программирования ABT, который может служить более адекватным средством моделирования течения времени, чем все ныне существующие языки программирования, по сути восходящие к идее вычислимости по Тьюрингу. Реализовать язык ABT в его существенных особенностях на реальных компьютерах невозможно, поэтому это действительно абстрактная конструкция. Так, на этом языке, как будет показано далее, можно описывать процессы, не имеющие первого шага выполнения.

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

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

В качестве памяти абстрактных компьютеров разрешается использовать любые непустые множества произвольной мощности. В частности, память Mm компьютера @ = может иметь несчетную мощность.

По определению, Mm(S) – подмножество множества Mm, указывающее, как много регистров или ячеек памяти (элементов Mm) ушло на размещение объекта (множества) S:

                Mm(S) Ì Mm.

А если в действительности объект S не был размещен в памяти Mm ? Тогда естественно считать, что для размещения S не была использована ни одна из ячеек памяти, т.е. что Mm(S) = Æ. Короче говоря, объект S размещен в памяти Mm, если и только если Mm(S) ¹ Æ.

Последнее условие, налагаемое на множества вида Mm(S), касается проблемы размещения в памяти двух и более объектов. Если необходимо поместить в память Mm множества S и S' (за один шаг или последовательно, множество за множеством), будем считать, что они займут непересекающиеся области памяти Mm, если только эти множества различны:

                S ¹ S' ® Mm(S) Ç Mm(S') = Æ.

Если же S = S', то, само собой разумеется, Mm(S) = Mm(S'). Как тогда быть, если необходимо разместить в памяти один и тот же объект в нескольких копиях? Выход прост: достаточно проиндексировать тем или иным способом требующееся количество экземпляров, а затем разместить их в памяти компьютера. Если, скажем, необходимо иметь две копии множества S, то можно разместить в памяти объекты и . Поскольку ¹ , эти упорядоченные пары займут непересекающиеся области памяти.

Размещением теоретико-множественных объектов в памяти, равно как и их удалением, управляет выполняемая процессором Pr программа, написанная на специальном языке ABT – абстрактном языке программирования. Мы не будем задумываться над тем, каким образом устроен процессор Pr, способный выполнять любую ABT-программу. Кроме того, будем считать, что ABT-программы размещаются вне области Mm и что в Mm хранятся только результаты вычислений. В оправдание последнего допущения можно указать на то обстоятельство, что физическое пространство заполняют вещи и события, тогда как физические законы традиционно не рассматриваются как объекты, способные занимать место в пространстве. Но ABT-программы будут играть скорее роль законов, чем роль вещей и событий (фактов). Правда, особых законов. Ведь не обязательно относиться к законам природы как к данностям. Можно рассматривать их и как своего рода предписания к действию, предписания, подлежащие неукоснительному выполнению самой природой. До сих пор природа успешно «вычисляла» будущее. Справится ли она с этим делом в дальнейшем – вот вопрос.

Компьютеры, способные выполнять ABT-программы, будем называть ABT-компьютерами. Сформулируем постулат, касающийся ABT-программ и ABT-компьютеров, который ввиду его принципиальной важности выделим особо.

 

Постулат существования:

Любой объект может появиться в памяти Mm

или исчезнуть из нее только в результате

выполнения процессором Pr соответствующего
оператора языка программирования ABT

 

Программы на языке ABT являются, по определению, конечной последовательностью инструкций

                Ii0

                Ii1

                 .

                 .

                 .

                Iin

(где i0, i1, ..., in - натуральные числа и ij < ik, если j < k), которые выполняются одна за другой сверху вниз, если только нет команды изменить порядок их выполнения.

Каждая инструкция порождает элементарный процесс и содержит либо единственный оператор языка ABT, либо представлена в виде составного оператора

                IF условие THEN оператор ,

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

Оператор GOTO. Хорошо известный оператор безусловного перехода. Используется в ABT-программах в виде конструкции

                GOTO Ij,

где Ij - одна из инструкций соответствующей ABT-программы. Его действие ничем не отличается от поведения аналогичных операторов в обычных языках программирования.

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

Следующие два оператора специфичны, поэтому их характеристика будет более подробной.

Оператор выбора CHOOSE. Применяется в ABT-программах в следующей форме.

                CHOOSE список переменных | условие

В этой записи условие означает то же самое, что и в случае оператора IF...THEN, за исключением того, что условие должно содержать все переменные из списка переменных, причем переменные не должны быть связанными (т.е. в условии не должно быть кванторов по этим переменным). На список переменных также накладываются ограничения: он не должен содержать повторных вхождений одной и той же переменной, и в него не могут входить переменные, значения которых уже размещены в памяти Mm. Поскольку вопрос о том, значения каких переменных размещены в памяти Mm, требует анализа хода выполнения соответствующей ABT-программы, последнее ограничение имеет не синтаксический, а семантический характер.

Более формально синтаксическую форму оператора CHOOSE можно представить в виде записи

                CHOOSE X0,X1,X2,...,Xn | условие(X0,X1,X2,...,Xn) ,

где Xi - некоторая переменная, причем переменные Xi и Xj различны, если i¹j. Все выражение может быть прочитано как «Выбрать объекты (множества) X0,X1,X2,...,Xn такие, что выполняется предикат условие(X0,X1,X2,...,Xn)».

Сформулируем условия выполнимости оператора CHOOSE в общем виде. Если процессор Pr ABT-компьютера @= выполняет синтаксически правильную инструкцию I вида

                CHOOSE X0,X1,X2,...,Xn | условие(X0,X1,X2,...,Xn)

и предусловие P

                Mm(X0)=Æ & Mm(X1)=Æ & Mm(X2)=Æ &...& Mm(Xn)=Æ

ложно, выполнение завершается аварийно: произойдет авост.

Если P истинно, процессор Pr пытается найти (выбрать) такие объекты (множества) S0,S1,S2,...,Sn, которые, будучи присвоены в качестве значений переменным X0,X1,X2,...,Xn соответственно, обеспечивают истинность условия инструкции I. Затем процессор Pr пытается разместить в памяти Mm объекты S0,S1,S2,...,Sn.

Если объектов (множеств) S0,S1,S2,...,Sn, удовлетворяющих условию инструкции I и способных поместиться в свободной области памяти Mm, не существует, выполнение I завершается авостом. В противном случае (т.е. если требуемые объекты существуют и памяти для их размещения достаточно) выполнение I завершается успешно в состоянии, в котором истинны следующие постусловия:

                Mm(Si) ¹ Æ для всех i,  0 Ј i Ј n ;                условие(S0,S1,S2,...,Sn) .

Приведём пример конкретной ABT-программы. Пусть T – какая-либо теория в не более, чем счётном языке первопорядкового исчисления предикатов. Рассмотрим синтаксически правильную программу

                I1 CHOOSE X | (X |= T)

                I2 GOTO I1

Выполнение первой инструкции состоит в нахождении модели теории T. Но если теория Т противоречива, она не имеет модели и выполнение I1 в соответствии с семантикой оператора CHOOSE завершится аварийно. Однако и в том случае, если теория Т имеет модель, это не гарантирует успешности выполнения инструкции I1. Например, если память АВТ-компьютера, на котором выполняется данная программа, конечна и теория Т не имеет конечных моделей, попытка выполнить I1 приведет к авосту.

Пусть теперь память Mm счётна (т.е. |Mm| = w). Если теория T непротиворечива, то в соответствии с теоремами логики существуют счётные модели теории Т. Одна из таких моделей будет найдена процессором Pr и размещена в памяти Mm. А если память Mm несчетна и Т имеет бесконечную модель, то процессор Pr мог бы выбирать между неизоморфными моделями теории Т, так как наряду со счетными моделями теория Т имела бы и несчетные модели. Но сказать, какой из возможных исходов будет иметь место до выполнения инструкции I1, невозможно в принципе, так что в общем случае при использовании оператора CHOOSE мы имеем дело с ситуацией недетерминированного выбора. В некотором роде оператор выбора CHOOSE близок к аксиоме выбора: их объединяет неконструктивный (в смысле математического конструктивизма) характер получения результатов.

При условии успешного выполнения инструкции I1 рассматриваемой ABT-программы процессор Pr приступит к выполнению инструкции I2, в соответствии с которой произойдет возврат к инструкции I1. Как только осуществится этот переход по GOTO, возникнет авост. Почему? В силу того обстоятельства, что Mm(X) ¹ Æ после первого выполнения инструкции I1. Но оператор выбора CHOOSE в соответствии с определением не может применяться к переменной, в отношении значения которой выбор был уже сделан, а само это значение было размещено в памяти Mm. Таким образом, независимо от того, противоречива теория Т или нет, все равно выполнение данной ABT-программы завершится аварийно.

Очевидно, наряду с оператором, выбирающим объекты и размещающим их в памяти ABT-компьютера, необходим также оператор, аннулирующий результаты предшествующих актов выбора и освобождающий память для размещения новых объектов.

Оператор уничтожения DELETE. Его синтаксис предельно прост:

                DELETE список переменных ,

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

                DELETE  X0,X1,X2,...,Xn

Теперь определим семантику рассматриваемого оператора.

Если процессор Pr ABT-компьютера @= выполняет синтаксически правильную инструкцию I вида

                DELETE  X0,X1,X2,...,Xn ,

и предусловие P

                Mm(X0)¹Æ & Mm(X1)¹Æ & Mm(X2)¹Æ &...& Mm(Xn)¹Æ

ложно, выполнение завершается аварийно: произойдет авост.

Если P истинно, процессор Pr завершит выполнение инструкции I в состоянии, в котором будет истинным следующее постусловие:

                Mm(Xi) = Æ для всех i,  0 Ј i Ј n .

Воспользуемся оператором DELETE для модификации рассматриваемого примера ABT-программы в предположении, что теория T имеет модель и память Mm бесконечна.

Расположить инструкцию с оператором DELETE в данной программе, содержащей всего две инструкции, можно тремя следующими способами.

            (p1)                                        (p2)                                        (p3)I1 CHOOSE X| X |= T            I1 CHOOSE X| X |= T            I1 DELETE XI2 GOTO I1                             I2 DELETE X                         I2 CHOOSE X| X |= TI3 DELETE X                         I3 GOTO I1                             I3 GOTO I1

Очевидно, ABT-программа p1 успешно работать не будет по той же самой причине, что и исходная программа. Зато с ABT-программой p2 все в порядке: осуществив выбор модели теории T в соответствии с инструкцией I1, процессор Pr перейдет к выполнению инструкции I2. Так как на этот момент предусловие Mm(X) ¹ Æ истинно, процессор Pr завершит выполнение I2 в состоянии Mm(X) = Æ и, выполняя инструкцию I3, перейдет по GOTO к I1. Поскольку предусловие Mm(X) = Æ истинно, инструкция I1 будет вновь выполнена и т.д. – процесс выполнения программы p2 никогда не завершится.

Осталось проанализировать третью альтернативу. Для того чтобы выполнить ABT-программу p3, процессор Pr должен вначале выполнить инструкцию I1, что возможно лишь в том случае, если Mm(X) ¹ Æ. Но в соответствии с постулатом существования объект X может появиться в памяти ABT-компьютера только в результате действия оператора CHOOSE, который должен выполняться после команды DELETE, так как выполнение инструкции I1 с оператором DELETE предшествует выполнению инструкции I2 с оператором CHOOSE в программе p3.

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

Действительно, предположим, что процесс выполнения ABT-программы p3 не имел начала, т.е. всякому очередному выполнению любой инструкции программы p3 предшествовало бесконечное число реализаций этой инструкции. Такое предположение непротиворечиво и потому вполне допустимо. В самом деле, перед тем, как в очередной раз выполнить инструкцию I1, процессор Pr выполнил инструкцию I3, а перед этим – инструкцию I2, после чего ABT-компьютер перешел в состояние с Mm(X) ¹ Æ. Переход по GOTO к I1 сохранил это состояние, так что истинность предусловия оператора DELETE была обеспечена. После успешного выполнения I1 стало истинным утверждение Mm(X) = Æ, необходимое для выполнения I2 и т.д.

Наглядно описанный процесс можно изобразить следующей схемой:

                ..., I1,I2,I3,I1,I2,I3,I1, ... .

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

 Постулат реализуемости:
Если предположение о том, что АВТ-программа p
выполнима, непротиворечиво, то программа p
выполняется
 

Интересное, на наш взгляд, различие между ABT-программами p2 и p3 заключается в том, что p3 можно выполнить только при условии отсутствия начала процесса выполнения, тогда как p2 выполнима независимо от того, имел процесс ее выполнения начало или нет. Гипотетический процесс выполнения p2, имеющий первый шаг, был описан выше. Что касается описания воображаемого выполнения p2 в ходе не имеющего начала процесса, то оно практически полностью повторяет соответствующее описание выполнения p3. Мы говорим о гипотетических или воображаемых процессах выполнения p2 потому, что если допустить наличие не имеющих начала процессов наряду с «нормальными», то на вопрос о том, процесс какого типа осуществляется при выполнении p2 на данном ABT-компьютере, нельзя ответить однозначно. С равным успехом это может быть как первая, так и вторая разновидность процессов.

Обсуждаемое различие важно для приложений в философии. Так, проблема начала времени не имеет устраивающего всех исследователей единственного решения. Если принимается тезис о том, что эта проблема неразрешима, то для моделирования течения времени больше подходит конструкция, аналогичная программе p2; принятие тезиса об отсутствии начала течения времени заставит прибегнуть к программам типа p3. Наконец, на языке ABT-программ нетрудно выразить и идею начала времени. Для этого достаточно перед выполнением бесконечного цикла выполнить инструкцию, которая больше уже выполняться не будет. Например, применительно к программе p2 достаточно добавить к списку ее инструкций команду GOTO I1.

                            (p4)                I0   GOTO I1                I1   CHOOSE X| X |= T                I2   DELETE X                I3   GOTO I1Полученная ABT-программа p4 может быть выполнена только в ходе процесса, имеющего начало. Действительно, первой будет выполнена инструкция I0, а дальше возникнет бесконечный цикл. Схематически                I0,I1,I2,I3,I1,I2,I3,I1, ... .Креативная ABTС-вычислимость

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

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

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

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

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

Но в реальности свойства появляются и исчезают! Например, когда-то не существовало свойства Разумное животное, но ныне это свойство существует. Мы можем быть также уверены, что существует соответствующее этому свойству конечное множество разумных животных. Однако это вовсе не означает, что мы должны быть готовы моделировать такое множество посредством некоторого построения, начинающегося с пустой совокупности. Натуральные числа, допустим, мы так и строим: объявляем, что 0 =Df Æ, 1 =Df {Æ}, 2 =Df {Æ, {Æ}} и т.д. Поведение получаемых объектов регулярно, закономерно и предсказуемо. Но не будет ли бессмысленным предположение, что подобным путем можно получить множество разумных животных? Нам представляется, что будет. Абсурдно полагать, что множество разумных животных возникнет по правилам теории множеств на каком-то этапе порождения множеств из пустой совокупности.

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

И всё же имеется исключение из общего правила. На роль иррегулярных объектов теории множеств мы предлагаем праэлементы или атомы. Атомы являются праэлементами потому, что они исходные объекты в том смысле, что не получены из каких-то ранее построенных множеств. Праэлементы являются атомами (неделимыми) потому, что им, как и пустому множеству Æ, ничего не принадлежит в качестве элемента. Тем не менее, они не равны пустому множеству. Атом привлекателен тем, что с чисто математической точки зрения он почти ничего из себя не представляет. В этом плане он совсем не похож, например, на такой экзотический математический объект, как недостижимый кардинал, про который очень много можно сказать нетривиального в математическом смысле. Короче, атомы настолько свободны от математических свойств, насколько это вообще представляется возможным. Тем не менее, они – чисто формальные объекты, которые могут быть введены в теорию множеств посредством соответствующих аксиом[13]. Именно это обстоятельство дает нам шанс для построения формальной модели творения нового из ничего.

Язык абстрактного программирования АВТС получается из языка АВТ добавлением оператора CREATE. Формально синтаксическую форму оператора CREATE можно представить в виде записи

                CREATE X0,X1,X2,...,Xn | условие(X0,X1,X2,...,Xn) ,

где Xi - некоторая переменная, причем переменные Xi и Xj различны, если i¹j. Все выражение может быть прочитано как «Создать атомы или множества атомов X0,X1,X2,...,Xn такие, что выполняется предикат условие(X0,X1,X2,...,Xn)».

Сформулируем условия выполнимости оператора CREATE в общем виде. Если процессор Pr ABT-компьютера @= выполняет синтаксически правильную инструкцию I вида

                CREATE X0,X1,X2,...,Xn | условие(X0,X1,X2,...,Xn)

и предусловие P

                Mm(X0)=Æ & Mm(X1)=Æ & Mm(X2)=Æ &...& Mm(Xn)=Æ

ложно, выполнение завершается аварийно: произойдет авост.

Если P истинно, процессор Pr пытается создать (сотворить из ничего) такие атомы или множества атомов S0,S1,S2,...,Sn, которые, будучи присвоены в качестве значений переменным X0,X1,X2,...,Xn соответственно, обеспечивают истинность условия инструкции I. Затем процессор Pr пытается разместить в памяти Mm объекты S0,S1,S2,...,Sn.

Если атомов или множеств атомов S0,S1,S2,...,Sn, удовлетворяющих условию инструкции I и способных поместиться в свободной области памяти Mm, логически не может существовать, выполнение I завершается авостом. В противном случае (т.е. если условие(X0,X1,X2,...,Xn) непротиворечиво и памяти для размещения новых объектов S0,S1,S2,...,Sn достаточно) выполнение I завершается успешно в состоянии, в котором истинны следующие постусловия:

                Mm(Si) ¹ Æ для всех i,  0 Ј i Ј n ;                условие(S0,S1,S2,...,Sn) .

Завершим наши усилия сотворением нового атома из ничего в предположении, что памяти достаточно для размещения одного атома. Рассмотрим следующую элементарную АВТС-программу.

I1 CREATE X | (X ¹ Æ) & "Z(Z Ï X)

В соответствии с постулатом существования, до выполнения этой программы Mm(X) = Æ. Условие (X ¹ Æ) & "Z(Z Ï X) указывает, что создаваемый Х будет атомом (а не множеством атомов). В ходе выполнения (согласно постулату реализуемости) оператора CREATE атом S, присваиваемый переменной Х, появляется ниоткуда, возникает в истинном смысле из ничего. Но до выполнения оператора CREATE атом S нигде не существовал ни в каком качестве, т.е. S будет совершенно новым. После выполнения программы имеем Mm(S) ¹ Æ и (S ¹ Æ) & "Z(Z Ï S).

 



* Работа выполнена при поддержке РГНФ, проект № 07–03–00203а.

[1] Бунге М. Причинность. Место принципа причинности в современной науке. М., 1962.

[2] Об этом, а также о проблеме производительной причинности подробно говорится в находящейся в печати работе: Анисов А.М. Недетерминированная вычислимость: Философские основания // Логические исследования. Вып. 15. М., 2008. С. 5-30.

[3] Анисов А.М. Время как вычислительный процесс // Замысел Бога в теориях физики и космологии. Время. СПб. – Изд-во С.-Петербургского ун-та, 2005. С.53-71.

[4] Пенроуз Р. Тени разума: в поисках науки о сознании. Москва - Ижевск, 2005. С. 546.

[5] Машины Тьюринга-Поста описываются во многих книгах (напр., см.: Мальцев А.И. Алгоритмы и рекурсивные функции. М., 1986.). Более близка к реальным ЭВМ так называемая МНР-машина (машина с неограниченными регистрами), обладающая теми же вычислительными возможностями, что и машины Тьюринга-Поста (см.: Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М., 1983.).

[6] Проблема вечного возвращения особенно остро стоит в случае компьютерного моделирования становления или течения времени. См.: Анисов А.М. Моделирование становления на ЭВМ //Логические исследования. Вып.2. М., 1993.

[7] Подробности см. в работе: Анисов А.М. Время и компьютер. Негеометрический образ времени. М., 1991.

[8] См.: Кекрис А., Московакис Я. Рекурсия в высших типах //Справочная книга по математической логике. Ч.III. Теория рекурсии. М., 1982; Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. М., 1972; Шор Р. Теория a-рекурсии //Справочная книга по математической логике. Ч.III. Теория рекурсии. М., 1982.

[9] Кекрис А., Московакис Я. Рекурсия в высших типах. С. 166-167.

[10] Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. С. 520.

[11] Полное описание можно найти в работе: Анисов А.М. Время и компьютер.

[12] Анисов А.М. Креативность // «Credo new», 2002, № 1. С. 103-116.

[13] См., напр.: Йех Т. Теория множеств и метод форсинга. М., 1973.vv


Вернуться назад