Я рассмотрю теперь две из важнейших проблем Гильберта, те две, которые наносят удар в самое сердце философии математики и наиболее прямо исследуют ее возможности. Как я уже упоминал, одной из этих проблем является так называемая Entscheidungsproblem, проблема отыскания систематического способа для определения того, можно ли доказать некоторое утверждение символического языка с помощью аксиом этого языка. Атаку на эту проблему почти одновременно предприняли двое, одним был американский логик Алонзо Чёрч (1903-95), который ввел и разработан то, что он назвал λ-исчислением, а другим — британский математик Алан Мэтисон Тьюринг (1912-54), который ввел «логическую вычислительную машину», известную как машина Тьюринга. Эти два подхода изначально были различны на поверхностном уровне, но сотрудничество Чёрча и Тьюринга показало, что на самом деле они математически эквивалентны. Существует одна чрезвычайно важная сильная сторона математики, ее способность показывать эквивалентность с виду совершенно несравнимых вещей. Мы сосредоточим внимание на подходе Тьюринга, поскольку он имеет больше сходства со знакомым нам современным миром компьютеров, но не должно пройти незамеченным, что λ-исчисление Чёрча ассоциируется с используемым в них программным обеспечением и является его основой.
Машина Тьюринга является прибором, который претендует на имитацию действий человека, производящего некоторого рода алгоритмическое вычисление, то есть вычисление, выполняемое с помощью серии последовательных правил, и в котором мы теперь узнаем представление цифрового компьютера. К первой реализации программируемого цифрового электронного компьютера Тьюринга привела, конечно, его работа со взламыванием кодов во время Второй мировой войны на Блетчли-парк, на севере Лондона, а позже в Манчестере. Благодаря успехам во взламывании кодов, на счету Тьюринга оказалось приписываемое ему уменьшение продолжительности войны на месяцы, если не на годы, и, определенно, спасение многих тысяч жизней. К позору для Англии середины двадцатого столетия, Тьюринг, преследуемый законами и нравами общества того времени (он был гомосексуалистом), рано закончил свою жизнь.
Тьюринг искал путь для извлечения сущности того способа, которым человек производит вычисления, а затем исследовал ограничения этого процесса, пытаясь выяснить, возможен ли вопрос, ответ на который, как бы долго ни работал человек, не будет получен? Вариант процедуры, предложенный Тьюрингом, был заключен в капсулу прибора, состоящего из бесконечно длинной ленты бумаги (в подражание бесконечному источнику бумаги и карандашей, которым может располагать человек- вычислитель при выполнении расчетов, делая записи промежуточных вычислений и затем записывая окончательный ответ) и считывающей и пишущей головки, которую можно запрограммировать так, чтобы она реагировала по определенным правилам на то, что записано в ячейке, проходящей мимо нее в данный момент (рис. 10.10). Эти правила можно было видоизменять и направлять на читающую головку с бумажной ленты.
Рис. 10.10. Версия машины Тьюринга. Машина состоит из бесконечно длинной ленты бумаги, разделенной на ячейки, в которых могут быть записаны символы (обычно, 0 или 1), и механизма, который может считывать эти символы, реагируя на считываемое в соответствии со своим внутренним состоянием в данный момент, меняя символы, если это требуется, и переходя к соседним ячейкам в соответствующем направлении. В этом представлении внутреннее состояние обозначается световым сигналом на одной из сторон считывающей головки. Правая диаграмма показывает возможный отклик: машина находится во внутреннем состоянии, обозначенном световым сигналом, и считывает 1; в результате она заменяет 1 на 0, меняет свое внутреннее состояние и сдвигает ленту на один шаг вправо.
Предположим, что ячейки бумажной ленты могут содержать либо 0, либо 1, а головка, в зависимости от своего внутреннего состояния, может считывать ячейку, записывать в ячейку и передвигать ленту на одну ячейку вправо или влево. Конкретная машина Тьюринга будет выполнять серию операций в зависимости от того, что она обнаружит на ленте, и в соответствии со способом реагирования, на который настроена ее головка. Например, если она обнаруживает на ленте 1, когда сама находится в состоянии «1», она может заменить на ленте 1 на 0, поменять свое внутреннее состояние на «2» и сдвинуть ленту на один шаг вправо. В новой ячейке может оказаться 0. Когда головка находится в состоянии «2» и считывает 0, она, возможно, запрограммирована на сдвиг ленты на один шаг влево, а если она считывает 1, то меняет 1 на 0 и сдвигает ленту на один шаг вправо. Если реакции головки искусно запрограммированы, машину можно использовать для выполнения даже самых сложных вычислений. Реальное конструирование такой головки и ее реакций может быть весьма сложной процедурой, а вычисления могут быть очень медленными, но здесь нас интересует лишь принцип вычислений, а не их эффективность.
Каждая из машин Тьюринга представляет собой специальное устройство из ленты и считывающей головки, определенным образом запрограммированной. Давайте предположим, что мы можем пронумеровать все возможные машины Тьюринга, так что у нас есть склад с ящиками, помеченными знаками t1, t2, и так далее. Если одна из этих машин принимает определенное число и останавливается, мы обнаружим определенное число на выходе. Например, если машина t10 принимает число 3, это может означать 42 на выходе и конец вычислений. Чтобы зарегистрировать этот результат, запишем t10(3) = 42. Однако может существовать комбинация машины и значения числа, для которой вычисления никогда не закончатся, например, если машина t22 принимает число 17. Чтобы зарегистрировать этот результат, запишем t22(17) = □. Перед Тьюрингом стояла задача узнать, существует ли способ проверки всех возможных машин и принимаемых ими значений чисел и принятия на основе этой проверки решения, будут ли вычисления когда-либо закончены.
Чтобы выполнить эту программу, предположим, что существует универсальная машина Тьюринга, которая является такой машиной Тьюринга, которую можно запрограммировать для имитации любой индивидуальной машины Тьюринга. У этой машины входная лента имеет две секции, одна для программы, а другая для данных. Программная часть может состоять из строки чисел, которые инструктируют головку, как реагировать на то, что она обнаруживает на ленте. Например, код 001 может означать:
001: если вы обнаруживаете на ленте 1 и находитесь в состоянии 1, замените 1 на 0, смените ваше внутреннее состояние на состояние 2 и передвиньтесь на один шаг вправо.
Подобным же образом, код 010 может означать:
010: если вы обнаруживаете на ленте 0 и находитесь в состоянии 2, передвиньтесь на один шаг влево; а если вы считываете 1, то замените 1 на 0 и передвиньтесь на один шаг вправо.
Программная часть ленты может выглядеть как …001010…, если эти две инструкции надо выполнить последовательно. Мы будем называть универсальную машину Тьюринга tu. Заметим, что, в то время как индивидуальная машина Тьюринга считывает только данные, универсальная машина сначала считывает программу, чтобы подготовить себя, а затем уж считывает данные. Так, если мы хотим, чтобы она имитировала t10, мы считываем программу 10, то есть множество инструкций, настраивающих машину на работу в режиме t10, а затем скармливаем ей данные. Если данные состоят из числа 3, мы будем ожидать от этого совместного процесса ответ 42 и запишем tu(10,3) = 42, где первое число в скобках является номером машины Тьюринга, которую мы хотели имитировать, а второе число представляет данные.
