Чтение онлайн

Я рассмотрю теперь две из важнейших проблем Гильберта, те две, которые наносят удар в самое сердце философии математики и наиболее прямо исследуют ее возможности. Как я уже упоминал, одной из этих проблем является так называемая Entscheidungsproblem, проблема отыскания систематического способа для определения того, можно ли доказать некоторое утверждение символического языка с помощью аксиом этого языка. Атаку на эту проблему почти одновременно предприняли двое, одним был американский логик Алонзо Чёрч (1903-95), который ввел и разработан то, что он назвал -исчислением, а другим — британский математик Алан Мэтисон Тьюринг (1912-54), который ввел «логическую вычислительную машину», известную как машина Тьюринга. Эти два подхода изначально были различны на поверхностном уровне, но сотрудничество Чёрча и Тьюринга показало, что на самом деле они математически эквивалентны. Существует одна чрезвычайно важная сильная сторона математики, ее способность показывать эквивалентность с виду совершенно несравнимых вещей. Мы сосредоточим внимание на подходе Тьюринга, поскольку он имеет больше сходства со знакомым нам современным миром компьютеров, но не должно пройти незамеченным, что -исчисление Чёрча ассоциируется с используемым в них программным обеспечением и является его основой.

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

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

Предположим, что ячейки бумажной ленты могут содержать либо 0, либо 1, а головка, в зависимости от своего внутреннего состояния, может считывать ячейку, записывать в ячейку и передвигать ленту на одну ячейку вправо или влево. Конкретная машина Тьюринга будет выполнять серию операций в зависимости от того, что она обнаружит на ленте, и в соответствии со способом реагирования, на который настроена ее головка. Например, если она обнаруживает на ленте 1, когда сама находится в состоянии «1», она может заменить на ленте 1 на 0, поменять свое внутреннее состояние на «2» и сдвинуть ленту на один шаг вправо. В новой ячейке может оказаться 0. Когда головка находится в состоянии «2» и считывает 0, она, возможно, запрограммирована на сдвиг ленты на один шаг влево, а если она считывает 1, то меняет 1 на 0 и сдвигает ленту на один шаг вправо. Если реакции головки искусно запрограммированы, машину можно использовать для выполнения даже самых сложных вычислений. Реальное конструирование такой головки и ее реакций может быть весьма сложной процедурой, а вычисления могут быть очень медленными, но здесь нас интересует лишь принцип вычислений, а не их эффективность.

Каждая из машин Тьюринга представляет собой специальное устройство из ленты и считывающей головки, определенным образом запрограммированной. Давайте предположим, что мы можем пронумеровать все возможные машины Тьюринга, так что у нас есть склад с ящиками, помеченными знаками t 1, t 2, и так далее. Если одна из этих машин принимает определенное число и останавливается, мы обнаружим определенное число на выходе. Например, если машина t 10принимает число 3, это может означать 42 на выходе и конец вычислений. Чтобы зарегистрировать этот результат, запишем t 10(3) = 42. Однако может существовать комбинация машины и значения числа, для которой вычисления никогда не закончатся, например, если машина t 22принимает число 17. Чтобы зарегистрировать этот результат, запишем t 22(17) = . Перед Тьюрингом стояла задача узнать, существует ли способ проверки всех возможных машин и принимаемых ими значений чисел и принятия на основе этой проверки решения, будут ли вычисления когда-либо закончены.

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

Подобным же образом, код 010 может означать:

Программная часть ленты может выглядеть как …001010…, если эти две инструкции надо выполнить последовательно. Мы будем называть универсальную машину Тьюринга tu. Заметим, что, в то время как индивидуальнаямашина Тьюринга считывает только данные, универсальнаямашина сначала считывает программу, чтобы подготовить себя, а затем уж считывает данные. Так, если мы хотим, чтобы она имитировала t 10, мы считываем программу 10, то есть множество инструкций, настраивающих машину на работу в режиме t 10, а затем скармливаем ей данные. Если данные состоят из числа 3, мы будем ожидать от этого совместного процесса ответ 42 и запишем tu(10,3) = 42, где первое число в скобках является номером машины Тьюринга, которую мы хотели имитировать, а второе число представляет данные.

Предположим теперь, что существует машина Тьюринга, которая может взять программу любой другой машины Тьюринга, например t 23, и любое множество данных, и решить, остановится или нет эта комбинация, чтобы напечатать ответ. Мы назовем эту особую машину Тьюринга th (hздесь от английского глагола «halt» — останавливаться). Если thполучает остановку для частной комбинации программы и данных, например t 23и 3, она напечатает 1 и остановится; если она определяет, что комбинация не приводит к остановке, например t 22и 17, thнапечатает 0 и остановится. Успех Тьюринга выразился в доказательстве того, что thне включена в список всех возможных машин Тьюринга и поэтому не существует. Чтобы проделать это, он использовал аргументы, очень похожие на «диагональные» аргументы, которыми пользовался Кантор для доказательства того, что иррациональные числа несчетны. Вы можете свободно перейти к следующему подразделу, если хотите пропустить вывод этого результата.

Эти аргументы таковы. Предположим, что мы задаем входные данные 0, 1, 2, … и машины Тьюринга t 0, t 1, t 2, … и составляем таблицу, верхним левым фрагментом которой является следующая:

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

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