Неразрешимость проблемы Гильберта

⇐ ПредыдущаяСтр 7 из 58Следующая ⇒

Мы теперь вплотную подходим к той цели, ради которой Тьюринг с самого начала разрабатывал свою теорию — получить ответ на вопрос, заключенный в общей проблеме алгоритмической разрешимости, поставленной Гильбертом, а именно: существует ли некая механическая процедура для решения всех математических задач, принадлежащих к некоторому широкому, но вполне определенному классу? Тьюринг обнаружил, что он мог бы перефразировать этот вопрос следующим образом: остановится ли в действительности n- я машина Тьюринга, если на ее вход поступит число m Эта задача получила название проблемы остановки . Не так сложно составить список команд, для которых машина никогда не остановится при любом m (как, например, в случаях n = 1 или 2, рассмотренных в предыдущем разделе, а также во всех случаях, когда вообще отсутствует команда STOP ). Точно так же существует множество списков команд, для которых машина будет останавливаться всегда, независимо от вводимого числа m (например, T ₁₁ ). Кроме того, некоторые машины при работе с одними числами останавливались бы, а с другими — нет. Совершенно очевидно, что алгоритм, который никогда не прекращает работу, бесполезен. Это, собственно, и не алгоритм вовсе. Поэтому важно уметь ответить на вопрос, приведет ли когда-нибудь работа машины T _n над данным числом m к какому-то ответу или нет! Если нет (т. е. процесс вычисления никогда не прекращается), то я буду выражать это следующей записью:

T _n(m ) = ^□.

(Сюда же включены машины, которые в ходе работы попадают в ситуацию, когда нет команды, определяющей их дальнейшее поведение, как это было в случае рассмотренных выше фиктивных машин T ₄ и T ₁ . К сожалению, наша на первый взгляд работоспособная машина T ₃ должна теперь также считаться фиктивной, т. е.

T ₃(m ) = ^□, поскольку результатом ее действия всегда будет просто пустая лента, тогда как нам, чтобы приписать номер полученному ответу, нужна хотя бы одна единица на выходе! Машина T ₁₁ , однако, совершенно полноправна, поскольку она производит единственную 1 . Результатом ее работы будет лента с номером 0, так что T ₁₁ (m ) = 0 для любого m .)

В математике весьма важно иметь возможность установить момент, когда машина Тьюринга остановится. Рассмотрим для примера уравнение

(х + 1)^ω⁺³ + (у + 1)^ω⁺³ = (z + 1)^ω⁺³.

(Не пугайтесь, даже если Вы не любите вникать в детали математических вычислений. Это уравнение используется здесь только в качестве примера, и от вас не требуется его глубокого понимания.) Это конкретное уравнение относится к известной (возможно, самой известной) и пока нерешенной математической проблеме. Проблема формулируется следующим образом: существует ли какой-либо набор х , у , z , ω , для которого это равенство выполняется. Знаменитое утверждение, записанное на полях «Арифметики» Диофанта великим французским математиком семнадцатого столетия Пьером де Ферма (1601–1665) и известное как «последняя теорема Ферма», гласит, что это равенство никогда не выполняется[48][49]. Будучи адвокатом по профессии, Ферма тем не менее был искуснейшим математиком своего времени. (Ферма был современником Декарта.) В своей записи он утверждал, что знает «воистину прекрасное доказательство» своей теоремы, но поля книги слишком малы, чтобы его привести. До сегодняшнего дня никому так и не удалось ни воспроизвести это доказательство[50], ни найти опровергающий это утверждение пример!

Очевидно, что для заданной четверки чисел (x , у , z , ω ) выяснить, выполняется это равенство или нет, можно простым вычислением. Значит, мы можем представить себе вычислительный алгоритм, который последовательно перебирает все возможные четверки чисел одну за другой и останавливается только тогда, когда равенство удовлетворяется. (Мы уже знаем, что для конечных наборов чисел существуют способы их кодирования на ленте вычислимым способом, а именно, в виде одного числа. Таким образом, перебор всех четверок можно провести, просто следуя естественному порядку соответствующих им одиночных чисел.) Если бы мы могли установить, что этот алгоритм никогда не останавливается, то это стало бы доказательством утверждения Ферма.

