От пальцевого счета до суперкомпьютеров      

Машина Тьюринга

Алан Мэтисон Тьюринг - выдающийся английский математик, совершивший грандиозное открытие, которое положило начало компьютерной эре. В свои неполные 24 года он мысленно сконструировал абстрактный механизм, призванный решить одну из фундаментальных проблем математики, поставленную знаменитым немецким профессором Давидом Гильбертом в 1900 г. на парижском Международном конгрессе математиков. Тем самым Тьюринг не только дал четкий ответ на эту конкретную задачу, но и - что гораздо важнее - сформировал научную основу алгоритма и предвосхитил архитектуру современных компьютеров. Более того, сама идея решения задач путем конструирования абстрактных механизмов, исполняемых на электронных устройствах, стала важнейшей для зарождения новой профессиональной сферы интеллектуальной деятельности - программирования. Тьюринг показал, что не существует "чудесной машины", способной решать все математические задачи. Но продемонстрировав ограниченность возможностей, он на бумаге построил то, что позволяет решать очень многое и что мы теперь называем словом "компьютер".

Машина Тьюринга имеет бесконечную в обе стороны ленту, разделенную на квадратики (ячейки). В каждой ячейке может быть записан некоторый символ из фиксированного (для данной машины) конечного множества, называемого алфавитом данной машины. Один из символов алфавита выделен и называется "пробелом", предполагается, что изначально вся лента пуста, то есть заполнена пробелами.

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

Таким образом, чтобы задать машину Тьюринга, надо указать следующие объекты:

• произвольное конечное множество A (алфавит); его элементы называются символами;
• некоторый выделенный символ a0 из A (пробел, или пустой символ);
• конечное множество S, называемое множеством состояний;
• некоторое выделенное состояние s0 из S, называемое начальным;
• таблицу переходов, которая определяет поведение машины в зависимости от состояния и текущего символа (см. ниже);
• некоторое подмножество F, входящее в S, элементы которого называются заключительными состояниями (попав в такое состояние, машина останавливается).

Таблица переходов устроена следующим образом: для каждой пары (текущее состояние, текущий символ) указана тройка (новое состояние, новый символ, сдвиг). Здесь сдвиг одно из чисел -1 (влево), 0 (на месте) и 1 (направо). Таким образом, таблица переходов есть функция типа S x A -> S x A x {-1,0,1}, определенная на тех парах, в которых состояние не является заключительным.

Остается описать поведение машины Тьюринга. В каждый момент имеется некоторая конфигурация, складывающаяся из содержимого ленты (формально говоря, содержимое ленты есть произвольное отображение Z -> A), текущей позиции головки (некоторое целое число) и текущего состояния машины (элемент S). Преобразование конфигурации в следующую происходит по естественным правилам: мы смотрим в таблице, что надо делать для данного состояния и для данного символа, то есть выясняем новое состояние машины, меняем символ на указанный и после этого сдвигаем головку влево, вправо или оставляем на месте. При этом если новое состояние является одним из заключительных, работа машины заканчивается. Остается договориться, как мы подаем информацию на вход машины и что считается результатом ее работы. Будем считать, что алфавит машины, помимо пробела, содержит символы 0 и 1 (а также, возможно, еще какие-то символы). Входом и выходом машины будут конечные последовательности нулей и единиц (двоичные слова). Входное слово записывается на пустой ленте, головка машины ставится в его первую клетку, машина приводится в начальное состояние и запускается. Если машина останавливается, результатом считается двоичное слово, которое можно прочесть, начиная с позиции головки и двигаясь направо (пока не появится символ, отличный от 0 и 1).

Детерминированность машины Тьюринга породила ложные представления об истинных возможностях компьютеров и воззрениях самого Алана Тьюринга.Немногие знают, что в 1951 г. Тьюринг выступил в Манчестере с лекцией "Интеллектуальные машины. Еретическая теория" (развитие его работы 1948 г.). Он сказал: "Моя точка зрения такова: можно сконструировать машины, которые весьма близко смогут моделировать поведение человеческого разума. Порой они будут ошибаться, а иногда смогут выдавать новые весьма интересные утверждения, и в целом их выводы будут заслуживать внимания в такой же степени, как и сделанные человеческим разумом. Данное утверждение основывается на ожидаемой большой частоте истинных утверждений, и я думаю, что ему нельзя дать строгое обоснование".

Тьюринг отмечает в своей лекции важнейший момент: "Я уверен, что опасность того, что математик сделает ошибку, является неизбежным следствием его способности порой находить принципиально новый метод. Похоже, это подтверждается хорошо известным фактом, что наиболее надежные люди обычно не обнаруживают действительно новых методов". Вот он, ключ к разгадке тайн мышления. Как ни парадоксально, именно возможность ошибок в мыслительном процессе машины открывает перспективы ее интеллектуальной мощи. Тьюринг завершает свою лекцию пророчеством: "Нужно было бы приложить массу усилий, пытаясь, скажем, мыслить на равных с машиной, поскольку представляется вероятным, что как только начнется машинный способ мышления, ему не потребуется много времени, чтобы превзойти наши слабые мыслительные способности. Не возникал бы вопрос о смерти машин, и они могли бы быть способны общаться друг с другом, оттачивая свой разум. Таким образом, на некотором этапе мы могли бы ожидать, что машины получат власть, как описано в "Эрехоне" Сэмюэла Батлера".