Текст книги "Жар холодных числ и пафос бесстрастной логики"

Автор книги: Борис Бирюков

Соавторы: В. Тростников
сообщить о нарушении

Текущая страница: 9 (всего у книги 14 страниц)

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

Гносеологические выводы из теоремы Гёделя нужно делать с большой осторожностью. То, на что наталкивает нас в философском плане эта теорема, высказано Э. Нагелем и Дж. Ньюменом в следующей форме: «Заключения, к которым пришел Гёдель, порождают, естественно, вопрос, можно ли построить вычислительную машину, сравнимую по своим «творческим» математическим возможностям с человеческим мозгом. Современные вычислительные машины обладают некоторым точно фиксированным запасом команд, которые умеют выполнять их элементы и блоки; команды соответствуют фиксированным правилам вывода некоторой формализованной аксиоматической процедуры. Таким образом, машина решает задачу, шаг за шагом выполняя одну из «встроенных» в нее заранее команд. Однако, как видно из гёделевской теоремы о неполноте, уже в элементарной арифметике натуральных чисел возникает бесчисленное множество проблем, выходящих за пределы возможностей любой конкретной аксиоматической системы, а значит, и недоступных для таких машин, сколь бы остроумными и сложными ни были их конструкции и с какой бы громадной скоростью ни проделывали они свои операции. Для каждой конкретной задачи в принципе можно построить машину, которой эта задача была бы под силу, но нельзя создать машину, пригодную для решения любой задачи. Правда, и возможности человеческого мозга могут оказаться ограниченными, так что и человек тогда сможет решить не любую задачу. Но даже если это так, структурные и функциональные возможности человеческого мозга пока еще намного больше по сравнению с возможностями самых изощренных из мыслимых пока машин... Единственный непреложный вывод, который мы можем сделать из гёделевской теоремы о неполноте, состоит в том, что природа и возможности человеческого разума неизмеримо тоньше и богаче любой из известных пока машин»^[7].

Действительно, электронная вычислительная машина есть универсальный инструмент вычисления, о чем пойдет речь ниже. Конечно, в самой схеме ЭВМ вовсе не заложен аксиоматически-дедуктивный метод получения теорем. Но машину в принципе всегда можно «научить» выводить теоремы с помощью заданных правил вывода из заданных аксиом (правда, соответствующие программы могут оказаться очень сложными). В результате машина «овладевает» дедуктивным методом доказательства теорем и, естественно, оказывается подвластной ограничениям, которые налагают на этот процесс положения Гёделя. Но эти же самые ограничения распространяются ина человека, если он работает строго по дедуктивному методу^[8].

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

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

7. ЧТО ТАКОЕ «МОЖНО ВЫЧИСЛИТЬ»?

Блестящее исследование Гёделя оказалось возможным благодаря тому, что математический материал, относящийся к логике и теория вывода, достиг уже «критической массы». В логике и основаниях математики образовался солидный багаж конкретных достижений. Стала известной специалистам концепция формализованной арифметики Фреге. Была сформулирована формальная аксиоматическая система теории множеств Цермело—Франкеля. Вышли в свет Principia Mathematica. В свете успехов алгебры новую оценку получили работы Буля. Манифесты Брауэра привели к углубленному анализу классической логики и впервые в истории поставили вопрос о ее пересмотре. Наконец, была провозглашена программа Гильберта, которая хотя и оказалась невыполнимой в центральном пункте, придала исследованиям новый дух и поставила перед ними новые задачи.

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

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

«Развитие математики в направлении все увеличивающейся строгости», о котором писал Гёдель, а еще более – критика математического платонизма привели к постановке до тех пор не стоявших вопросов: что такое конструктивный математический объект, то есть объект математического построения? Какие доказательства, выводы, числа, функции, формулы можно считать осуществимыми, вычислимыми?

Разберемся в сущности этой проблемы. Возьмем, например, число 2⁶⁴. Несмотря на то, что оно очень велико, его можно фактически записать в обычной десятеричной системе счисления. Число же 4⁴⁴⁴ таким образом записать уже нельзя – не хватит ни бумаги, ни типографской краски во всем мире. Но вряд ли есть смысл исключать из математики такие числа. Как и всякая теоретическая наука, математика нуждается в отвлечении от реальных условий, в использовании идеализации. В частности, в математических суждениях и выкладках полезно допускать, что в распоряжении рассуждающего всегда имеется достаточно большое количество бумаги и чернил или что доска, на которой пишутся формулы, достаточно велика. Полезно также предполагать, что имеется достаточно много времени для производства расчетов. При этих вполне разумных допущениях^[1] число 4⁴⁴⁴существует как бы фактически, являясь построяемым – конструктивным – объектом, хотя никто и никогда не выпишет его на бумаге. Конструктивность объекта в таком понимании сводится к тезису о его потенциальной осуществимости: объект, считающийся конструктивным, мог бы быть фактически получен (выписан), если бы мы располагали необходимым для этого временем (которое может быть необозримо большим, но в любом случае конечным), пространством (на размеры которого также не накладывается каких-либо ограничений) и материалами (масса которых может превосходить массу известной нам части Вселенной).