Сходным образом в терминах проблемы остановки машины Тьюринга можно перефразировать многие другие нерешенные математические проблемы. Примером такого рода проблем может служить так называемое предположение Гольдбаха: любое четное число, большее двух, может быть представлено в виде суммы двух простых чисел[51]). Процесс, с помощью которого можно установить, относится некоторое натуральное число к простым или нет, является алгоритмическим, поскольку достаточно проверить делимость данного числа на все числа, меньшие его, а это достигается с помощью конечного числа вычислительных операций. Мы можем придумать машину Тьюринга, которая перебирает четные числа 6, 8, 10, 12, 14…, пробуя все возможные способы разбиения их на пары нечетных чисел

6 = 3 + 3, 8 = 3 + 5, 10 = 3 + 7 = 5 +5,

12 = 5 + 7, 14 = 3 + 11=7 + 7…

и убеждаясь, что для каждого четного числа какое-то из разбиений образовано двумя простыми числами. (Очевидно, нам не надо проверять пары четных слагаемых, кроме 2 + 2, поскольку все простые числа за исключением 2 — нечетные.) Наша машина должна остановиться только в том случае, если она находит четное число, для которого ни одно из разбиений не является парой простых чисел. В этом случае мы получили бы контрпример к предположению Гольдбаха, т. е. нашли бы четное число, большее 2, которое не является суммой двух простых чисел. Следовательно, если бы мы могли установить, останавливается машина Тьюринга когда-нибудь или нет, то тем самым мы выяснили бы, справедливо предположение Гольдбаха или нет.

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

В сущности, его доказательство сводилось к следующему. Предположим, наоборот, что указанный алгоритм существует[52]. Тогда существует и некая машина Тьюринга Н , которая «решает», остановится ли в конце концов n -я машина Тьюринга, действуя на число m . Условимся, что результатом действия машины Н будет лента с номером 0 , если n -я машина не останавливается, и с номером 1 в противоположном случае:

Здесь мы могли бы воспользоваться способом кодирования пары (n , m ), использованным ранее для универсальной машины Тьюринга U . Однако это привело бы к проблеме технического характера, поскольку при некоторых n (например, n = 7) T _n будет определена некорректно, и маркер 111101 будет непригоден для отделения на ленте n от m . Чтобы избежать этой проблемы, будем полагать, что n представлено не в двоичной, а в расширенной двоичной форме, тогда как для m будет по-прежнему использоваться обычная двоичная запись. В этом случае комбинации 110 будет достаточно для разделения n и m . Использование точки с запятой в обозначении Н (n ; m ) в отличие от запятой в обозначении универсальной машины U (n , m ) указывает на это различие в кодировании.

Представим себе теперь бесконечную таблицу, в которую включены окончательные результаты действий всех возможных машин Тьюринга на все возможные (различные) входные данные. В этой таблице N - й ряд представляет собой результаты вычислений n - й машины Тьюринга, полученные при ее работе последовательно с m = 0, 1, 2, 3, 4…:

Я немного «сжульничал» и не стал располагать машины Тьюринга по порядку их действительных номеров. Если бы я так сделал, то получился бы список, начало которого выглядело бы слишком скучным, поскольку все машины при значениях n меньших 11 не дают ничего, кроме ^□, а для n = 11 мы имеем просто нули. Дабы сделать начало этой таблицы более интересным, я предположил, что мы использовали некую гораздо более эффективную систему кодирования. Фактически, я просто присвоил ячейкам более или менее произвольные значения, только чтобы дать вам общее представление о том, как может выглядеть эта таблица.

На самом деле нам не требуется, чтобы эта таблица была построена путем вычислений , скажем, с помощью некоторого алгоритма. (На самом деле, как мы увидим далее, такого алгоритма и не существует.) Достаточно просто представить себе, что каким-то образом истинный список попал в наше распоряжение, возможно, с помощью Бога! Если бы мы попытались получить эту таблицу с помощью вычислений, то именно символы ^□ вызвали бы затруднения, поскольку мы не могли бы с уверенностью сказать, когда в той или иной ячейке должен быть помещен символ ^□ — ведь соответствующие вычисления никогда не заканчиваются!

