Питер Эткинз - Десять великих идей науки. Как устроен наш мир.

Я рассмотрю теперь две из важнейших проблем Гильберта, те две, которые наносят удар в самое сердце философии математики и наиболее прямо исследуют ее возможности. Как я уже упоминал, одной из этих проблем является так называемая 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 и сдвигает ленту на один шаг вправо. Если реакции головки искусно запрограммированы, машину можно использовать для выполнения даже самых сложных вычислений. Реальное конструирование такой головки и ее реакций может быть весьма сложной процедурой, а вычисления могут быть очень медленными, но здесь нас интересует лишь принцип вычислений, а не их эффективность.

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

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