Золотой билет - Страница 26

Машина Тьюринга казалась очень простой, однако, по словам ученого, на ней можно было вычислить все, что вообще поддавалось вычислению. Почти в то же самое время Алонзо Чёрч сделал аналогичное заявление относительно своего лямбда-исчисления, которое считают предшественником языков программирования. Тезис Чёрча – Тьюринга выдержал испытание временем, хотя сформулирован он был еще до изобретения современных компьютеров. Все, что поддается вычислению, вычислимо и на машине Тьюринга; по своим вычислительным возможностям она не уступит любому современному компьютеру, так что о ее чересчур примитивном устройстве можно не беспокоиться.

Рис. 5.1. Машина Тьюринга

Для понимания сути вычислительного процесса вам даже не нужно знать, что это за машина: достаточно взять любой язык программирования и представить, что у него есть доступ к неограниченному объему памяти. Все языки программирования функционально эквивалентны; все, что может быть запрограммировано, вычислимо и на «простенькой» машине Тьюринга.

В том же 1936 году Тьюринг доказал, что не всякую задачу можно решить на его абстрактной машине. Наиболее известный пример – проблема останова: не существует такой вычислительной машины, которая бы по коду программы определяла, остановится она или будет работать бесконечно.

Во время Второй мировой войны Алан Тьюринг был одним из главных «дешифраторов» Великобритании. В послевоенные годы он задался вопросом, можно ли на его машине сымитировать работу человеческого мозга. Ученый разработал тест, призванный определить, способна ли машина рассуждать «по-человечески»; впоследствии этот тест назвали в его честь. Представьте, что вы переписываетесь с кем-то через систему обмена сообщениями. Вы уверены, что вам отвечает человек? А вдруг это просто компьютерная программа? Программа, сумевшая обмануть большинство собеседников, проходит тест Тьюринга.

К несчастью, исследовательская деятельность Тьюринга прервалась очень рано. В 1952 году он был осужден за гомосексуализм, который в те годы считался в Великобритании противозаконным. Случившееся в конечном итоге привело к тому, что в 1954 году Тьюринг покончил жизнь самоубийством. Лишь в 2009-м британское правительство принесло официальные извинения.

За неоценимый вклад, внесенный ученым в развитие информатики и искусственного интеллекта, Ассоциация вычислительной техники назвала в его честь свою главную награду – «компьютерный» аналог Нобелевской премии. Среди ученых, о которых речь пойдет дальше, многие являются лауреатами премии Тьюринга.

Вычислительная сложность

В пятидесятых годах цифровые компьютеры распространились уже довольно широко; требовалось как-то оценивать объем вычислений, необходимый для решения той или иной задачи. Первые методы оценки появились в результате попыток формализовать процесс человеческого мышления и поведения.

В 1943 году нейропсихологи Уоррен Маккаллок и Уолтер Питтс разработали нейронную сеть – теоретическую модель, описывающую деятельность человеческого мозга. В пятидесятых годах математик и логик Стивен Клини изобрел конечный автомат – частный случай машины Тьюринга – и изучал свойства разрешимых на нем задач. При помощи конечных автоматов удобно описывать алгоритмы работы простейших агрегатов (к примеру, автомата с газировкой), однако что-то более сложное они уже не потянут.

Примерно в тот же период, в пятидесятых годах, лингвист Ноам Хомский исследовал механизмы построения предложений в английском и некоторых других языках. Он сформулировал понятие контекстно-свободной грамматики, в которой предложениям ставились в соответствие схемы, называемые «деревьями разбора». На рисунке ниже представлено дерево разбора для английского предложения The quick brown fox jumped over the lazy dog.

Рис. 5.2. Дерево разбора

С синтаксическим разбором контекстно-свободные грамматики справляются неплохо, но они не являются полными и не могут охватить все многообразие естественного языка. В лингвистической среде до сих пор ведутся споры о возможности построения идеальной грамматики.

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

В последующие годы было создано множество вычислительных моделей, однако настоящий прорыв совершили в 1962 году Юрис Хартманис и Ричард Стернс, работавшие в то время в Исследовательской лаборатории General Electric в Скенектади, штат Нью-Йорк. Для оценки качества работы программы ученые предлагали смотреть, как меняются время ее выполнения и объем задействованной памяти при увеличении объема входных данных. Блестящая идея! В 1965 году вышла их совместная статья «О вычислительной сложности алгоритмов», заложившая основы нового раздела математики – теории сложности вычислений. В 1993 году Хартманис и Стернс получили за эту работу премию Тьюринга.

В 1960-х теория вычислительной сложности развивалась сразу в двух направлениях. Приверженцы одного выбирали конкретные вычислительные модели, ограничивали время исполнения и доступный объем памяти и пытались определить, какие задачи могут быть решены при таких условиях, а какие – не могут. Мануэль Блюм, работая над диссертацией в Массачусетском технологическом институте, использовал иной – совершенно абстрактный – подход, не зависящий ни от вычислительной модели, ни от времени и памяти и каких-либо других ресурсов. Ни один из вариантов не приблизил ученых к понятию вычислительной эффективности.