Тем не менее искомую таблицу можно , построить с помощью вычислительной процедуры, если использовать нашу гипотетическую машину Н , поскольку она могла бы определить, где на самом деле появляются значения ^□. Однако вместо этого мы используем машину Н для того, чтобы избавиться от появления значений ^□ в таблице, заменив их во всех случаях нулями. Это достигается за счет вычисления значения Н (n ; m ), предваряющего действие T _n на m , после чего мы позволим T _n производить соответствующие действия, только если H (n ; m ) = 1 (т. е. только тогда, когда вычисление T _n(m) приводит к определенному результату), и будем просто записывать в соответствующую ячейку 0 при Н (n ; m ) = 0 (т. е. если T _n (m ) = ^□). Мы можем записать эту новую процедуру, представляющую собой последовательное действие Н (n ; m ) и T(m), как

T _n(m) х Н (n; m ).

(Здесь я использую общепринятую в математике договоренность о последовательности выполнения действий, согласно которой операция, записанная справа , должна выполняться первой . Обратите внимание, что в этом случае можно символически записать ^□ х 0 = 0.)

Теперь таблица принимает следующий вид:

Заметьте, что, исходя из предположения существования машины Н , мы получаем ряды таблицы, состоящие из вычислимых последовательностей. (Под «вычислимой последовательностью» я понимаю бесконечную последовательность, элементы могут быть найдены один за другим посредством некоего алгоритма; это означает, что существует некоторая машина Тьюринга, которая, будучи применена поочередно к натуральным числам m = 0, 1, 2, 3, 4, 5…, производит члены рассматриваемой последовательности.) Обратите внимание на следующие два факта относительно этой таблицы. Во-первых, любая вычислимая последовательность натуральных чисел должна появиться где-то (может быть, далеко не сразу) среди рядов таблицы. Это свойство выполнялось уже и для исходной таблицы, содержавшей значения ^□. Мы просто добавили несколько рядов, чтобы заменить «фиктивные» машины Тьюринга (т. е. такие, которые приводят к ^□ хотя бы в одном случае). Во-вторых, считая, что машина Тьюринга H существует, мы получили таблицу вычислительным путем (т. е. с помощью некоторого определенного алгоритма), а именно, посредством процедуры T _n(m) х Н (n ; m ). Иными словами, существует некая машина Тьюринга Q , применение которой к паре чисел (n , m ) дает значение соответствующей ячейки таблицы. Для этой машины числа n и m на ленте можно кодировать таким же образом, как и для H , т. е. мы имеем

Q (n ; m ) = T _n (m ) х H (n ; m ).

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

Эти элементы образуют некоторую последовательность 0,0,1,2,1,0, 3,7,1…., к каждому члену которой мы теперь прибавим единицу:

1, 1, 2, 3, 2, 1, 4, 8, 2…

Это, безусловно, механическая процедура, и, поскольку наша таблица была получена путем вычислений, мы получим новую вычислимую последовательность 1 + Q (n ; m ), т. е.

1 + T _n (n ) х H (n ; n )

(с учетом того, что для диагональных элементов n = m ). Но наша таблица содержит в себе все вычислимые последовательности, поэтому она должна содержать также и новую последовательность. Однако это невозможно! Ведь наша новая последовательность отличается от первого ряда первым элементом, от второго — вторым, от третьего — третьим, и т. д. Налицо явное противоречие, которое и устанавливает справедливость доказываемого нами утверждения о том, что машина Тьюринга H на самом деле не существует! Иными словами, не существует универсального алгоритма для решения вопроса об остановке произвольной машины Тьюринга.

Можно построить доказательство и по-другому. Для этого заметим, что из предположения о существовании H следует и существование машины Тьюринга с номером k , реализующей алгоритм (диагональный процесс!) 1 + Q (n ; n ), т. е. можно записать

1 + T _n (n ) х H (n ; n ) = T _k (n ).

Но если мы подставим в это выражение n = k , то получится

1 + T _k (k ) x H (k ; k ) = T _k (n ).

