Теоретическая сторона этой области не требует вычислительных машин. Но без них многие вопросы никогда бы не возникли.
Теоретик информатики Эдсгер Дейкстра, лауреат премии Тьюринга и изобретатель одного из самых знаковых алгоритмов в истории вычислительной техники, был человеком с твердыми убеждениями. Например, его раздражали некоторые языки программирования: однажды он назвал Фортран «инфантильным расстройством» и заявил, что «использование COBOL калечит разум; поэтому его преподавание следует считать уголовным преступлением». Оправдывая свое пренебрежение к использованию компьютеров в собственной работе, он писал: «От исследователей в области медицины не требуется страдать от болезней, которые они изучают».
Впервые я столкнулась с резкими высказываниями Дейкстры почти четыре года назад, вскоре после того, как пришла в Quanta в качестве штатного автора, пишущего о компьютерных науках. Эта тема была для меня новой — до этого я работала журналистом в сфере физики, а до этого была физиком, — и вскоре я поняла, что большинство людей не знают, что значит «автор, пишущий о компьютерных науках». В широком общественном дискурсе компьютерные науки практически синонимичны программированию, но в Quanta мы освещаем менее понятную теоретическую сторону этой области. И тут я наткнулся на свое любимое из множества запоминающихся высказываний, приписываемых Эдсгер Дейкстре: «Информатика связана с компьютерами не больше, чем астрономия — с телескопами».
В философии «квалиа» относится к субъективным качествам нашего восприятия: к тому, что значит для Алисы видеть синий цвет, а для Боба — испытывать восторг. Квалиа — это «то, как вещи кажутся нам», как выразился покойный философ Дэниел Деннет. В этих статьях наши авторы следуют своему любопытству и исследуют важные, но не обязательно имеющие ответ научные вопросы. Как выяснилось, эта аналогия не принадлежит Эдсгер Дейкстре, но он, вероятно, поддержал бы эту мысль. Для меня эта цитата стала лаконичным и провокационным способом отличить мои репортажи от технической журналистики. И я не могу отрицать, что она была лестна для меня: она намекала на то, что сфера, которую я освещаю, связана с чем-то глубоким, вневременным и выходящим за рамки простых технологических инноваций.
У меня вошло в привычку регулярно прибегать к этой аналогии — в том числе в эпизоде подкаста The Quanta, — но со временем я начал сомневаться в ней по причинам, которые не мог толком сформулировать. Чувствовал ли я себя виноватым из-за того, что косвенно подшучивал над своими бывшими коллегами, которые строят телескопы, или в этой аналогии упущено что-то важное?
Я решил разобраться. Является ли информатика наукой о компьютерах? А если нет, то о чем она?
Я ввязался в очень давнюю дискуссию. Исследователи начали разрабатывать математическую теорию вычислений в 1930-х годах. В 1940-х инженеры создали первые электронные компьютеры общего назначения. Информатика как отдельная академическая дисциплина сформировалась в последующие десятилетия, когда объединились исследовательские традиции математики и инженерии, и вскоре начались споры о природе новой области. В 1967 году выдающиеся ученые в области компьютерных наук Аллен Ньюэлл, Алан Перлис и Герберт Саймон обозначили свою позицию в эмоциональном письме редактору в журнале Science. «Там, где есть явления, может быть и наука, которая описывает и объясняет эти явления, — писали они, возможно, с некоторым раздражением. — Есть компьютеры. Следовательно, информатика — это наука о компьютерах».
У информатики два родителя. Один — математика, другой — инженерия, и на самом деле информатика — это их гибрид. Уильям Рапапорт, Университет Буффало
Ньюэлл, Перлис и Саймон адресовали свое письмо в том числе критикам, которые утверждали, что любая наука, достойная этого названия, должна изучать природные явления. В ответ они привели примеры искусственных явлений, которые считаются достойными изучения в таких признанных науках, как химия. В своей книге «Науки об искусственном» 1969 года Саймон пошел дальше и признал это различие: по его мнению, именно акцент на намеренно созданных искусственных системах делает компьютерную науку особенной.
В 1974 году учёный-компьютерщик Дональд Кнут предложил свой взгляд на эту область, в котором акцент делался на процессе вычислений, а не на самих компьютерах. Он определил информатику как науку об алгоритмах, то есть о точных пошаговых процедурах, которые компьютеры используют для выполнения задач. Алгоритмы могут быть реализованы на разных языках программирования — примерно так же, как идеи могут быть выражены на английском, китайском или арабском языках. Люди тоже используют алгоритмы — не только для решения математических задач, но и для сортировки предметов. С этой точки зрения математика, лежащая в основе вычислений, играет ключевую роль. Сами по себе компьютеры важны только потому, что они позволяют решать задачи, на которые у нас, людей, не хватает ни времени, ни терпения.
Определение Кнута мне нравится, но трудно отрицать простоту определения, предложенного Саймоном и его коллегами. Однако ни это, ни какое-либо другое определение, похоже, не получило всеобщего признания среди исследователей. Почему это так?» Я спросил Уильяма Рапапорта — почетного профессора информатики и философии в Университете Буффало, который подробно описал множество предложенных определений информатики. Он предположил, что разногласия в конечном счете связаны с междисциплинарным характером этой области.
«У информатики два родителя, — сказал он мне. — Один — это математика, а другой — инженерное дело, и на самом деле информатика — это нечто среднее между ними».
Рапапорт по-прежнему видит в этой области своего рода интеллектуальное единство — это нечто большее, чем просто математика и инженерия в одном флаконе. По его мнению, информатика — это изучение двух центральных вопросов, каждый из которых каждая из областей решает по-своему: «Что можно вычислить и как это вычислить?». Такой подход показался мне полезным. Очевидно, что есть области компьютерных наук, в которых компьютерное оборудование и программное обеспечение играют ключевую роль, например разработка операционных систем или изучение управления памятью. Но в конечном счете меня больше всего интересует теоретическая сторона этой области, где исследователям не нужно иметь дело с реальным, физическим компьютером. Играют ли компьютеры ключевую концептуальную роль в этой теоретической работе? Вот что мне нужно было бы выяснить, если бы я хотел разобраться со своими противоречивыми чувствами по поводу цитаты Эдсгера Дейкстры.
Давайте начнем с первого вопроса Рапапорта: что можно вычислить? Чтобы хотя бы попытаться ответить на этот вопрос с теоретической точки зрения, нужно начать с математической формализации вычислений — того, что исследователи называют моделью вычислений. В 1930-х годах исследователи предложили несколько различных моделей вычислений и начали изучать их применение.
Другие науки можно рассматривать через призму вычислений. Именно этот основополагающий логический принцип проявляется практически везде. Том Гур, Кембриджский университет
Затем, в знаменитой статье 1937 года, математик Алан Тьюринг разработал модель, основанную на гипотетических машинах, которые могли бы считывать и записывать символы, напечатанные на бесконечной ленте, в соответствии с набором простых правил. Вскоре Тьюринг и другие исследователи доказали, что эта оказавшая огромное влияние модель «машины Тьюринга» математически эквивалентна моделям, предложенным другими учёными. Внезапно вместо нескольких отдельных определений у исследователей появилась единая универсальная теория вычислений. Однако теория вычислений Тьюринга на самом деле не имела отношения к компьютерам, по крайней мере на первых порах. Когда Тьюринг писал свою основополагающую статью, у него не только не было компьютера общего назначения, но он даже не стремился понять, как могут работать такие машины будущего. Скорее, он пытался решить центральную проблему в области оснований математики. Он рассматривал свою машину как способ моделирования мыслительной деятельности человека, выполняющего вычисления.
Более того, теория вычислений применима к вещам, которые мы не назвали бы компьютерами. Исследователи часто изучают природные процессы, моделируя их как вычисления и анализируя математически. Они использовали этот подход для выявления непредсказуемого поведения в физических системах, анализа эволюционной динамики и решения задач в области квантовой гравитации, а также для других целей. По иронии судьбы, область, которую Саймон еще в 1960-х годах назвал «наукой об искусственном», сегодня занимает центральное место в нашем понимании мира природы.
«С помощью вычислений можно взглянуть на другие науки по-новому, — говорит Том Гур — специалист по теоретической информатике из Кембриджского университета. — Этот базовый логический принцип проявляется практически везде».
Ответ на первый вопрос Рапапорта, похоже, подтверждает правоту цитаты Эдсгера Дейкстры. А вот второй вопрос Рапапорта: если вы решили, что хотите что-то вычислить, как именно вы это сделаете? Для специалистов по теоретической информатике ответ кроется в математике алгоритмов. В конце 1960-х — начале 1970-х годов они начали разрабатывать систему для количественной оценки времени, необходимого алгоритмам для решения различных задач, на абстрактном математическом уровне, без учета особенностей компьютерного оборудования.
Вскоре они поняли, что существуют важные качественные различия между задачами, которые могут возникнуть в практических приложениях, например при планировании маршрутов в сети или при разложении чисел на множители. Все эти задачи в принципе можно решить с помощью алгоритмов. Однако только для некоторых из них существовали эффективные алгоритмы, способные быстро найти решение. Для других же единственные известные алгоритмы были мучительно медленными. Попытки разобраться в этих различиях положили начало теории сложности вычислений — разделу теоретической информатики, который изучает внутреннюю сложность различных задач и служит основой для современных схем шифрования.
«Математические задачи имеют фундаментальную структуру, которая делает их решение более или менее простым, — говорит Кристофер Мур — специалист по теоретической информатике из Института Санта-Фе. — Дело не в том, насколько быстр ваш компьютер, и не в том, насколько вы умны». Если математика в каком-то смысле является языком реальности, то выявление этой скрытой структуры может ощущаться «как открытие законов Вселенной», как выразился специалист по теории сложности Валентин Кабанец из Университета Саймона Фрейзера в Канаде, когда я несколько лет назад брал у него интервью для головоломной статьи о самой известной нерешенной проблеме в теории сложности.
Дальнейшие разработки в области теории сложности указывали на направления, которые, казалось, имели еще меньше отношения к вычислениям. В качестве примера Гур привел новые представления о математическом доказательстве, появившиеся в теории сложности в 1980–1990-х годах. Представляя доказательство как интерактивный процесс, ученые-компьютерщики обнаружили, что можно доказать истинность утверждения, ничего не объясняя, и что можно проверить правильность некоторых доказательств, проверив лишь несколько небольших фрагментов.
«Внезапно мы сталкиваемся с совершенно новыми типами вопросов, — сказал Гур. — Мы говорим о чем-то, что выходит далеко за рамки вычислений».
На мой взгляд, все это складывается в убедительную картину компьютерной науки без компьютеров. «Здесь были фундаментальные вопросы, которые можно было задать сотни лет назад, — сказал Скотт Ааронсон — специалист по теоретической информатике из Техасского университета в Остине, который также является членом консультативного совета Quanta. — Просто никому не пришло в голову их задать».
Конечно, это порождает другой вопрос: почему бы и нет?
По крайней мере, один человек задался этими фундаментальными вопросами. Чарльз Бэббидж — эрудит XIX века, разработавший вычислительную машину общего назначения, которую он назвал аналитической машиной, в своей автобиографии предположил, что его новая машина потребует новой теории алгоритмов. «Всякий раз, когда с его помощью пытаются получить какой-либо результат, — писал он, — возникает вопрос: каким путем машина может прийти к этим результатам за кратчайшее время?»
Бэббидж так и не закончил свою аналитическую машину, и неясно, как именно он планировал решить этот важный вопрос. Возможно, он предполагал, что технические особенности конструкции машины позволят одним методам работать быстрее других. Нет никаких свидетельств того, что он предвидел что-то вроде богатой математической структуры, которую впоследствии открыли специалисты по теории сложности. Но, как мне кажется, именно в этом и заключается суть. Главный вопрос теории сложности — почему для некоторых задач не существует быстрых алгоритмов — на первый взгляд может показаться не таким уж сложным. Его глубина становится очевидной, только когда вы начинаете его изучать. И только в 1960-х годах, когда исследователи начали экспериментировать с настоящими компьютерами, этот вопрос показался им достойным внимания.
Я думаю, что именно этого не хватает в представлении о компьютерных науках, которое преуменьшает роль компьютеров: в истории глубокие теоретические вопросы часто переплетаются с практическими, связанными с созданием более совершенных машин.
Матти Тедре, специалист по информатике из Университета Восточной Финляндии и автор книги о дисциплинарной идентичности этой области, не является поклонником цитаты Эдсгера Дейкстры в том виде, в котором она обычно трактуется. Тем не менее сравнение с астрономией может быть уместным в другом смысле. «[Дейкстра] абсолютно прав, но он ошибается в том, что касается важности телескопов для астрономии, — сказал Тедре. — Если бы у нас не было телескопов, мы бы ничего не знали о Вселенной». Помимо области компьютерных наук, здесь можно найти уроки, которые помогут нам понять научный прогресс в целом. Согласно распространенному мнению, прорывы в фундаментальной науке стимулируют развитие технологий: например, квантовая физика привела к изобретению транзистора, а теория относительности — к появлению GPS. История компьютерных наук показывает, что взаимодействие фундаментального и практического имеет более сложную природу, и это можно проследить и в других дисциплинах. Ааронсон указал на второй закон термодинамики, который гласит, что энтропия, мера беспорядка, со временем имеет тенденцию к увеличению.
«Возможно, это самое фундаментальное утверждение об эволюции всей Вселенной, — сказал он. — И все же никто не задумывался об этом, пока не начали строить паровые двигатели».
Или, как выразился специалист по теории сложности Райан Уильямс из Массачусетского технологического института, “Достаточно интересные проблемы на практике порождают большие теоретические вопросы”.