Для построения конструктивного объекта требуется осуществить всегда конечное число тех или иных актов поведения—действий, операций. Какой характер могут носить эти акты поведения? Они могут быть реальными действиями, совершаемыми над знаками как материальными образованиями, но могут быть действиями умственными – представлениями о реальных действиях. Далее, чтобы избежать опасности (которая после обнаружения парадоксов теории множеств стала очевидной) допущения в отдельных фазах построения объекта чреватых ошибками интуитивных обобщений, требуется, чтобы эти действия имели простой, элементарный характер. Различный выбор элементарных действий – шагов процесса, приводящего к построению конструктивного объекта, определяет разные подходы к уточнению идеи вычислимости. Мы рассмотрим три таких подхода. Первый подход – рекурсивный.

Определение рекурсивной функции содержалось уже в знаменитой статье Гёделя. Позже Гёдель, а также Ж. Эрбран, развили это понятие. Но особое звучание рекурсивным функциям придал американский логик и математик Алонзо Чёрч (род. в 1903 г.).

Дадим более аккуратное, чем в предшествующей главе, определение рекурсивной функции. Оно состоит из четырех пунктов. Всюду впредь в качестве аргументов и значений функций фигурируют лишь натуральные числа 0, 1, 2, ... (такие функции называют теоретико-числовыми, или арифметическими).

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

I. Подстановка. Из функции получается новая функция, если вместо всех ее аргументов подставить функции^[2].

II. Примитивная рекурсия^[3]. Она заключается в получении (n + 1)-местной функции f из данных n-местной функции g и (n + 2)-местной функции h по схеме:

f(х1, х2,... хn, 0) = g(x1, х2,..., xn),