Мы приходим к противоречию, потому что если T _k (k ) останавливается, то мы имеем невыполнимое равенство

1 + T _k (k ) = T _k (k )

(поскольку Н (k ; k ) = 1), тогда как в случае безостановочного действия T _k (k ) (т. е. когда Н (k ; k ) = 0) мы получаем не менее абсурдное соотношение

1 + 0 = ^□.

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

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

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

Как превзойти алгоритм

К вопросу о том, как установить истинность математических утверждений, мы вернемся позднее, в связи с теоремой Геделя (см. главу 4). Пока же я бы хотел обратить ваше внимание на то, что доказательство Тьюринга носит гораздо более конструктивный характер и не столь негативно, как могло показаться из предыдущего изложения. Мы ведь не показали, что есть некая определенная машина Тьюринга, для которой абсолютно невозможно решить, останавливается она или нет. Более того, если внимательно проследить за доказательством, то выяснится, что для кажущихся «чрезвычайно сложными» машин сама процедура Тьюринга, использованная для их построения, неявным образом дает ответ ! Посмотрим, как это происходит. Допустим, у нас есть алгоритм, который иногда позволяет определить, что машина Тьюринга не остановится. Вышеописанная процедура Тьюринга позволяет явно проследить за вычислениями машины Тьюринга в случае, когда этот конкретный алгоритм не дает ответа на вопрос об остановке вычислительного процесса. Однако тем самым эта процедура дает нам в этом случае возможность узнать ответ! Конкретная машина Тьюринга, за работой которой мы следим, и вправду никогда не остановится.

Чтобы подробно разобраться в этом вопросе, предположим, что у нас есть некий алгоритм, который иногда позволяет решить проблему остановки. Как и ранее, мы обозначим этот алгоритм (машину Тьюринга) через H , но теперь мы допускаем, что этот алгоритм не всегда может точно определить, что машина Тьюринга не остановится:

так что Н (n ; m ) = ^□ возможно в случае, когда T _n (m ) = ^□. Существует немало алгоритмов типа Н (n ; m ). (Например, Н (n ; m ) мог бы просто давать на выходе 1 , как только машина T _n (m ) останавливается, хотя такой алгоритм едва ли представляет большой практический интерес!)

Мы можем повторить процедуру Тьюринга, следуя уже пройденным путем, с той только разницей, что теперь некоторые из «^□» останутся не замененными на нули. Как и ранее, применив диагональный процесс, получим

1 + T _n (n ) х H (n ; n )

в качестве n -го элемента диагонали. (Мы будем иметь ^□ каждый раз, когда H (n ; n ) = ^□.

Отметим, что ^{□x□}=^□, 1 + ^□ = ^□.) Это безупречно алгоритмизованное вычисление, поэтому оно может быть произведено некоторой машиной Тьюринга, скажем k -й, и тогда мы получим

1 + T _n (n ) х H (n ; n ) = Т _k (n ).

Для k -го диагонального элемента (т. е. n = k ) мы имеем

1 + T _k (k ) x H(k ; k ) = T _k (k ).

Если вычисления Т _k (k ) останавливаются, то мы приходим к противоречию ( в этом случае Н (k ; k ) должно равняться единице, но тогда возникнет невыполнимое равенство: 1+Т _k (k ) = Т _k (k )) . Значит, Т _k (k ) не может остановиться, т. е.

Т _k (k ) = ^□.

Но алгоритм не может этого «знать», потому что, если бы он давал Н (k ; k ) = 0, мы снова пришли бы к противоречию (мы получили бы тогда неверное соотношение 1+0=^□).

Таким образом, если мы можем отыскать k , то мы знаем, как построить вычислительную процедуру, для которой алгоритм не дает решения проблемы остановки, но нам ответ известен! А как нам найти k ? Это непростая задача. Необходимо тщательно изучить конструкцию H (n ; m ) и T _n (m ) и понять, как в точности действует 1 + Т _n (n ) х Н (n ; n ) в качестве машины Тьюринга. Затем надо определить номер этой машины, который и есть k . Конечно, это выполнить трудно, но вполне возможно[53]. Из-за этих трудностей вычисление Т _k (k ) нас бы вовсе не интересовало, не будь она специально предназначена для доказательства неэффективности алгоритма H ! Важно то, что мы получили строго определенную процедуру, которая для любого наперед заданного алгоритма H позволяет найти такое k , что для Т _k (k ) этот алгоритм не может решить проблему остановки, т. е. мы тем самым превзошли его. Возможно, мысль о том, что мы «умнее» каких-то алгоритмов, принесет нам некоторое удовлетворение!

