Книга: Золотой билет

Алан Тьюринг

Алан Тьюринг

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

Слово computer появилось еще в XVII веке. В те времена никому и в голову не приходило изобретать машины, которые бы что-либо вычисляли. Компьютерами, или вычислителями, называли мастеров счета, занимавшихся вычислениями профессионально. С развитием банковской системы на вычислителей «свалились» еще и вклады и кредиты.

Согласно Оксфордскому словарю, для обозначения механического счетного устройства слово computer впервые применили в 1897 году, а для электронного – в сороковых годах прошлого века. Так от людей-вычислителей термин перешел к огромным установкам из нескольких вычислительных машин, а затем и к компьютерам, которыми мы пользуемся сейчас.

Если абстрагироваться от технической части, то задача компьютера – получить входные данные, обработать их согласно заданным инструкциям и выдать некий результат. С этой точки зрения компьютером является даже обычная почта, которая принимает на вход письмо, обрабатывает указанный на нем адрес и доставляет письмо получателю, а также любой живой организм, который обрабатывает последовательность ДНК и производит необходимые для жизни белки.

А как обстоит дело с самим процессом вычисления? Есть ли что-то такое, что вычислению не поддается? Вопрос был решен еще до появления вычислительных машин: в 1936 году ответ на него дал великий математик Алан Тьюринг. Размышляя над тем, как рассуждают математики, Тьюринг пришел к формальной математической модели вычислительного процесса, которая впоследствии стала классической. Теперь ее называют машиной Тьюринга.

Тьюринг родился в 1912 году в Лондоне. В начале тридцатых он поступил в Королевский колледж Кэмбриджа, где показал необыкновенные успехи в математике. Использовав себя в качестве наглядного примера, Тьюринг попытался описать, каким образом математики выполняют вычисления. В голове у ученого происходит некий процесс; его память ограничена, а бумага и ручки имеются в изобилии. Сделав очередную запись, он либо переходит к следующей странице, либо возвращается на предыдущую, чтобы изменить то, что было написано ранее. Формализовав этот интуитивный алгоритм, Тьюринг создал абстрактную модель вычислений.

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

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

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

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

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

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

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

Оглавление книги