f(x1, х2,..., хn, m') = h(х1, х2,..., хn, m, f(х1, х2, ..., хn, m)).

Здесь n = 1,2, ...; для случая, когда аргументы х1, х2, ...,Хn (называемые параметрами рекурсии) отсутствуют, отдельно устанавливается f(0) =r (где r – фиксированное целое неотрицательное число), f(m') = h(m, f(m)). Здесь m'—число, непосредственно следующее за числом m в натуральном раду.

III. Мю-операция (или (μ-оператор). Пусть дана (n + 1)-местная функция (функция от n + 1 аргумента) g; по ней (μ-оператор строит n-местную функцию f следующим образом.

Для любого набора чисел х1, х2, ..., Хn f(х1, x2,... хn) равно наименьшему целому неотрицательному числу а, удовлетворяющему условию g (х1 ..., xn, а) = 0. Это число обозначается через рy(g (х1, ..., хn, у) = 0), откуда и название операции.

Если такого числа для набора чисел x1, х2, ..., хn не существует, то функция f на этом наборе не определена.

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

(а) Многоместные функции (от n аргументов, n = 0, 1,2....) Nⁿ, тождественно-равные нулю, то есть функции, для которых верно:

Nⁿ (х1, х2, ..., Хn) = 0 при любых значениях аргументов.

(б) Одноместная функция S «следования за», то есть функция, для которой выполняется равенство S(х) = х' где штрих означает взятие числа, непосредственно следующего за x в натуральном ряду.

(в) n-местные проектирующие функции Iⁿi, Для которых Iⁿi{х1, .... xn) = xi ( i = 1, 2, ..., n; n = 1, 2, 3, ...).

Функции, получающиеся из исходных конечным числом применений схем порождения I и II, называются примитивно рекурсивными; как очевидно, эти функции являются всюду определенными. К примитивно рекурсивным относятся не все, а только часть арифметических функций (правда, наиболее часто встречающееся такого рода функции примитивно рекурсивны). Если разрешить применять схему порождения III, то функции, которые будут таким образом возникать, называются частично рекурсивными. Хотя частично рекурсивные функции – как и примитивно рекурсивные – в конечной счете получаются из исходных (примитивно рекурсивных) функций (а), (б), (в), они в общем случае не всюду определены; это вызывается спецификой (μ-оператора, который из всюду определенной может породить частичную (и даже нигде не определенную) функцию. Если частично рекурсивная функция от n аргументов является всюду определенной (то есть если она определена для любого набора из n натуральных чисел), она называется общерекурсивной функцией. Таким образом, каждая примитивно рекурсивная функция является общерекурсивной, а каждая общерекурсивная – частично рекурсивной. Однако существуют частично рекурсивные функции, не являющиеся общерекурсивными, и общерекурсивные, не являющиеся примитивно рекурсивными.

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

Если исходная функция принадлежит к типу (а), то для любого набора значений ее аргументов ее значением является нуль. Эта функция «аннулирует» любой набор. Операция очень проста, она не требует особой фантазии или интуиции.

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

Смысл проектирующих функций тоже очень прост: каждая из них отыскивает i-тый по порядку аргумент и объявляет его значением функции. Вычисление значений такой Функции выполняется с помощью обыкновенного счета: если дан определенный набор значений аргументов некоторой функции типа (в), то считывается нижний индекс i в ее обозначении и в упомянутом наборе отыскивается (с помощью счета) i-тое число; это число и оказывается значением функции.

Что же представляют собой акции, позволяющие строить из одних рекурсивных функций другие, вообще говоря, более сложные рекурсивные функции?

Подстановка есть не что иное, как вычисление, разбитое на два этапа: сначала вычисляются значения всех «внутренних» функций, а потом – значение «внешней» функции при аргументах, равных полученным на предыдущем этапе числам. Это – акт суперпозиции, последовательного выполнения однотипных операций. Например, суперпозиция функций I³i и S (где S – внешняя функция) порождает функцию от трех аргументов: f(х1, х2, х3) = S (I³i (х1, х2, х3)); суперпозиция функций S, I¹1, N¹ и I³1 (внешняя функция) порождает одноместную функцию q(х) = I³1 (S(х), I¹1(х), N¹(х)) и т. д. Самый придирчивый критик не заподозрит в подобных процедурах присутствия чего-либо неясного.

Вычисление по схеме примитивной рекурсии тоже не вызывает недоверия с точки зрения своей четкости и общепонятности. Это мы уже видели на примерах вычисления значения функции «усеченное вычитание», определенной рекурсивно (см. с. 127)^[4]. Собственно говоря, мы очень часто пользуемся методом построения какой-то последовательности, формируя каждый ее член по предыдущим членам. В данной схеме следует обратить внимание на то, что вычисление каждого последующего значения нуждается в знании только одного, непосредственно предыдущего, значения. Это, конечно, простейший вариант подобного типа вычислений. Но тем не менее при вычислении по схеме рекурсии значения некоторой функции для какого-то значения ее аргумента (например, для числа 137) приходится на промежуточных фазах вычисления находить значения функции для всех предыдущих значений аргумента: 0, 1, 2, ..., 136, хотя каждый раз все значения, кроме самого последнего, мы можем забывать, стирать с доски и т. д.

Акция, соответствующая четвертому пункту (мю-операция), иначе называется операцией взятия наименьшего числа. Ее включили в определение рекурсивных функций, так сказать, неохотно, под давлением суровой необходимости (в первоначальном определении у Гёделя мю-операции не было), поскольку без нее, как выяснилось, не могут быть получены некоторые функции, играющие в математике важную роль. Как мы отметили выше, функции, в которых участвуют только подстановка и рекурсия, называют примитивно рекурсивными, особо выделяя тем самым мю-операцию. Каков же познавательный статус этой операции? Чем существенным отличается она от подстановки и рекурсии?

Посмотрим сначала, как конкретно функционирует мю-операция. Пусть надо задать способ нахождения наименьшего числа у, для которого выполняется некое условие g°(x1, x2, y) = 0, имеющее вид 100 ∸ х1•х^y₂ = 0 (напомним, что это равенство равносильно неравенству х1 • х^y₂ >> 100). Это означает, что над функцией g° (х1, х2, у) надо произвести мю-операцию – определить функцию f° (х1,x2) = μy(g° (x1, x2, y) = 0) = μy(100 ∸ x1 • х^y₂ = 0).

Сделать это нетрудно, так как функция g° задана, и мы для каждого набора значений ее аргументов х1, х2 можем установить (путем перебора, начинающегося с нуля) то наименьшее значение ее аргумента у, при котором g°(х1, х2, у) = 0. В самом деле, пусть значения аргументов х1, и x2 например, таковы: х1 = 3, х2 = 2. Тогда для вычисления f° (3,2,) надо поступить следующим образом.

1. Положим y = 0; вычислим g°(3, 2, 0). Получим:

100 ∸ 3 • 2° = 100 ∸ 3 • 1 = 100 ∸ 3 = 97. Условие не выполнено, поэтому сделаем следующий шаг, перейдем к значению y = 1.

2. Положим y = 1; вычислим g°(3, 2, 1). Получим:

100 ∸ 3 • 21 = 100 ∸ 3 • 2 = 100 ∸ 6 = 94. Требуемое условие не выполнено, так что возьмем следующее значение у.

3. Положим y = 2; вычислим g° (3, 2, 2). Получим:

100 – 3 • 22 = 100 ∸ 3 • 4 = 100 ∸ 12 = 88. Условие не выполнено. Перейдем к следующему значению у,

4. Положим y = 3; вычислим g° (3, 2, 3). Получим:

100 ∸ 3 • 23 = 100 ∸ 3 • 8 = 100 ∸ 24 = 76. Требуемое условие не выполнено; берем следующее значение у.

5. Положим y = 4; вычислим g° (3, 2, 4). Получим:

100 ∸ 3 • 24 = 100 – 3 • 16 = 100 – 48 = 52. Требуемое условие не выполнено; сделаем еще один шаг.

6. Положим y = 5; вычислим g° (3, 2, 5). Получим:

100 ∸ 3 • 25 = 100 ∸ 3 • 32 = 100 ∸ 96 = 4. Требуемое условие не выполнено, и мы возьмем на единицу большее значение у.

7. Положим у = 6; вычислим g° (3, 2, 6). Получим:

100 ∸ 3 • 26 = 100 ∸ 3 • 64 = 100 ∸ 192 = 0. Условие на этот раз выполнено, поэтому в качестве значения функции f° берется число 6—мы пишем: f° (3, 2) = μy(g° (3, 2, 6) = 0) = 6.

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

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

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

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

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

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

По мере углубления в проблему выяснялось, что все «обиходные» функции, принятые в анализе, выражаются через рекурсивные функции, так что в этом плане обеднения не происходит. Учитывая этот факт, А. Чёрч в 1936 году выдвинул гипотезу, получившую название тезиса Чёрча, которая может быть сформулирована следующим образом: вычислимы те, и только те, математические объекты, которые могут быть получены с помощью общерекурсивиых функций. Другими словами, Чёрч предположил, что общерекурсивных функций достаточно для реализации любой строгой и однозначно определяемой вычислительной процедуры.

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

Иногда шутят: в математике тезисы хороши тем, что их не не нужно доказывать. Действительно, тезис Чёрча (как и два других тезиса, о которых речь пойдет ниже) недоказуем математически. Об этом очень ясно сказал Ласло Кальмар^[6]. «В своем знаменитом исследовании неразрешимых арифметических проблем Чёрч^[7] использовал рабочую гипотезу о тождественности понятия эффективно вычислимой функции понятию общерекурсивной функции... Эта рабочая гипотеза известна под названием тезиса Чёрча. Она имеет несколько эквивалентных форм... В настоящей статье я не буду опровергать тезис Чёрча. Этот тезис не есть математическая теорема, которая может быть доказана или опровергнута в строго математическом смысле, поскольку он устанавливает тождество двух понятий, из которых только одно определено математически, в то время как другое употребляется математиками без точного определения. Конечно, тезис Чёрча можно замаскировать под определение: мы называем арифметическую функцию эффективно вычислимой тогда, и только тогда, когда она является общерекурсивной; однако в этом случае появляется опасность, что в будущем кто-нибудь построит функцию, которая, с одной стороны, не будет эффективно вычислимой в установленном таким образом смысле, а с другой стороны, ее значения будут очевидно эффективно вычислимыми для любых заданных аргументов.

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

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

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

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

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

В том же году (1936), когда Чёрч выдвинул свой тезис о рекурсивных функциях, английский математик и логик Алан Тьюринг (1912—1954) в поисках элементарных действий, к которым можно свести всякую процедуру вычисления, решил стать на путь ее «механизации». Он исходил из представления, что механические операции являются наиболее простыми и надежными. Однако Тьюринг был далек от стремления изготовить какой-то механизм из железа или других материалов; его интересовала теоретическая сторона дела. Ему важно было убедиться в принципиальной осуществимости такой машины, которая в состоянии проделать любую вычислительную процедуру^[9].

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

Предполагается, что машина Тьюринга реагирует на знаки из некоторого набора знаков – внешнего алфавита, наносимые в ячейках некоторой (бумажной или иной) ленты; в каждой ячейке может быть нанесен только один знак;

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

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

Набор действий, доступных машине Тьюринга, весьма ограничен. Она может выполнить следующие операции:

(1) перейти в другое внутреннее состояние (или остаться в прежнем состоянии);

(2) стереть знак, напечатанный в обозреваемой ею ячейке ленты, напечатать вместо него другой или оставить знак без изменения;

(3) передвинуть бумажную ленту на стандартное расстояние (скажем, на 1 см), соответствующее размеру ячейки, в левую или в правую сторону;