На самом деле, упомянутая процедура настолько хорошо определена, что мы могли бы даже найти алгоритм для нахождения k по заданному H . Поэтому, прежде чем мы «погрязнем» в самодовольстве, мы должны осознать, что этот алгоритм может улучшить H [54], поскольку он, по сути, «знает», что Т _k (k ) = ^□, - или все-таки нет? В предыдущем изложении было удобно использовать антропоморфный термин «знать» по отношению к алгоритму. Однако не мы ли в конечном счете «знаем», тогда как алгоритм просто следует определенным нами правилам? А может быть мы сами просто следуем правилам, запрограммированным в конструкции нашего мозга и в окружающей нас среде? Эта проблема затрагивает не только алгоритмы, но и то, как мы выносим суждения об истинности и ложности. К этим важнейшим проблемам мы вернемся позднее. Вопрос о математической истине (и ее неалгоритмической природе) будет рассмотрен в главе 4. На данный момент мы, по крайней мере, получили некоторое представление о значении слов «алгоритм» и «вычислимость» и достигли понимания некоторых из относящихся к ним вопросов.

Лямбда-исчисление Черча

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

Задача о разрешимости определенной математической операции может их заинтриговать, особенно потому, что общее решение этой головоломки само по себе алгоритмически не разрешимо.

Следует сделать еще одно замечание. Вычислимость — это по-настоящему «абсолютная» математическая идея. Это абстрактное понятие, которое никак не зависит от какой-либо конкретной реализации в терминах «машин Тьюринга» в том виде, как я их описал выше. Как я уже указывал, нет необходимости придавать какое-либо специальное значение «лентам», «внутренним состояниям» и т. п., характерным для гениального, но тем не менее частного подхода Тьюринга. Существуют также и другие способы выражения идеи вычислимости, причем исторически первым было «лямбда-исчисление», предложенное американским логиком Алонзо Черчем совместно со Стивеном Клини. Процедура, предложенная Черчем, значительно отличалась от метода Тьюринга и была гораздо более абстрактна. Фактически, форма, в которой Черч изложил свою теорию, делала связь между ними и чем бы то ни было «механическим» совсем не очевидной. Главная идея, лежащая в основе процедуры Черча, абстрактна по своей сути — это математическая операция, которую сам Черч назвал «абстрагированием».

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

В рамках этой схемы рассматривается «универсальное множество» различных объектов, обозначаемых, скажем, символами

каждый из которых представляет собой математическую операцию, или функцию . (Штрихованные буквы позволяют создавать неограниченные наборы символов для обозначения таких функций.) «Аргументы» этих функций, т. е. объекты, на которые эти функции действуют, в свою очередь являются объектами той же природы, т. е. функциями. Более того, результат действия одной функции на другую (ее «значение») также представляет собой функцию. (Поистине, в системе Черча наблюдается замечательная экономия понятий.) Поэтому, когда мы пишем[55]

а = bс ,

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

(fp)q

(что есть результат действия функции fp на функцию q ). Для функции трех переменных можно использовать выражение

((fp)q)r

и так далее.

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

λx . [fx ],

мы подразумеваем функцию, которая при действии на, например, а имеет значение fа , т. е.

(λх . [fx ])a = fа .

Другими словами, λх . [fх ] — это просто функция f , т. е.

λх . [fх ] = f .

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

λх . [sin х ] = sin .

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

Тогда мы могли бы ввести определение

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

Тогда, например,

К обсуждаемым проблемам большее отношение имеют выражения, составленные просто из элементарных функциональных операций Черча, таких как

λf.[f (fx)]

Это функция, которая, действуя на другую функцию, скажем g , дает дважды итерированную g , действующую на x

(λf.[f (fx)])g = g(gx) .

Мы могли бы сначала «абстрагироваться» от x и рассмотреть выражение

λf. [λх. [f (fх)]] ,

которое можно сократить до

λfx. [f (fx)] .

Это и есть операция, применение которой к g дает функцию «вторая итерация g ». По сути, это та самая функция, которую Черч обозначил номером 2 :

2 = λfx.[f (fx)] ,

так что (2g) y = g (gy) . Аналогичным образом он определил:

3 = λ fx. [f (f (fx))] ,

4 = λfх. [f (f (f (fx)))] , и т. д.,

а также

1 = λfх. [fх] и 0 = λ fx.

[x] .

Видно, что 2 Черча больше похоже на «дважды», 3 — на «трижды» и т. д. Значит, действие 3 на функцию f , т. е. 3f равносильно операции «применить f три раза», поэтому 3f при действии на у превращается в

(3f)y = f (f (f (y))) -

Посмотрим, как в схеме Черча можно представить очень простую математическую операцию — прибавление 1 к некоторому числу. Определим операцию

S = λabc. [b ((аb)с)] .

Чтобы убедиться, что S действительно прибавляет 1 к числу в обозначениях Черча, проверим ее действие на 3 :

поскольку (3b)с = b (b (bc)) . Очевидно, эта операция с таким же успехом может быть применена к любому другому натуральному числу Черча. (В действительности, операция

λаbс. [(аb)(bс)] приводит к тому же результату, что и S .)

А как насчет удвоения числа? Удвоение числа может быть получено с помощью операции

что легко видеть на примере ее действия на 3 :

Фактически, основные арифметические операции — сложение, умножение и возведение в степень могут быть определены, соответственно, следующим образом:

А = λfgxy. [((fx)(gx))y],

М = λfgx. [f (gx)],

P = λfg. [fg]

Читатель может самостоятельно убедиться (или же принять на веру), что

(Am) n = m + n ,

(Mm) n = m x n ,

(Pm) n = n^m ,

где m и n — функции Черча для двух натуральных чисел, m + n — функция, выражающая их сумму, и т. д. Последняя из этих функций поражает больше всего. Посмотрим, например, что она дает в случае m = 2, n = 3 :

Операции вычитания и деления определяются не так легко (на самом деле нам потребуется соглашение о том, что делать с (m — n ), когда m меньше n , и с (m/n ), когда m не делится на n ). Решающий шаг в развитии этого метода был сделан в начале 1930-х годов, когда Клини удалось найти выражение для операции вычитания в рамках схемы Черча! Затем были описаны и другие операции. Наконец, в 1937 году Черч и Тьюринг независимо друг от друга показали, что всякая вычислимая (или алгоритмическая) операция — теперь уже в смысле машин Тьюринга — может быть получена в терминах одного из выражений Черча (и наоборот).

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

Как я отмечал ранее, существуют и другие способы определения понятия вычислимости. Несколько позже, но независимо от Тьюринга, Пост предложил во многом сходную концепцию вычислительной машины. Тогда же благодаря работам Дж. Хербранда и Геделя появилось и более практичное определение вычислимости (рекурсивности). X. Б. Карри в 1929 году, и ранее, в 1924, М. Шенфинкель, предложили иной подход, который был отчасти использован Черчем при создании своего исчисления (см. Ганди [1988]). Современные подходы к проблеме вычислимости (такие как машина с неограниченным регистром, описанная Катлендом [1980]) в деталях значительно отличаются от разработанного Тьюрингом и более пригодны для практического использования. Однако понятие вычислимости во всех этих подходах остается неизменным.

Как и многие другие математические идеи, особенно наиболее фундаментальные и красивые, идея вычислимости кажется овеществленной и объективно существующей в платоновском смысле. Именно к этому мистическому вопросу о платоновской реальности математических понятий мы и обратимся в следующих двух главах.

Глава 3

Дата добавления: 2018-08-06; просмотров: 335; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 2 3 4 5 678 9 10 11 Следующая ⇒

Мы поможем в написании ваших работ!